The Setting
A two-way automaton working on a block of its tape enters and leaves the block through its two boundaries, possibly many times. A boundary diagram records such crossings as edges between labels at the two boundaries, and gluing two blocks side by side multiplies their diagrams. For an idempotent diagram , the question is how the edges that cross from one boundary to the other are grouped by the labels at which such crossings recur, and which of these edges a diagram in the corner of must keep.
Diagrams and Their Product
A boundary diagram on labels is a quadruple of relations on two copies and of an -element label set: the forward relation , whose edges enter on the left and exit on the right; the backward relation , whose edges enter on the right and exit on the left; the left relation , whose edges enter and exit on the left; and the right relation , whose edges enter and exit on the right.✦ The set of boundary diagrams on labels is .
The product of two diagrams and is the diagram obtained by gluing to the left of . With relations composed in path order, and with the reflexive transitive closure of a relation , where is the identity, its relations are (1)✦
The corner of a diagram is the set of diagrams nested in , written : those with and .✦
Edge inclusion is the relation on under which when , , and .✦
Recurrent Classes and Rectangles
A sign is one of and , and is the corresponding copy of the label set. The through relation of a diagram at a sign is the relation on of its through edges in the direction of : and .✦ The loop closure of a diagram at is the relation on that closes up the alternating returns at a boundary: and .✦ The recurrence relation of at , and the surviving relation of a second diagram relative to at , are the relations on (2)
A label is recurrent for at when . The set of signed recurrent classes of consists of the pairs of a sign and a set of labels such that, for some label recurrent at , (3)✦ The set of classes missing after is replaced by a diagram consists of the classes of such that no label has .✦
The rectangle of at a sign and a label is the relation on , where (4)✦
The Claim
Theorem 1. Let be a diagram on labels and a sign.
If is idempotent, then for every label (5)✦
If is idempotent and and are labels with and in , then (6)✦
If is idempotent, then (7)✦
If is a diagram nested in and is a label with , then (8)✦
If is idempotent and is a diagram nested in with , then (9)✦
In the paper, the result reads: for idempotent and in the corner of , the rectangle of a positive class and a label is independent of and contained in , these rectangles cover , the rectangle of a class lies in , reflected statements hold for negative classes, and in particular implies . The box indexes rectangles by labels rather than by classes.
What Is Checked
The claims (5) through (9) are stated over boundary diagrams on labels, their product (1) with the reflexive transitive closure it uses, the corner of a diagram, edge inclusion, the through relations and loop closures, the recurrence and surviving relations (2), the signed recurrent classes (3), the missing classes and the rectangles (4).