The Setting
A two-way automaton reading a block of its tape can cross the block in either direction, or enter it and come back out at the end it came in by. A boundary diagram records how these passages connect labels at the two ends of the block, with one copy of the labels for passages moving right and one for passages moving left, and gluing two blocks side by side multiplies their diagrams.
The item compares two boundary diagrams and , with nested in (the product with on either side leaves unchanged), through two relations on one copy of the labels: the loop closure, which closes up returns at the two ends taken alternately, and the recurrent relation, a crossing preceded and followed by such returns. The question is whether the loop closure of lies in that of , and whether the recurrent relation of absorbs the recurrent relation and the crossings of composed with it on either side.
Boundary Diagrams
Relations compose in path order: when and for some . The reflexive transitive closure of a relation on a set is the relation on , where is the identity relation on and .✦
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 is the diagram obtained by gluing to the left of : (1)✦
A diagram is nested in a diagram , written , when the product with on either side leaves unchanged: (2)✦ The corner of is the set of diagrams nested in .✦
Relations at a Sign
A sign is or . The through relation of a diagram at a sign is the relation on of its traversals in the direction of : the forward relation and the backward relation .✦
The loop closure of at is the relation on given by (3)✦
The recurrent relation of a diagram at a sign is the relation on obtained by closing the through relation of at with the loop closure of at on both sides: (4)✦
The Claim
Theorem 1. Let and be boundary diagrams on labels with , and let be a sign. Then (5)✦ (6)✦ and (7)✦
In the paper, the result reads: for idempotents and either sign, , and , and in the positive sign and , with in place of for the negative sign, and being written there without their sign.
The statement asks of and only that , and so covers nested idempotents.
What Is Checked
The claim is stated over boundary diagrams on labels, their product (1) with the reflexive transitive closure in it, the nesting (2), and the through relation, the loop closure (3) and the recurrent relation (4) of a diagram at a sign.