The Setting
A nondeterministic automaton with state set sends each word to the relation on of pairs of states joined by a run on it, and concatenation of words becomes the path-order product of relations, in which when and for some . The relation monoid of a set is the monoid of all binary relations on under this product, with the identity relation as its unit.✦
The head of a two-way automaton can enter a block of tape from either side and leave it through either side, so what a block does is described by a boundary diagram rather than by a relation. The question is how many labels it takes for a set of boundary diagrams, closed under the product of diagrams defined below, to map onto all of multiplicatively and so that adding edges to a diagram can only shrink its image. The library answers it with a lower bound on the number of labels in terms of , and states beside it four facts on idempotents and corners.
Diagrams and the Loss Bound
A boundary diagram on labels is a quadruple of relations on two copies and of an -element set of labels: the forward relation , from entry on the left to exit on the right; the backward relation , from entry on the right to exit on the left; the left relation , from entry on the left back to exit on the left; and the right relation , from entry on the right back to exit on the right.✦ The set of boundary diagrams on labels is .
For a relation on a set , the reflexive transitive closure is the relation on joining to when a chain of steps in , possibly empty, leads from to .✦ The product of diagrams is the diagram obtained by gluing to the left of : (1)✦
The identity diagram is the diagram with forward relation , backward relation , and empty left and right relations.✦
Edge inclusion is the order on in which when , , and .✦
The loss bound of a natural number is the number (2)✦
Idempotents and Corners
Theorem 1. Let be a finite monoid and . Then there is an integer for which is idempotent: (3)✦
Theorem 2. Let be a finite semigroup, a monoid, and a surjective map with for all . Then there are an idempotent of and a monoid homomorphism from the corner , a monoid with identity , to such that (4)✦ where and are the groups of units.
Theorem 3. Let be a set and . Then the relation is an idempotent of : (5)✦
The corner of a diagram is the set of diagrams that leaves unchanged on either side: (6)✦
Theorem 4. Let be a monoid with identity , and let be a map with for all . Then every satisfies (7)✦
The Claim
Theorem 5. Let , let be a finite set with , and let be a set of diagrams that contains and is closed under the product. Let be a surjective map that is multiplicative, for all , and order-reversing, for all with . Then (8)✦
What Is Checked
The bound (8) is stated over the boundary diagrams on labels with their product (1), the identity diagram and edge inclusion , over the relation monoid of a finite set , and over the loss bound (2); the facts (3) and (4) are stated over every finite monoid and every finite semigroup. About the relations and the diagrams themselves, the library states (5) in and (7) on the corner (6) of a diagram.