OctoInformBeta

OpenAI preprint, September 2026 · §5. Finite computations and the main lower bound · §5

Corollary 5.3 [Determinization]: A two-way deterministic automaton for words of relations on n−2n-2 points with nonempty product needs 2⌊(n−4)/127⌋/22^{\lfloor (n-4)/127 \rfloor}/2 states once n≥131n \ge 131

No polynomial bound determinizes two-way automata over all alphabets.

Hover over a blue or green term in the text, or a node in the graph, to find it in the other. Select it to read its declaration both in Lean and in words.

The Setting

Take a two-way nondeterministic finite automaton (2NFA) with nn 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 nn always suffices when the alphabet may grow with nn. The witnesses here are languages whose letters are the binary relations on a finite set.

Two-way Automata

Let Σ\Sigma be an alphabet and let ⊢{\vdash} and ⊣{\dashv} be two endmarkers outside it. For a word w=w1⋯wmw = w_1 \cdots w_m over Σ\Sigma, the tape has cells 0,1,…,m+10, 1, \dots, m+1, and the tape symbol τw(i)\tau_w(i) at cell ii is ⊢{\vdash} for i=0i = 0, ⊣{\dashv} for i=m+1i = m+1 and the letter wiw_i otherwise.✦

A 2NFA AA over Σ\Sigma with state set QQ consists of an initial state q0q_0, a set F⊆QF \subseteq Q of accepting states and a transition function δ\delta that assigns to each state qq and each tape symbol σ\sigma a set δ(q,σ)⊆Q×{−1,0,1}\delta(q, \sigma) \subseteq Q \times \{-1, 0, 1\} of pairs of a next state and a head move, −1-1, 00 and 11 standing for left, stay and right.✦

A configuration of AA on ww is a pair (q,i)(q, i) of a state and a cell✦, and the one-step relation →w\to_w on configurations is (q,i)→w(q′,i′)⇔(q′,i′−i)∈δ(q,τw(i)),0≤i,i′≤m+1.(q, i) \to_w (q', i') \iff (q', i' - i) \in \delta(q, \tau_w(i)), \qquad 0 \le i, i' \le m+1.(1)✦ The language L(A)L(A) of AA is the set of words on which some configuration with an accepting state is reachable from (q0,0)(q_0, 0) under the reflexive transitive closure →w*\to_w^*, by a run of zero or more steps: L(A)={w∈Σ*:(q0,0)→w*(q,i) for some q∈F and some cell i}.L(A) = \{\, w \in \Sigma^* : (q_0, 0) \to_w^* (q, i) \text{ for some } q \in F \text{ and some cell } i \,\}.(2)✦

A 2DFA over Σ\Sigma with state set QQ is a 2NFA over Σ\Sigma with state set QQ in which every set δ(q,σ)\delta(q, \sigma) has at most one element.✦

Words of Relations

Write [h][h] for a set with hh elements. For a finite set HH, ℛH\mathcal{R}_H is the monoid of binary relations on HH under the path-order product, in which (x,z)∈PQ(x, z) \in PQ when (x,y)∈P(x, y) \in P and (y,z)∈Q(y, z) \in Q for some yy, with identity IHI_H. The relation product of a word w=a1⋯amw = a_1 \cdots a_m over the alphabet ℛH\mathcal{R}_H is r(w)=a1a2⋯amr(w) = a_1 a_2 \cdots a_m, with r(ε)=IHr(\varepsilon) = I_H.✦ The language LHL_H over ℛH\mathcal{R}_H is the set of words whose relation product relates at least one pair of points of HH: LH={w∈ℛH*:r(w)≠∅}.L_H = \{\, w \in \mathcal{R}_H^* : r(w) \ne \emptyset \,\}.(3)✦

The Claim

