OctoInformBeta

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

§5.2 (proof of Lemma 2.2): finite computations as diagram paths: A fresh state carries accepted runs past the right endmarker, and joining networks of finite paths multiplies their boundary diagrams

Acceptance of a two-way automaton read off boundary diagrams.

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) and an input word. A run moves the head back and forth over the marked tape, so a stretch of the tape meets the run only where it crosses the two ends of the stretch, in either direction and in some state. The result below is Lemma 2.2 of the OpenAI preprint on an exponential state lower bound for two-way nondeterministic complementation. It reads the finite computations of the automaton as paths through records of such crossings, one cell at a time, and the question is how acceptance of a word is read off at the two ends of its tape.

Two-way Automata

A 2NFA A=(Q,Σ,q0,F,δ)A = (Q, \Sigma, q_0, F, \delta) over an alphabet Σ\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 xx (a letter of Σ\Sigma or one of the endmarkers ⊢{\vdash} and ⊣{\dashv}) a set δ(q,x)\delta(q, x) of pairs of a next state and a move dd: left (d=−1d = -1), stay (d=0d = 0) or right (d=+1d = +1).✦

The tape of a word w=w1⋯wnw = w_1 \cdots w_n has cells 0,1,…,n+10, 1, \dots, n+1, and the tape symbol at cell ii is ⊢{\vdash} for i=0i = 0, ⊣{\dashv} for i=n+1i = n+1 and wiw_i otherwise.✦ The one-step relation →w\to_w of AA on ww is the relation on configurations, the pairs (q,i)(q, i) of a state and a cell, with (q,i)→w(q′,i+d)(q, i) \to_w (q', i + d) when (q′,d)∈δ(q,x)(q', d) \in \delta(q, x) for the tape symbol xx at cell ii and i+di + d is again a cell.✦

Relations compose in path order, (ξ,ζ)∈PP′(\xi, \zeta) \in PP' when (ξ,η)∈P(\xi, \eta) \in P and (η,ζ)∈P′(\eta, \zeta) \in P' for some η\eta, and the reflexive transitive closure of a relation PP on a set XX is P*=⋃k≥0PkP^* = \bigcup_{k \ge 0} P^k, with P0=IXP^0 = I_X the identity relation on XX. The language L(A)L(A) of AA is the set of words ww over Σ\Sigma with (q0,0)→w*(q,i)(q_0, 0) \to_w^* (q, i) for some accepting state qq and some cell ii, a run of length zero included.✦

Boundary Diagrams

Fix a label set DD of mm elements and two copies D+D^+ and D−D^- of it. A boundary diagram a∈𝒯ma \in \mathcal{T}_m is a quadruple of relations: the forward relation Fa⊆D+×D+F_a \subseteq D^+ \times D^+, entering on the left and exiting on the right; the backward relation Ba⊆D−×D−B_a \subseteq D^- \times D^-, entering on the right and exiting on the left; the left relation La⊆D+×D−L_a \subseteq D^+ \times D^-, entering and exiting on the left; and the right relation Ra⊆D−×D+R_a \subseteq D^- \times D^+, entering and exiting on the right.✦

The product abab of diagrams a,b∈𝒯ma, b \in \mathcal{T}_m is the diagram of aa glued to the left of bb: Fab=Fa(LbRa)*Fb,Lab=La∪Fa(LbRa)*LbBa,Bab=Bb(RaLb)*Ba,Rab=Rb∪BbRa(LbRa)*Fb.\begin{aligned} F_{ab} &= F_a (L_b R_a)^* F_b, & L_{ab} &= L_a \cup F_a (L_b R_a)^* L_b B_a,\\ B_{ab} &= B_b (R_a L_b)^* B_a, & R_{ab} &= R_b \cup B_b R_a (L_b R_a)^* F_b. \end{aligned}(1)✦ The identity diagram 1m1_m has forward relation ID+I_{D^+}, backward relation ID−I_{D^-}, and empty left and right relations.✦

Path Networks and Chains

