The Setting
Take a two-way nondeterministic finite automaton (2NFA) and an input word. A run moves the head back and forth over the marked tape, so a stretch of the tape meets the run only where it crosses the two ends of the stretch, in either direction and in some state. The result below is Lemma 2.2 of the OpenAI preprint on an exponential state lower bound for two-way nondeterministic complementation. It reads the finite computations of the automaton as paths through records of such crossings, one cell at a time, and the question is how acceptance of a word is read off at the two ends of its tape.
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 that assigns to each state and each tape symbol (a letter of or one of the endmarkers and ) a set of pairs of a next state and a move : left (), stay () or right ().✦
The tape of a word has cells , and the tape symbol at cell is for , for and otherwise.✦ The one-step relation of on is the relation on configurations, the pairs of a state and a cell, with when for the tape symbol at cell and is again a cell.✦
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 language of is the set of words over with for some accepting state and some cell , a run of length zero included.✦
Boundary Diagrams
Fix a label set of elements and two copies and of it. A boundary diagram is a quadruple of relations: the forward relation , entering on the left and exiting on the right; the backward relation , entering on the right and exiting on the left; the left relation , entering and exiting on the left; and the right relation , entering and exiting on the right.✦
The product of diagrams is the diagram of glued to the left of : (1)✦ The identity diagram has forward relation , backward relation , and empty left and right relations.✦
Path Networks and Chains
A finite-path network on a vertex set with labels consists of an edge relation on and four boundary relations: left and right entrances , relating a label to the vertices it enters at on that side, and left and right exits , relating a vertex to the labels by which it leaves on that side.✦ The summary diagram of records which boundary labels a finite internal path joins: (2)✦
The join of on , placed to the left of a network on , is the network on with the left entrances and exits of , the right entrances and exits of , and as edge relation the block relation whose restrictions to , , and are (3)✦
A move assignment on an alphabet and the label set assigns to each letter and each move a relation on . For a word over with a final letter , the chain of and has cells, and its chain vertices are disjoint copies of , one for each cell.✦ The cell coordinate of a chain vertex is the index of its cell✦, and the symbol at the vertex is the letter of that cell, for and for ✦. The chain step relation is the relation on pairs of a label and a position with when is the cell coordinate of a chain vertex with symbol and ; no step leaves the terminal position .✦
The Claim
Definition 1. Let be a fresh state and . For a word of length , the augmented configuration of a configuration of is the same pair in , whose last position lies past the right endmarker.✦ The augmented step relation of on is the relation on consisting of the pairs (4)✦ The augmented move relation of at a tape symbol and a move is the relation on given by (5)✦ and it never relates to a state of .
The single-cell diagram of three relations , and on , the left, stay and right moves of one cell, records the paths that enter the cell from either side, stay finitely often and leave by one move to the left or the right: (6)✦
The single-cell network of a letter is the finite-path network on one cell given by the relations , and on . The chain network of a word over with final letter is the finite-path network on the chain vertices of and built by recursion on from the single-cell networks of its letters, where is a letter and a word over : (7)✦
Theorem 1.
Let be a 2NFA over and a word over of length . Then (8)✦
Let and be finite-path networks on and on with labels. Then (9)✦
Let be a move assignment on and , let be a word over of length with final letter , and let . Then (10)✦
Let be a 2NFA over with states. Then there are a map from words over to , diagrams and labels and such that, for all words , and over , (11)✦
What Is Checked
The theorem is stated over a 2NFA with its tape symbols, one-step relation and language, the augmented configurations and the augmented step relation (4), boundary diagrams with their product (1) and the identity diagram, finite-path networks with their summary diagram (2) and join (3), and a move assignment with its chain step relation and chain network (7).