Theorem 1 (Determinization). (a) Let n≥4n \ge 4 and H=[n−2]H = [n-2]. There is a 2NFA AnA_n over ℛH\mathcal{R}_H with nn states such that L(An)=LHL(A_n) = L_H and every 2NFA over ℛH\mathcal{R}_H with a finite state set QQ that recognizes the complement ℛH*\L(An)\mathcal{R}_H^* \setminus L(A_n) has |Q|≥12⋅2⌊(n−4)/127⌋−1.|Q| \ge \frac{1}{2} \cdot 2^{\lfloor (n-4)/127 \rfloor} - 1.(4)✦ (b) If moreover n≥131n \ge 131, every 2DFA over ℛH\mathcal{R}_H with a finite state set QQ that recognizes LHL_H, which is L(An)L(A_n), has |Q|≥12⋅2⌊(n−4)/127⌋.|Q| \ge \frac{1}{2} \cdot 2^{\lfloor (n-4)/127 \rfloor}.(5)✦ (c) For every polynomial pp with real coefficients there are natural numbers nn and kk and a 2NFA AA with nn states over a kk-letter alphabet such that every 2DFA with ss states recognizing L(A)L(A) has s>p(n).s > p(n).(6)✦

In the paper, the result reads: 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 c⋅2⌊(n−4)/127⌋c \cdot 2^{\lfloor (n-4)/127 \rfloor} states, and hence no polynomial state bound independent of the finite alphabet can determinize all 2NFAs.

The theorem takes c=12c = \frac{1}{2} and n0=131n_0 = 131.

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 LHL_H of (3) over the alphabet ℛH\mathcal{R}_H of binary relations on H=[n−2]H = [n-2].

One-way Liveness

The one-way liveness language OWLh\mathrm{OWL}_h is the set of live words over the alphabet of binary relations on [h][h]✦, a word being live when its relation product, as in (3), is nonempty.✦

A nondeterministic automaton AA with nn states over Σ\Sigma 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 Σ\Sigma or an endmarker, a set of pairs (q′,d)(q', d) of a next state and a move d∈{−1,0,1}d \in \{-1, 0, 1\}, with no move left on ⊢{\vdash} and no move right on ⊣{\dashv}.✦ A deterministic automaton BB with ss states over Σ\Sigma is a nondeterministic automaton with ss states over Σ\Sigma 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 AA on a word ww are as in (1), with dd the head move. An automaton AA accepts a word ww 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 ww by a run of any length when a run of zero or more steps does, as in (2). Under either convention, an automaton AA recognizes a language LL over Σ\Sigma when the words it accepts are exactly the words of LL.

For one-way liveness the library proves, for h≥2h \ge 2, that some one-way nondeterministic automaton with h+3h + 3 states recognizes OWLh\mathrm{OWL}_h under both conventions, and that every deterministic automaton with ss states recognizing OWLh\mathrm{OWL}_h under either convention satisfies 2⌊(h−2)/31⌋≤4(s+ϵ)2,2^{\lfloor (h-2)/31 \rfloor} \le 4(s + \epsilon)^2,(7)✦ where ϵ=2\epsilon = 2 for acceptance by a nonempty run and ϵ=1\epsilon = 1 for acceptance by a run of any length.

The 2DFAs of the theorem obey a bound of the same shape: if h≥2h \ge 2, every 2DFA with ss states over ℛ[h]\mathcal{R}_{[h]} that recognizes L[h]L_{[h]} satisfies 2⌊(h−2)/31⌋≤4(s+1)2.2^{\lfloor (h-2)/31 \rfloor} \le 4(s + 1)^2.(8)✦

The exponents ⌊(n−4)/31⌋\lfloor (n-4)/31 \rfloor and ⌊(n−4)/127⌋\lfloor (n-4)/127 \rfloor are tied by an inequality of numbers: if n≥131n \ge 131 and ss is a natural number with 2⌊(n−4)/31⌋≤4(s+1)22^{\lfloor (n-4)/31 \rfloor} \le 4(s+1)^2, then s≥12⋅2⌊(n−4)/127⌋.s \ge \frac{1}{2} \cdot 2^{\lfloor (n-4)/127 \rfloor}.(9)✦