The Setting
A two-way automaton can cross a block of its tape many times in one run, entering the block on the left or on the right and leaving it on either side. Boundary diagrams record such crossings. A boundary diagram on labels is a quadruple of relations on two copies and of an -element label set: the forward relation , entering on the left and leaving on the right; the backward relation , entering on the right and leaving on the left; the left relation , entering and leaving on the left; and the right relation , entering and leaving on the right.✦ The left and right relations are the returns of , and the set of boundary diagrams on labels is .
Relations compose in path order: when and for some . The reflexive transitive closure of a relation on a set is the relation (1)✦ where is the identity relation on .
The product of two boundary diagrams and on labels is the boundary diagram obtained by gluing to the left of , with relations (2)✦ A diagram is idempotent when .
Fix an idempotent diagram . Through paths of , joined by the returns that bounce back and forth at the junction of two copies of , can come back to the label they started from, and the labels on such loops fall into classes, one family for each sign, or , according to the copy or in which the labels lie. The classes are counted, and those that go missing when is replaced by a diagram with and are singled out.
Loop Closures and Recurrent Classes
Write for a sign, and for the copy of the label set carrying it. The through relation of sign of a diagram is its forward relation for and its backward relation for .✦
Closing up the returns at the junction of two copies of a diagram gives its loop closures: the loop closure of sign is the relation on given by (3)✦ The recurrence relation of sign of is the relation on made of a through step of with a loop closure on either side: (4)✦
A signed recurrent class of is a pair of a sign and the set of labels joined by in both directions to a label with .✦ The set of signed recurrent classes of is (5)✦
Corners and Missing Classes
The corner of a diagram is the set of diagrams with and .✦ The surviving through relation of sign of a diagram relative to is the relation on formed as is, with the through relation of in place of that of : (6)✦
The loop of sign at a label survives in when . The missing set of relative to is the set of the signed recurrent classes of at none of whose labels the loop survives: (7)✦
The Claim
Theorem 1. Let and be boundary diagrams on labels and let be a sign. If is idempotent, then (8)✦ and (9)✦ Whether or not is idempotent, (10)✦ If lies in the corner of , then (11)✦ (12)✦ and (13)✦ If is idempotent and lies in the corner of , then for every signed recurrent class of and all labels and in , (14)✦ and (15)✦
In the paper, the result reads: for an idempotent , and , and , and , the recurrent classes of both signs number at most , the corner is , , the corner identities and hold together with absorption, and the missing set is well-defined on classes, where , and stand for , and with the sign dropped.
Each identity above holds for both signs, absorption is (12) together with (13), and the well-definedness of on classes is (14) together with (15).
What Is Checked
The claim is stated over boundary diagrams on labels and their product, idempotence and the corner of a diagram, the through relations , the loop closures with the reflexive transitive closure behind them, the recurrence relations , the signed recurrent classes , the surviving through relations and the missing set .