A two-way nondeterministic finite automaton (2NFA) reads its input between a left and a right endmarker with one read-only head, which starts on the left endmarker and at each step moves left, moves right or stays. It accepts when some finite computation reaches an accepting state, the initial configuration included. A 2NFA is a two-way deterministic finite automaton (2DFA) when each state and scanned symbol allow at most one move. The complementation problem asks whether there is one polynomial such that every 2NFA with states over any finite alphabet has a 2NFA with at most states recognizing the complementary language. For a finite set , is the monoid of all binary relations on , multiplied in path order, so that when and for some , with identity . Over the alphabet , the relation product of a word is , with for the empty word. The relation-product liveness language is .
Sakoda and Sipser initiated the state-succinctness problem of simulating 2NFAs deterministically. For nonempty words, is their family , where . Kapoutsis uses the name one-way liveness for this family. Vardi constructed, for the complement of any 2NFA, a one-way nondeterministic automaton with exponentially many states. A 2NFA is sweeping when its head reverses direction only at the endmarkers. Kapoutsis proved that every sweeping 2NFA recognizing the complement of one-way liveness has exponentially many states. Geffert, Mereghetti and Pighizzini proved that 2DFAs can be complemented with a linear number of states, independently of the alphabet. Guillon, Prigioniero and Taheri describe polynomial complementation of 2NFAs as open. A 1-limited automaton is an automaton that may, unlike a 2NFA, rewrite each tape cell on its first visit. The same authors give polynomial complementation of 2NFAs by 1-limited automata.
The preprint proves that for every , with and , there is an -state 2NFA recognizing such that every 2NFA recognizing has at least states. In particular, the preprint answers the complementation problem negatively. It deduces that there are absolute constants and such that, for every , every 2DFA recognizing has at least states. For , a partitioned binary relation of degree is a binary relation on the points , read as a directed graph whose edges are its pairs. The product of two partitioned binary relations of degree places above , with the primed points of identified with the unprimed points of , and has an edge from to , for and among the unprimed points of and the primed points of , when a directed path of edges of and , switching from one factor to the other at each identified point, leads from to . is the monoid of partitioned binary relations of degree under this product. Martin and Mazorchuk introduced this monoid. The preprint calls the elements of path diagrams on labels. Edge inclusion between path diagrams holds when every edge of is an edge of . The preprint also proves that if a submonoid of maps multiplicatively onto , with , by a map such that implies , then .
The Lean library Automata proves each of these results. Lean has checked every result of the Lean library, so the Lean library is the reference. Each result on these pages is stated as the Lean library states it and linked to the Lean declaration behind it. Where the preprint states a result differently, the page gives the Lean library’s statement, with the preprint’s beside it. The Lean library proves the bound on 2DFAs recognizing with and . The preprint is a guide only: it gives the results their order and their names.
Automata is a Lean library: 24 items, in five groups. Each has a page written by OctoInform, listed below.
No item matches.