The Setting
A run of a two-way automaton meets a factor of its input in four ways: it crosses the factor from left to right or from right to left, or it enters and leaves on the same side. Boundary diagrams record these passages as relations on labels and multiply by gluing side by side, as the relations of a one-way automaton, the path-order product of the relations of the letters of a word , multiply along the word. Each diagram has recurrent classes, sets of labels that its passages join into loops, each class signed by the direction of travel. The item takes two idempotent diagrams and , with nested in , and asks which classes of lie inside each class of , given the classes of that go missing when is replaced by .
Boundary Diagrams
Relations compose in path order: when and for some . The reflexive transitive closure of a relation on a set is the union of its powers , , where is the identity relation on .✦
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 boundary diagram obtained by gluing to the left of : (1)✦ An idempotent diagram is a diagram with .
The corner of a diagram is the set of diagrams with and ; a diagram in the corner of is nested in , written .✦
Recurrent and Missing Classes
A sign is or , and is the copy of the labels it names. The through relation of a diagram at a sign is the relation on of its traversals in the direction of .✦ The loop closure of at is the relation on that closes up the alternating left and right returns at a boundary: (2)✦
The recurrence relation of a diagram at a sign is the relation on obtained by closing the through relation of with its loop closure on both sides: (3)✦ The set of signed recurrent classes of is the set of pairs of a sign and a set of labels given by (4)✦
The surviving relation of a diagram relative to at a sign is the relation on obtained by placing the loop closure of on both sides of the through relation of .✦ The set of classes of missing from is the set of signed recurrent classes of whose loops are all lost when is replaced by : (5)✦
The Claim
Theorem 1 (Containment of recurrent classes). Let and be idempotent boundary diagrams on labels with , and let be a signed recurrent class of . Then at least one of the following holds: (6)✦
In the paper, the result reads: for idempotents , every class of contains either a whole class of or two distinct whole classes of , all classes involved having the same sign.
What Is Checked
The claim (6) is stated over boundary diagrams on labels, their product (1) and the corner of a diagram, the through relation and the loop closure (2), the recurrence relation (3) and the signed recurrent classes (4) it defines, and the surviving relation and the classes missing from a diagram (5).