Two-way finite automata: exponential costs of determinism and complement

← All digests

Family 129 · Theoretical computer science
Importance 3/5 · Provisional editorial rating
Sources consulted 2026-10-09

1. The question

A finite automaton reads a string while remembering only one of finitely many internal states. Allowing it to reread the input seems powerful: perhaps repeated scans can replace a large amount of internal memory. Allowing nondeterministic choices is another resource: the machine can guess a successful path, and accepts if at least one finite computation succeeds.

How many states are needed to remove those guesses? And how many are needed to recognize the complementary language, accepting exactly the strings the original machine does not accept?

For two-way automata, these are distinct questions. A deterministic simulator removes nondeterminism; a complementing machine may remain nondeterministic. The present family claims exponential lower bounds for both tasks, even though the target can move its head freely in both directions.

The main qualification belongs at the beginning: the witness languages use finite alphabets that grow with the state parameter. The results rule out polynomial state bounds whose constants are independent of the alphabet. They do not establish the same lower bound over a single fixed alphabet, nor a separation of general logarithmic-space complexity classes.

2. Background and essential definitions

A deterministic finite automaton has at most one next move for each current state and scanned symbol. A nondeterministic automaton can have several. A one-way machine never moves left; a two-way machine can move left, right, or stay in place. Endmarkers bound the input.

The only mutable information is the finite state and head position. There is no work tape, writable input, extra head, random source, or advice. All states, including initial and accepting states, count toward the size.

Acceptance means reaching an accepting state in a finite computation. An infinite computation that never accepts does not accept. This convention is important for complementation: merely exchanging accepting and rejecting states does not necessarily handle nonhalting computations correctly.

The witness language uses binary relations on $H=\{1,\ldots,h\}$. A relation $R\subseteq H\times H$ specifies permitted moves between two successive layers. Relations compose in path order:

$$(a,c)\in AB \quad\Longleftrightarrow\quad \text{there exists }b\text{ with }(a,b)\in A \text{ and }(b,c)\in B.$$

Each relation is one alphabet symbol. A word $R_1\cdots R_\ell$ is called live when the product is nonempty. Equivalently, there is a path through all its layers, with any starting and ending point allowed. The empty word has the identity relation as its product and is live.

A small nondeterministic automaton guesses the current point and follows a permitted edge in each successive relation. Its state needs to remember only that point, plus a few control states. Certifying that no such path exists is a different task.

3. Development history and previous partial results

Rabin and Scott, and Shepherdson, established that two-way finite automata recognize the same regular languages as one-way automata. Equal expressive power does not mean equal succinctness: describing a language in one model can require many more states than describing it in another.

Sakoda and Sipser made this distinction central in their 1978 study of nondeterminism and two-way automata. Their relation-product family, now called one-way liveness, serves as a fundamental test problem for replacing one-way nondeterminism by two-way determinism.

Exponential lower bounds were known when the deterministic target’s motion was restricted. Sweeping machines can reverse direction only at the endmarkers; other results restrict the number of reversals. Those restrictions exclude the arbitrary interior reversals allowed here. Against unrestricted deterministic targets, earlier results gave polynomial lower bounds, including the quadratic one-way-liveness bound of Adeogun and Kapoutsis.

Complementation has its own history. Vardi gave an exponential-state construction for complementing a two-way nondeterministic automaton by a one-way nondeterministic one. Kapoutsis proved exponential lower bounds when the complementing target was sweeping. The new M1 claims a lower bound even when that target has unrestricted two-way motion.

Deterministic two-way complementation behaves better: Geffert, Mereghetti, and Pighizzini obtained a linear state overhead, including the necessary treatment of nonaccepting loops. Recent 1-limited-automaton work permits limited rewriting of input cells, a resource absent from the read-only model here. These results concern different combinations of memory and motion and should not be conflated.

4. What the new manuscripts claim

Complementation remains expensive even with nondeterminism

M1 constructs, for every $n\ge4$, an $n$-state two-way nondeterministic automaton recognizing liveness on $h=n-2$ points. Every two-way nondeterministic automaton recognizing its complement is claimed to require at least

$$\frac12\,2^{\lfloor(n-4)/127\rfloor}-1$$

states. The lower bound grows exponentially for sufficiently large $n$.

The alphabet consists of all binary relations on $n-2$ points and has size $2^{(n-2)^2}$. This is a state-complexity result, not an exponential lower bound in the total transition-table length.

Deterministic simulation has a separate exponential bound

M2 gives a one-way nondeterministic source with $h+3$ states. Every equivalent two-way deterministic automaton with $s$ states satisfies

$$4(s+2)^2\ge2^{\lfloor(h-2)/31\rfloor}.$$

This again forces $s=2^{\Omega(h)}$. A slightly improved additive constant is stated when acceptance in the initial configuration counts immediately. The displayed bound covers both conventions considered in the paper.