A finite-path network NN on a vertex set VV with mm labels consists of an edge relation ENE_N on VV and four boundary relations: left and right entrances ιNℓ,ιNr⊆D×V\iota^\ell_N, \iota^r_N \subseteq D \times V, relating a label to the vertices it enters at on that side, and left and right exits ωNℓ,ωNr⊆V×D\omega^\ell_N, \omega^r_N \subseteq V \times D, relating a vertex to the labels by which it leaves on that side.✦ The summary diagram Nˆ∈𝒯m\widehat N \in \mathcal{T}_m of NN records which boundary labels a finite internal path joins: FNˆ=ιNℓEN*ωNr,BNˆ=ιNrEN*ωNℓ,LNˆ=ιNℓEN*ωNℓ,RNˆ=ιNrEN*ωNr.F_{\widehat N} = \iota^\ell_N E_N^* \omega^r_N, \quad B_{\widehat N} = \iota^r_N E_N^* \omega^\ell_N, \quad L_{\widehat N} = \iota^\ell_N E_N^* \omega^\ell_N, \quad R_{\widehat N} = \iota^r_N E_N^* \omega^r_N.(2)✦

The join N⋈MN \bowtie M of NN on VV, placed to the left of a network MM on WW, is the network on V⊔WV \sqcup W with the left entrances and exits of NN, the right entrances and exits of MM, and as edge relation the block relation whose restrictions to V×VV \times V, V×WV \times W, W×VW \times V and W×WW \times W are EN,ωNrιMℓ,ωMℓιNr,EM.E_N, \qquad \omega^r_N \iota^\ell_M, \qquad \omega^\ell_M \iota^r_N, \qquad E_M.(3)✦

A move assignment μ\mu on an alphabet Γ\Gamma and the label set DD assigns to each letter x∈Γx \in \Gamma and each move dd a relation μ(x,d)\mu(x, d) on DD. For a word w=w1⋯wnw = w_1 \cdots w_n over Γ\Gamma with a final letter z∈Γz \in \Gamma, the chain of ww and zz has n+1n + 1 cells, and its chain vertices are n+1n + 1 disjoint copies of DD, one for each cell.✦ The cell coordinate of a chain vertex is the index k∈{0,…,n}k \in \{0, \dots, n\} of its cell✦, and the symbol at the vertex is the letter of that cell, wk+1w_{k+1} for k<nk < n and zz for k=nk = n✦. The chain step relation ⇝w,z\rightsquigarrow_{w,z} is the relation on pairs of a label and a position 0,…,n+10, \dots, n+1 with (q,k)⇝w,z(r,k+d)(q, k) \rightsquigarrow_{w,z} (r, k + d) when kk is the cell coordinate of a chain vertex with symbol xx and (q,r)∈μ(x,d)(q, r) \in \mu(x, d); no step leaves the terminal position n+1n + 1.✦

The Claim

