The Setting
Let be a set. The relation monoid of is the monoid of binary relations on under the path-order product (1)✦ with unit the identity relation . For a subset of , the restricted identity is the relation on .✦
Let be the alphabet whose letters are the binary relations on . The relation product of a word over is the relation on , the path-order product of its letters, with .✦ The language consists of the words whose relation product is nonempty, and its complement of the words with .
Proposition 2.3 concerns two-way nondeterministic finite automata (2NFA) that recognize for a finite , and the number of states they need. It works with diagrams, which record how a two-way automaton traverses a block of its tape, entering it from the left or the right and leaving it on the left or the right.
For a natural number , the loss bound is the power of two (2)✦
Diagrams
Let and be two copies of an -element set of labels. A diagram on labels is a quadruple of relations: the forward relation , the backward relation , the left relation and the right relation .✦ The pairs in these relations are the edges of . An edge of enters on the left and exits on the right, an edge of enters on the right and exits on the left, an edge of enters and exits on the left, and an edge of enters and exits on the right.
The reflexive transitive closure of a relation on a set is the relation on that relates to when there is a chain with and for each .✦ The product of diagrams and on labels is the diagram on labels with (3)✦ where relations compose in path order. The identity diagram on labels is the diagram whose forward relation is the identity relation on , whose backward relation is the identity relation on , and whose left and right relations are empty.✦ The monoid is the set of diagrams on labels under this product, with unit .
Edge inclusion is the relation on that holds at when each relation of is contained in the corresponding relation of : (4)✦
Recognizers
A diagram recognizer of on labels is a map with for all words and , together with diagrams and labels and , such that for every word over (5)
The Claim
Theorem 1. Let be a set.
For every word over and all , (6)✦
Let be a natural number and let , , , , be a diagram recognizer of on labels. For all words and over with , (7)✦
If moreover , there are a submonoid of and a surjective monoid homomorphism such that for all (8)✦
If moreover , and has elements, then (9)✦
In the paper, the result reads: if is finite with at least two elements and an -state 2NFA recognizes , then a submonoid of admits a surjective unital homomorphism onto with implying .
The box states this for a diagram recognizer on labels in place of the automaton, with in the role of .
What Is Checked
The claim is stated over the relation monoid with relation products of words and restricted identities, the monoid of diagrams with the product (3), the identity diagram and edge inclusion (4), diagram recognizers (5) and the loss bound (2).