The Setting
A two-way automaton working on a factor of its input may cross the factor from left to right, cross it from right to left, or enter it and turn back to the side it came from. A boundary diagram records such crossings between labels on each side of a block, and blocks placed side by side multiply. The item is an order on the idempotent diagrams that compares them through this product alone, much as an idempotent of a finite monoid is compared with an idempotent by asking whether lies in the corner .
Diagrams and Their Product
Relations compose in path order: when and for some , and is the identity relation on a set . The reflexive transitive closure of a relation on is the relation on given by (1)✦
A boundary diagram on labels is a quadruple of relations on two copies and of an -element label set, (2)✦ 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 boundary diagrams is the boundary diagram obtained by gluing to the left of , with relations (3)✦ A boundary diagram is idempotent when .
The Claim
Definition 1. Let be a natural number. Nesting is the relation on in which a diagram is nested in a diagram , written , when and are idempotent and (4)✦ Nesting is reflexive on idempotents: if is idempotent, then (5)✦ Nesting is transitive: if satisfy and , then (6)✦
In the paper, the result reads: for idempotent diagrams and , if and only if , and is a partial order, distinct from the componentwise edge inclusion of diagrams.
What Is Checked
The claim is stated over the boundary diagrams (2) on labels, their product (3), built with the reflexive transitive closure (1), and the nesting relation (4).