The Setting
Take a two-way nondeterministic finite automaton (2NFA) and a factor of its input. A run of may cross many times and in both directions, each time entering across its left or its right boundary in some state and leaving it across one of the two boundaries in some state. The four kinds of crossing give four relations, which together form a diagram. A word acts on the states of a one-way automaton by a single relation, the product of the relations of its letters, and acceptance is read off that relation. The question is whether a 2NFA admits the same description with diagrams in place of relations: a homomorphism from words to diagrams, and acceptance of a word read off one edge of its image flanked by two fixed diagrams.
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 .✦ To each state and each symbol , a letter of or one of the endmarkers and , assigns a set of pairs of a next state and a move to the left, in place or to the right.
The tape of a word over has cells , and its symbol in cell is for , for and the letter otherwise.✦ The step relation of on is the relation on configurations, the pairs of a state and a cell, given by (1)✦
The reflexive transitive closure of a relation on a set joins to when a chain of zero or more steps of leads from to .✦ The language of is the set of words on which a run from the initial state on the left endmarker reaches an accepting state: (2)✦
Diagrams
A diagram on labels is a quadruple of relations on two copies and of a label set with elements: the forward relation , the backward relation , the left relation and the right relation . The pairs in these relations are the edges of : a forward edge enters on the left and exits on the right, a backward edge enters on the right and exits on the left, and a left or right edge enters and exits on that side. The diagrams on labels form the set .
Relations compose in path order, when and for some . The product of diagrams , with on the left, is the diagram with (3)✦ The identity diagram on labels is the diagram in 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 single-cell diagram of three relations , and on , the moves to the left, in place and to the right inside one cell, is the diagram in with (4)✦
For a map , the word diagram of a word is the product of the diagrams of its letters: (5)✦
The Claim
Theorem 1. Let be a 2NFA with states over an alphabet . There are a map with and for all words and , diagrams and labels such that, for every word over , (6)✦
In the paper, the result reads: for an -state 2NFA over a finite alphabet , with for the page’s , there are a monoid homomorphism , endmarker diagrams and and labels with if and only if , and consequently implies for all words and whenever , each of the four relations of lying inside the corresponding relation of .
What Is Checked
The claim (6) is stated over a 2NFA with states, its step relation (1) on the tape with endmarkers and its language (2), and the diagrams on labels with the product (3) and the identity diagram .
Acceptance by has a second form, through an augmented machine. The augmented configurations of on a word of length are the pairs of a state of or a new state and a cell among , the cell lying to the right of ; each configuration of is one of them.✦ The augmented step relation of on is the relation on augmented configurations that joins to when , when with and , and when and .✦ For every word of length , (7)✦
A network on labels with vertex set consists of an edge relation on , left and right entrance relations and left and right exit relations .✦ Its summary is the diagram of its paths from an entrance to an exit: (8)✦
Let each letter carry three relations , and on , and take a word of length and a final letter . The chain network is the network on labels obtained by joining, from left to right, the single-cell networks of the letters of , where the single-cell network of a letter is the network whose summary is the single-cell diagram of its three relations; its vertices are copies of , one for each cell , and each vertex carries its cell and the letter in it, in cell and in cell .✦ The chain step relation on joins to , for a move , when , and for the letter in cell .✦ For all labels and , (9)✦