The Setting
Cut the tape of a two-way automaton around a factor. A run segment inside the factor enters across one of its two boundaries and leaves across one, and the rest of the tape sees the factor only through which crossings such segments join. A boundary diagram on labels keeps this record on two copies and of an -element label set, with a label in for a crossing to the right and a label in for a crossing to the left; the diagrams of two adjacent factors multiply by gluing.
Fix an idempotent diagram . Its signed recurrent classes, defined below, are sets of labels that its recurrence relation, also defined below, ties into loops, and replacing by a diagram of its corner, the set of diagrams nested in , can lose every loop of a class, which is then missing at . Put in a context: diagrams and with idempotent as well, so that replacing by turns into . The question is how the classes of missing at are controlled by those of missing at , uniformly in . For a set of classes of , the theorem below answers it by a set of at most classes of , and it also gives a containment in, and a size bound for, an explicit set of classes of marked by , defined below.
Diagrams and Recurrent Classes
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 .
Relations compose in path order, when and for some , and the reflexive transitive closure of a relation on a set is , with the identity relation on . The product of is the diagram obtained by gluing to the left of : (1)✦
A diagram is idempotent when . A diagram is nested in , written , when , and the corner of is the set of diagrams nested in , written when is idempotent.✦
A sign is or , and is the opposite sign. At a sign , the through relation of a diagram is its traversal in the direction of ✦, and its loop closure closes up the alternating returns at a boundary; both are relations on : (2)✦ The recurrence relation of and the surviving relation of a diagram relative to place the loop closure of on both sides of a through relation: (3)
The set of signed recurrent classes of consists of the pairs of a sign and a set of labels for which some label with has . For a diagram , the set of classes of missing at holds the classes whose loops are all lost when is replaced by : (4)✦
The Marked Classes
Fix diagrams , , and in . A port is a pair of a sign and a label. The port relation of relates the port to the port when lies in , , or according as is , , or : it reads as one relation from entry ports to exit ports, with the negative ports on its left boundary and the positive ones on its right.✦
For relations and on the labels, the bounce relation on ports keeps the sign and moves the label by at a positive port and by at a negative one.✦ Write ; a step of is a return into off on the right of or off on the left of .
The recurrent rectangle of at a label and a sign is the relation on labels (5) The class rectangle of a pair of a sign and a set of labels relates the port to the port when for some .✦
At a sign , the context entry relation , from labels to ports, and the context exit relation , from ports to labels, pass through the loop closure of and a traversal of or : (6) The class influence relation of a pair at is the relation on labels following a path from the context through and back, with any number of returns off and on either side of : (7)✦
The set of classes of marked by a set of pairs of a sign and a set of labels consists of the classes of with a label on a loop of the class influence relation at of some pair of : (8)✦
The Claim
Theorem 1. Let and be idempotent diagrams in , and let and be diagrams with .
(i) For every set there is a set with such that every with and satisfies (9)✦
(ii) For every set of pairs of a sign and a set of labels, every with satisfies (10)✦
(iii) For every set , (11)✦
In the paper, the result reads: for idempotents and and diagrams and with , every has a single with such that for every with and .
What Is Checked
The claim is stated over boundary diagrams on labels with the gluing product (1), the idempotents and corners of that product, the recurrent classes and the missing classes (4) built from the relations (3), and the marked classes (8) built from the class influence relations (7).