The Setting
Take a two-way nondeterministic finite automaton (2NFA) with states. The question is how many states a two-way deterministic finite automaton (2DFA) needs to recognize the same language, and whether a polynomial in always suffices when the alphabet may grow with . The witnesses here are languages whose letters are the binary relations on a finite set.
Two-way Automata
Let be an alphabet and let and be two endmarkers outside it. For a word over , the tape has cells , and the tape symbol at cell is for , for and the letter otherwise.✦
A 2NFA over 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 set of pairs of a next state and a head move, , and standing for left, stay and right.✦
A configuration of on is a pair of a state and a cell✦, and the one-step relation on configurations is (1)✦ The language of is the set of words on which some configuration with an accepting state is reachable from under the reflexive transitive closure , by a run of zero or more steps: (2)✦
A 2DFA over with state set is a 2NFA over with state set in which every set has at most one element.✦
Words of Relations
Write for a set with elements. For a finite set , is the monoid of binary relations on under the path-order product, in which when and for some , with identity . The relation product of a word over the alphabet is , with .✦ The language over is the set of words whose relation product relates at least one pair of points of : (3)✦
The Claim
Theorem 1 (Determinization). (a) Let and . There is a 2NFA over with states such that and every 2NFA over with a finite state set that recognizes the complement has (4)✦ (b) If moreover , every 2DFA over with a finite state set that recognizes , which is , has (5)✦ (c) For every polynomial with real coefficients there are natural numbers and and a 2NFA with states over a -letter alphabet such that every 2DFA with states recognizing has (6)✦
In the paper, the result reads: there are absolute constants and such that for every every 2DFA recognizing has at least states, and hence no polynomial state bound independent of the finite alphabet can determinize all 2NFAs.
The theorem takes and .
What Is Checked
The theorem is stated over 2NFAs and 2DFAs with finite state sets, their languages (2) under the one-step relation (1), and the language of (3) over the alphabet of binary relations on .
One-way Liveness
The one-way liveness language is the set of live words over the alphabet of binary relations on ✦, a word being live when its relation product, as in (3), is nonempty.✦
A nondeterministic automaton with states over consists of an initial state, a set of accepting states and a transition function that assigns to each state and each scanned symbol, a letter of or an endmarker, a set of pairs of a next state and a move , with no move left on and no move right on .✦ A deterministic automaton with states over is a nondeterministic automaton with states over whose transition function gives, for each state and each scanned symbol, at most one pair of a next state and a move.✦ A nondeterministic automaton is one-way when none of its transitions moves the head left.✦
Configurations and steps of an automaton on a word are as in (1), with the head move. An automaton accepts a word by a nonempty run when a run of at least one step leads from the left endmarker in the initial state to a configuration with an accepting state, and accepts by a run of any length when a run of zero or more steps does, as in (2). Under either convention, an automaton recognizes a language over when the words it accepts are exactly the words of .
For one-way liveness the library proves, for , that some one-way nondeterministic automaton with states recognizes under both conventions, and that every deterministic automaton with states recognizing under either convention satisfies (7)✦ where for acceptance by a nonempty run and for acceptance by a run of any length.
The 2DFAs of the theorem obey a bound of the same shape: if , every 2DFA with states over that recognizes satisfies (8)✦
The exponents and are tied by an inequality of numbers: if and is a natural number with , then (9)✦