OctoInformBeta

Exponential state costs for two-way automata

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 pp such that every 2NFA with nn states over any finite alphabet has a 2NFA with at most p(n)p(n) states recognizing the complementary language. For a finite set HH, ℛH\mathcal R_H is the monoid of all binary relations on HH, multiplied in path order, so that (p,r)∈AB(p,r)\in AB when (p,q)∈A(p,q)\in A and (q,r)∈B(q,r)\in B for some qq, with identity IH={(p,p):p∈H}I_H=\{(p,p):p\in H\}. Over the alphabet ΣH=ℛH\Sigma_H=\mathcal R_H, the relation product of a word w=R1⋯Rkw=R_1\cdots R_k is r(w)=R1⋯Rkr(w)=R_1\cdots R_k, with r(ε)=IHr(\varepsilon)=I_H for the empty word. The relation-product liveness language is LH={w∈ΣH*:r(w)≠⌀}L_H=\{w\in\Sigma_H^*:r(w)\neq\varnothing\}.

Sakoda and Sipser initiated the state-succinctness problem of simulating 2NFAs deterministically. For nonempty words, LHL_H is their family BhB_h, where h=|H|h=|H|. 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 n≥4n\ge4, with H={1,…,n−2}H=\{1,\ldots,n-2\} and Σn=ℛH\Sigma_n=\mathcal R_H, there is an nn-state 2NFA AnA_n recognizing LHL_H such that every 2NFA recognizing Σn*\L(An)\Sigma_n^*\setminus L(A_n) has at least 122⌊(n−4)/127⌋−1\tfrac12\,2^{\lfloor(n-4)/127\rfloor}-1 states. In particular, the preprint answers the complementation problem negatively. It deduces that there are absolute constants c>0c>0 and n0n_0 such that, for every n≥n0n\ge n_0, every 2DFA recognizing L(An)L(A_n) has at least c2⌊(n−4)/127⌋c\,2^{\lfloor(n-4)/127\rfloor} states. For m≥1m\ge1, a partitioned binary relation of degree mm is a binary relation on the 2m2m points 1,…,m,1′,…,m′1,\ldots,m,1',\ldots,m', read as a directed graph whose edges are its pairs. The product abab of two partitioned binary relations of degree mm places aa above bb, with the primed points of aa identified with the unprimed points of bb, and has an edge from xx to yy, for xx and yy among the unprimed points of aa and the primed points of bb, when a directed path of edges of aa and bb, switching from one factor to the other at each identified point, leads from xx to yy. 𝒯m\mathcal T_m is the monoid of partitioned binary relations of degree mm under this product. Martin and Mazorchuk introduced this monoid. The preprint calls the elements of 𝒯m\mathcal T_m path diagrams on mm labels. Edge inclusion a⊑ba\sqsubseteq b between path diagrams holds when every edge of aa is an edge of bb. The preprint also proves that if a submonoid of 𝒯m\mathcal T_m maps multiplicatively onto ℛH\mathcal R_H, with |H|=h≥2|H|=h\ge2, by a map ϕ\phi such that a⊑ba\sqsubseteq b implies ϕ(b)⊆ϕ(a)\phi(b)\subseteq\phi(a), then 2m≥2⌊(h−2)/127⌋2m\ge2^{\lfloor(h-2)/127\rfloor}.

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 L(An)L(A_n) with c=12c=\tfrac12 and n0=131n_0=131. The preprint is a guide only: it gives the results their order and their names.

The Lean library: Automata

Automata is a Lean library: 24 items, in five groups. Each has a page written by OctoInform, listed below.

§1. Introduction 2 items
  1. §1 (setting): the 2NFA model and the relation-product liveness language Two-way automata and a language of binary relations. §1
  2. Theorem 1.1 [Main theorem] Complementing two-way nondeterministic automata can need exponentially many states. §1
§2. Path diagrams and missing recurrent classes 8 items
  1. §2.1 (setting): the diagram monoid 𝒯_m and edge inclusion Boundary diagrams on mm labels form a monoid. §2.1
  2. Theorem 2.1 [Order-reversing image bound] Order-reversing homomorphisms from diagrams onto relations need exponentially many labels. §2
  3. Lemma 2.2 [Diagram representation of a 2NFA] Acceptance by a two-way automaton through a homomorphism to diagrams. §2
  4. Proposition 2.3 [Order reversal from complementation] Recognizing the complement reverses inclusion of diagrams. §2
  5. §2.3 (setting): recurrent classes, corners and missing sets Recurrent classes of an idempotent diagram and its missing sets. §2.3
  6. Lemma 2.4 [Products of missing sets] Products in an idempotent’s corner lose no new recurrent classes. §2
  7. Lemma 2.5 [Rectangles of through edges] Through edges of an idempotent diagram ee come in rectangles. §2
  8. Lemma 2.6 [Transport] Missing recurrent classes pass through a context at most doubled. §2
§3. A loss budget for nested idempotents 4 items
  1. §3 (setting): nesting Nesting of idempotent diagrams is reflexive and transitive. §3
  2. Lemma 3.1 [Absorption under nesting] A nested diagram’s recurrent relation absorbs the outer diagram’s. §3
  3. Lemma 3.2 [Containment of recurrent classes] Recurrent classes of a nested idempotent contain outer classes. §3
  4. Proposition 3.3 [Chain bound] A chain of nested idempotents loses at most twice its budget. §3
§4. An exponential bound for order-reversing images 6 items
  1. Lemma 4.1 [Minimal idempotent corners] Corners at minimal idempotent lifts in finite semigroups reflect units. §4
  2. Lemma 4.2 [Restriction of a relation corner] Corners of a relation monoid that are full relation monoids. §4
  3. §4.2 (setting): the target bound D(h) The exponential target bound and its doubling step. §4.2
  4. Proposition 4.3 [Cost of one added pair] One pair added to the identity costs exponentially many classes. §4
  5. §4.2 (proof of Proposition 4.3): base case, Steps 1 to 3 Base case and inductive steps of the missing-class bound. §4.2
  6. §4 (proof of Theorem 2.1) Order-reversing homomorphisms from diagrams onto all relations need many labels. §4
§5. Finite computations and the main lower bound 4 items
  1. Lemma 5.1 [The source automaton] A two-way automaton with |H|+2|H|+2 states for nonempty relation products. §5
  2. §5.2 (proof of Lemma 2.2): finite computations as diagram paths Acceptance of a two-way automaton read off boundary diagrams. §5.2
  3. §5 (proof of Theorem 1.1) Complementing a two-way automaton can cost exponentially many states. §5
  4. Corollary 5.3 [Determinization] No polynomial bound determinizes two-way automata over all alphabets. §5

No item matches.