The Setting
Let be a two-way nondeterministic finite automaton (2NFA) with states over a finite alphabet , reading its input between a left and a right endmarker. How many states does a 2NFA need to recognize the complement , as a function of ? In particular, is there a polynomial such that every -state 2NFA, over any finite alphabet, has a 2NFA with at most states for its complement?
The library answers with a family of witnesses over alphabets that grow with : for each , a 2NFA with states over the alphabet of binary relations on a set of points, and a lower bound on the number of states of every 2NFA over that alphabet that recognizes the complement of its language.
Two-way Automata
A two-way nondeterministic finite automaton over an alphabet , with a set of states, consists of an initial state , a set of accepting states and a transition function that assigns to each state and each tape symbol , where is the left endmarker and the right endmarker, a set of pairs of a next state and a head move, left, stay or right.✦
On an input the tape has the cells , and the tape symbol at cell is (1)✦
A configuration of on is a pair of a state and a cell of the tape. The one-step relation of on is the relation on configurations given by (2)✦ and its reflexive transitive closure relates a configuration to a configuration when there is a run of some length .
The language recognized by consists of the words on which a run from the initial configuration reaches an accepting state: (3)✦
Relations as Letters
For a set , the relation monoid is the monoid of binary relations on under the path-order product, in which, for relations on , when and for some , with the identity relation as its unit.
For a word over the alphabet , the relation product is the element of (4)✦ The language over is the set of words whose relation product is nonempty: (5)✦
The Claim
Theorem 1. Let be the alphabet with .
For every there is a 2NFA over with states such that, for every 2NFA over with a finite set of states that recognizes , both of the following hold: (6)✦
For every there is a 2NFA over with states such that every 2NFA over with states that recognizes satisfies (7)✦
For every there is a 2NFA over with states such that every 2NFA over with a finite set of states that recognizes satisfies (8)✦
For every polynomial with real coefficients there are natural numbers and and a 2NFA with states over the alphabet such that every 2NFA over with states that recognizes satisfies (9)✦
In the paper, the result reads: for every integer , with and , there is an -state 2NFA recognizing such that every 2NFA recognizing has at least states, and in particular there is no polynomial state bound for complementation that is independent of the finite alphabet.
What Is Checked
The four claims are stated over two-way nondeterministic automata with endmarkers and their languages (3), defined by runs of the one-step relation (2) on the tape (1): (6), (7) and (8) over the alphabet , (6) also over the language of (5) and the relation product (4), and (9) over the alphabets .