The Setting
Let be a two-way nondeterministic finite automaton (2NFA) with states. How many states must a 2NFA have whose language is the complement of the language of , and can that number be forced to grow exponentially in ? The automata here read words over the alphabet of binary relations on a finite set , and such a word multiplies out, letter by letter, to a single relation on .
The same question is asked of boundary diagrams, which record the paths that enter and leave a block from its left or right side. Diagrams on labels are assigned to the words over so that concatenation of words becomes the product of diagrams, and one pair of labels is to detect the words that multiply out to the empty relation: how large must be? A third statement concerns renaming the states of a 2NFA along a bijection.
Two-way Automata
A 2NFA over an alphabet with state set consists of an initial state , a set of accepting states and a transition function , which assigns to each state and each tape symbol , a letter of or one of two distinct endmarkers and outside , a set of pairs of a next state and a head move, with , and standing for left, stay and right.✦
On a word over the tape has cells , and cell holds the symbol (1)✦ so that the empty word is read as . A configuration of on is a pair of a state and a cell. The one-step relation of on relates to when, for some move , (2)✦ with again a cell of the tape.
The reflexive transitive closure of a relation on a set is the relation on that relates to when there is a chain , with , whose consecutive pairs lie in .✦ The language of is the set of words over on which a run of any length, zero included, leads from the initial state on the left endmarker to an accepting state: (3)✦
The renaming of a 2NFA along a bijection is the 2NFA over with state set , initial state , accepting states and transition function (4)✦
Relations and Boundary Diagrams
Relations compose in path order: when and for some . The relation product of a word over is the product of its letters in , and , the identity relation on .✦
A boundary diagram on labels is a quadruple of relations on two copies and of an -element set of labels: 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.✦ These diagrams form the set .
The product of diagrams is the diagram obtained by gluing to the left of , with relations composed in path order: (5)✦ The identity diagram is the diagram with forward relation , backward relation , and empty left and right relations.✦
The loss bound of a natural number is (6)✦
The Claim
Theorem 1. Let and . There is a 2NFA over with states such that every 2NFA over with states and satisfies (7)✦
Theorem 2. Let and , let be a set with elements, and let map the words over to diagrams in so that and for all words and . Suppose that for some diagrams and labels , every word over has if and only if . Then (8)✦
Theorem 3. Let be a 2NFA over with state set , and let be a bijection. Then (9)✦
What Is Checked
The three claims are stated over the 2NFA with its tape between endmarkers (1), its one-step relation (2) and its language (3) through the reflexive transitive closure, the renaming of states (4), the relation product on words over , the boundary diagrams in with their product (5) and the identity , and the loss bound (6).