Definition 1. Let qfq_{\mathrm f} be a fresh state and Q′=Q∪{qf}Q' = Q \cup \{q_{\mathrm f}\}. For a word ww of length nn, the augmented configuration of a configuration (q,i)(q, i) of AA is the same pair in Q′×{0,…,n+2}Q' \times \{0, \dots, n+2\}, whose last position n+2n + 2 lies past the right endmarker.✦ The augmented step relation ⇒w\Rightarrow_w of AA on ww is the relation on Q′×{0,…,n+2}Q' \times \{0, \dots, n+2\} consisting of the pairs (q,i)⇒w(q′,i′) for (q,i)→w(q′,i′),(q,i)⇒w(qf,i) for q∈F,i≤n+1,(qf,i)⇒w(qf,i+1).(q, i) \Rightarrow_w (q', i') \text{ for } (q, i) \to_w (q', i'), \quad (q, i) \Rightarrow_w (q_{\mathrm f}, i) \text{ for } q \in F,\ i \le n + 1, \quad (q_{\mathrm f}, i) \Rightarrow_w (q_{\mathrm f}, i + 1).(4)✦ The augmented move relation μA(x,d)\mu_A(x, d) of AA at a tape symbol xx and a move dd is the relation on Q′Q' given by (p,r)∈μA(x,d)⇔{(r,d)∈δ(p,x),d≠−1 if x=⊢,d≠+1 if x=⊣for p,r∈Q,p∈F and d=0for p∈Q,r=qf,d=+1for p=r=qf,(p, r) \in \mu_A(x, d) \iff \begin{cases} (r, d) \in \delta(p, x),\ d \ne -1 \text{ if } x = {\vdash},\ d \ne +1 \text{ if } x = {\dashv} & \text{for } p, r \in Q,\\ p \in F \text{ and } d = 0 & \text{for } p \in Q,\ r = q_{\mathrm f},\\ d = +1 & \text{for } p = r = q_{\mathrm f}, \end{cases}(5)✦ and it never relates qfq_{\mathrm f} to a state of QQ.

The single-cell diagram κ∈𝒯m\kappa \in \mathcal{T}_m of three relations M−1M_{-1}, M0M_0 and M+1M_{+1} on DD, the left, stay and right moves of one cell, records the paths that enter the cell from either side, stay finitely often and leave by one move to the left or the right: Fκ=Rκ=M0*M+1,Bκ=Lκ=M0*M−1.F_\kappa = R_\kappa = M_0^* M_{+1}, \qquad B_\kappa = L_\kappa = M_0^* M_{-1}.(6)✦

The single-cell network Nμ(x)N_\mu(x) of a letter x∈Γx \in \Gamma is the finite-path network on one cell given by the relations μ(x,−1)\mu(x, -1), μ(x,0)\mu(x, 0) and μ(x,+1)\mu(x, +1) on DD. The chain network Cμ(w,z)C_\mu(w, z) of a word ww over Γ\Gamma with final letter zz is the finite-path network on the chain vertices of ww and zz built by recursion on ww from the single-cell networks of its letters, where x∈Γx \in \Gamma is a letter and vv a word over Γ\Gamma: Cμ(ε,z)=Nμ(z),Cμ(xv,z)=Nμ(x)⋈Cμ(v,z).C_\mu(\varepsilon, z) = N_\mu(z), \qquad C_\mu(xv, z) = N_\mu(x) \bowtie C_\mu(v, z).(7)✦

Theorem 1.

  1. Let AA be a 2NFA over Σ\Sigma and ww a word over Σ\Sigma of length nn. Then w∈L(A)⇔(q0,0)⇒w*(qf,n+2).w \in L(A) \iff (q_0, 0) \Rightarrow_w^* (q_{\mathrm f}, n + 2).(8)✦

  2. Let NN and MM be finite-path networks on VV and on WW with mm labels. Then N⋈Mˆ=NˆMˆ.\widehat{N \bowtie M} = \widehat N \, \widehat M.(9)✦

  3. Let μ\mu be a move assignment on Γ\Gamma and DD, let ww be a word over Γ\Gamma of length nn with final letter zz, and let q,r∈Dq, r \in D. Then (q,0)⇝w,z*(r,n+1)⇔(q,r)∈FCμ(w,z)ˆ.(q, 0) \rightsquigarrow_{w,z}^* (r, n + 1) \iff (q, r) \in F_{\widehat{C_\mu(w, z)}}.(10)✦

  4. Let AA be a 2NFA over Σ\Sigma with ss states. Then there are a map τ\tau from words over Σ\Sigma to 𝒯s+1\mathcal{T}_{s+1}, diagrams λ,ρ∈𝒯s+1\lambda, \rho \in \mathcal{T}_{s+1} and labels α\alpha and β\beta such that, for all words uu, vv and ww over Σ\Sigma, τ(ε)=1s+1,τ(uv)=τ(u)τ(v),w∈L(A)⇔(α,β)∈F(λτ(w))ρ.\tau(\varepsilon) = 1_{s+1}, \qquad \tau(uv) = \tau(u)\,\tau(v), \qquad w \in L(A) \iff (\alpha, \beta) \in F_{(\lambda\,\tau(w))\,\rho}.(11)✦

What Is Checked

The theorem is stated over a 2NFA with its tape symbols, one-step relation and language, the augmented configurations and the augmented step relation (4), boundary diagrams with their product (1) and the identity diagram, finite-path networks with their summary diagram (2) and join (3), and a move assignment with its chain step relation and chain network (7).