The target may use partial transition rules, stay moves, arbitrary reversals, and nonaccepting infinite computations. There is no bound on input length or on the time taken by a successful computation.

M1 also implies a deterministic lower bound through the linear-overhead complementation theorem: a small deterministic recognizer would have a small deterministic complement, contradicting M1. M2 supplies an independent diagram argument with a larger exponential rate. The two manuscripts therefore overlap in consequence but prove different primary statements.

5. Why the advance matters

Provisional importance: 3/5. These claims address foundational questions about the relative succinctness of finite-state models. They would show that unrestricted rescanning does not always compensate for nondeterministic choices when size is measured by states uniformly over finite alphabets.

The complementation claim is particularly informative because it leaves nondeterminism available to the target. The difficulty is not solely making one unique computation; it is representing the absence of every successful path with limited finite control.

The direct deterministic result also goes beyond lower bounds for sweeping or reversal-limited machines. It allows the target to use the full two-way read-only model, which is precisely where earlier restricted-motion arguments could not automatically apply.

The rating reflects a substantial contribution within automata theory, tempered by the growing-alphabet scope. The enormous alphabet carries significant information in each symbol, so describing the result only as an unrestricted exponential separation would conceal an essential feature of its parameterization.

6. The main idea

Replace a computation segment by its boundary behavior

When a head moves back and forth through an input segment, its internal history can be complicated. What matters to neighboring segments is how a computation can enter and leave through the two boundaries.

M1 records four relations: left-to-right traversals, right-to-left traversals, and returns to the same side. Joining two input segments composes these path diagrams. The operation is associative, so a whole word has a diagram obtained by multiplying its symbol diagrams.

Adding possible paths can only add accepting computations. By contrast, adding pairs to a relation product makes product emptiness less likely. Carefully chosen context letters test individual relation pairs, forcing a complementing automaton’s diagram representation to preserve this opposition between path availability and absence.

The algebraic argument studies recurrent boundary classes inside idempotent diagrams, where idempotent means that composing a diagram with itself leaves it unchanged. Adding relation information forces some recurrent structure to disappear. The manuscript bounds how that loss can move through contexts and how it accumulates along nested restrictions.

An amplification construction creates many relation additions sharing one budget of available boundary structure. Each addition demands further loss in a smaller instance. Comparing total available structure with the repeated demands yields an exponential recurrence.

Encode deterministic motion by matching diagrams

M2 uses a different representation. A matching diagram pairs ports on the two sides of a segment. Multiplication joins adjacent boundaries and follows the resulting paths, discarding closed components that do not reach an outside port.

Determinism allows the relevant accepting computation structure to be represented through a tree traversal. Auxiliary leaves for unused transition possibilities ensure that each cell’s diagram depends only on its own symbol, not on neighboring letters. This locality is necessary before symbol diagrams can be composed consistently.

For an $s$-state target, the manuscript constructs diagrams with at most $4(s+2)^2$ ports on each side. Contexts that test individual relation pairs then force the generated diagram system to map onto the full relation-product system while preserving composition.

The remaining lower bound is algebraic. The rank of a matching diagram counts pairs connecting opposite sides. A sequence of relation additions forces repeated rank losses inside smaller idempotent regions. A shared support bound limits how much rank can be lost at once; induction makes the required number of ports double after a fixed increase in $h$.

The diagrams are analytical encodings, not extra memory granted to the automaton. Their purpose is to expose a resource that every small target would have to possess, then show that too many such resources are required.

7. Scope, limitations, and open questions

The alphabet size grows as $2^{h^2}$. A theorem ruling out a polynomial bound independent of the alphabet does not by itself rule out a polynomial bound with constants depending on a fixed alphabet. Encoding the relation symbols into binary can alter state costs, so a fixed-alphabet conclusion requires a separate argument.

Likewise, counting states differs from counting the full transition table. A machine with few states and a huge alphabet can have an enormous explicit description. The claimed exponential lower bounds are parameterized by states in the source model.

The results compare finite-state devices without a work tape. They do not separate deterministic and nondeterministic logarithmic-space computation on general encoded inputs. Input length and computation time are unrestricted within the finite-automaton model.

The fixed-alphabet frontier, sharper quantitative tradeoffs involving alphabet size, and other combinations of writable memory and head motion remain distinct questions. The digest reports the two stated diagram lower bounds without auditing their algebraic proofs.

8. Sources and further reading

Sakoda–Sipser supplies the original succinctness problem and witness family. The linked quadratic lower bound, deterministic complementation theorem, and limited-rewriting result locate the new claims among earlier partial solutions. M1 below concerns nondeterministic complementation; M2 concerns deterministic simulation directly.

Source manuscripts

• M1. OpenAI, An exponential state lower bound for two-way nondeterministic complementation (September 25, 2026).
• M2. OpenAI, An exponential two-way deterministic state lower bound for one-way liveness (September 25, 2026).

Sources consulted on 9 October 2026 at repository revision fd4aeeb. Download the manuscript citations.