OctoInformBeta

OpenAI preprint, September 2026 · §2. Path diagrams and missing recurrent classes · §2

Lemma 2.2 [Diagram representation of a 2NFA]: An ss-state two-way automaton accepts ww exactly when a fixed forward edge lies in the image of ww flanked by two fixed diagrams

Acceptance by a two-way automaton through a homomorphism to 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) AA and a factor uu of its input. A run of AA may cross uu many times and in both directions, each time entering uu across its left or its right boundary in some state and leaving it across one of the two boundaries in some state. The four kinds of crossing give four relations, which together form a diagram. A word acts on the states of a one-way automaton by a single relation, the product of the relations of its letters, and acceptance is read off that relation. The question is whether a 2NFA admits the same description with diagrams in place of relations: a homomorphism from words to diagrams, and acceptance of a word read off one edge of its image flanked by two fixed diagrams.

Two-way Automata

A 2NFA AA 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.✦ To each state qq and each symbol σ\sigma, a letter of Σ\Sigma or one of the endmarkers ⊢\vdash and ⊣\dashv, δ\delta assigns a set δ(q,σ)⊆Q×{−1,0,+1}\delta(q, \sigma) \subseteq Q \times \{-1, 0, +1\} of pairs of a next state and a move to the left, in place or to the right.

The tape of a word w=w1⋯wnw = w_1 \cdots w_n over Σ\Sigma has cells 0,1,…,n+10, 1, \dots, n+1, and its symbol tw(i)t_w(i) in cell ii is ⊢\vdash for i=0i = 0, ⊣\dashv for i=n+1i = n+1 and the letter wiw_i otherwise.✦ The 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, given by (q,i)→w(q′,i+μ)when (q′,μ)∈δ(q,tw(i)) and 0≤i+μ≤n+1.(q, i) \to_w (q', i + \mu) \quad\text{when } (q', \mu) \in \delta\bigl(q, t_w(i)\bigr) \text{ and } 0 \le i + \mu \le n + 1.(1)✦

The reflexive transitive closure P*P^* of a relation PP on a set joins xx to yy when a chain of zero or more steps of PP leads from xx to yy.✦ The language L(A)L(A) of AA is the set of words on which a run from the initial state on the left endmarker reaches an accepting state: 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)✦

Diagrams

A diagram dd on mm labels is a quadruple of relations on two copies D+D^+ and D−D^- of a label set DD with mm elements: the forward relation Fd⊆D+×D+F_d \subseteq D^+ \times D^+, the backward relation Bd⊆D−×D−B_d \subseteq D^- \times D^-, the left relation Ld⊆D+×D−L_d \subseteq D^+ \times D^- and the right relation Rd⊆D−×D+R_d \subseteq D^- \times D^+. The pairs in these relations are the edges of dd: a forward edge enters on the left and exits on the right, a backward edge enters on the right and exits on the left, and a left or right edge enters and exits on that side. The diagrams on mm labels form the set 𝒯m\mathcal{T}_m.

Relations compose in path order, (x,z)∈PP′(x, z) \in PP' when (x,y)∈P(x, y) \in P and (y,z)∈P′(y, z) \in P' for some yy. The product dede of diagrams d,e∈𝒯md, e \in \mathcal{T}_m, with dd on the left, is the diagram with Fde=Fd(LeRd)*Fe,Bde=Be(RdLe)*Bd,Lde=Ld∪Fd(LeRd)*LeBd,Rde=Re∪BeRd(LeRd)*Fe.\begin{aligned} F_{de} &= F_d\,(L_e R_d)^*\,F_e, &\qquad B_{de} &= B_e\,(R_d L_e)^*\,B_d,\\ L_{de} &= L_d \cup F_d\,(L_e R_d)^*\,L_e B_d, &\qquad R_{de} &= R_e \cup B_e R_d\,(L_e R_d)^*\,F_e. \end{aligned}(3)✦ The identity diagram 1m1_m on mm labels is the diagram in 𝒯m\mathcal{T}_m whose forward relation is the identity relation ID+I_{D^+} on D+D^+, whose backward relation is the identity relation ID−I_{D^-} on D−D^-, and whose left and right relations are empty.

The single-cell diagram γ=γ(M−1,M0,M+1)\gamma = \gamma(M_{-1}, M_0, M_{+1}) of three relations M−1M_{-1}, M0M_0 and M+1M_{+1} on DD, the moves to the left, in place and to the right inside one cell, is the diagram in 𝒯m\mathcal{T}_m with Fγ=Rγ=M0*M+1,Bγ=Lγ=M0*M−1.F_\gamma = R_\gamma = M_0^*\, M_{+1}, \qquad B_\gamma = L_\gamma = M_0^*\, M_{-1}.(4)✦

For a map θ:Σ→𝒯m\theta\colon \Sigma \to \mathcal{T}_m, the word diagram θˆ(w)\hat\theta(w) of a word w=w1⋯wnw = w_1 \cdots w_n is the product of the diagrams of its letters: θˆ(w)=θ(w1)θ(w2)⋯θ(wn),θˆ(ε)=1m.\hat\theta(w) = \theta(w_1)\,\theta(w_2) \cdots \theta(w_n), \qquad \hat\theta(\varepsilon) = 1_m.(5)✦

The Claim

Theorem 1. Let AA be a 2NFA with ss states over an alphabet Σ\Sigma. There are a map τ:Σ*→𝒯s+1\tau\colon \Sigma^* \to \mathcal{T}_{s+1} with τ(ε)=1s+1\tau(\varepsilon) = 1_{s+1} and τ(uv)=τ(u)τ(v)\tau(uv) = \tau(u)\,\tau(v) for all words uu and vv, diagrams λ,ρ∈𝒯s+1\lambda, \rho \in \mathcal{T}_{s+1} and labels a,b∈D+a, b \in D^+ such that, for every word ww over Σ\Sigma, w∈L(A)⇔(a,b)∈Fλτ(w)ρ.w \in L(A) \iff (a, b) \in F_{\lambda\,\tau(w)\,\rho}.(6)✦

In the paper, the result reads: for an ss-state 2NFA BB over a finite alphabet Σ\Sigma, with BB for the page’s AA, there are a monoid homomorphism τ:Σ*→𝒯s+1\tau\colon \Sigma^* \to \mathcal{T}_{s+1}, endmarker diagrams λ\lambda and ρ\rho and labels a,b∈D+a, b \in D^+ with w∈L(B)w \in L(B) if and only if (a,b)∈Fλτ(w)ρ(a, b) \in F_{\lambda\tau(w)\rho}, and consequently αuβ∈L(B)\alpha u \beta \in L(B) implies αvβ∈L(B)\alpha v \beta \in L(B) for all words α\alpha and β\beta whenever τ(u)⊑τ(v)\tau(u) \sqsubseteq \tau(v), each of the four relations of τ(u)\tau(u) lying inside the corresponding relation of τ(v)\tau(v).

What Is Checked

The claim (6) is stated over a 2NFA AA with ss states, its step relation (1) on the tape with endmarkers and its language (2), and the diagrams on s+1s+1 labels with the product (3) and the identity diagram 1s+11_{s+1}.

Acceptance by AA has a second form, through an augmented machine. The augmented configurations of AA on a word ww of length nn are the pairs (q,i)(q, i) of a state of AA or a new state ⋆\star and a cell among 0,…,n+20, \dots, n+2, the cell n+2n+2 lying to the right of ⊣\dashv; each configuration of AA is one of them.✦ The augmented step relation ⇒w\Rightarrow_w of AA on ww is the relation on augmented configurations that joins cc to dd when c→wdc \to_w d, when c=(q,i)c = (q, i) with q∈Fq \in F and d=(⋆,i)d = (\star, i), and when c=(⋆,i)c = (\star, i) and d=(⋆,i+1)d = (\star, i + 1).✦ For every word ww of length nn, w∈L(A)⇔(q0,0)⇒w*(⋆,n+2).w \in L(A) \iff (q_0, 0) \Rightarrow_w^* (\star, n + 2).(7)✦

A network NN on mm labels with vertex set VV consists of an edge relation EE on VV, left and right entrance relations inℓ,inr⊆D×V\mathrm{in}_\ell, \mathrm{in}_r \subseteq D \times V and left and right exit relations outℓ,outr⊆V×D\mathrm{out}_\ell, \mathrm{out}_r \subseteq V \times D.✦ Its summary N¯∈𝒯m\overline{N} \in \mathcal{T}_m is the diagram of its paths from an entrance to an exit: FN¯=inℓE*outr,BN¯=inrE*outℓ,LN¯=inℓE*outℓ,RN¯=inrE*outr.\begin{aligned} F_{\overline{N}} &= \mathrm{in}_\ell\, E^*\, \mathrm{out}_r, &\qquad B_{\overline{N}} &= \mathrm{in}_r\, E^*\, \mathrm{out}_\ell,\\ L_{\overline{N}} &= \mathrm{in}_\ell\, E^*\, \mathrm{out}_\ell, &\qquad R_{\overline{N}} &= \mathrm{in}_r\, E^*\, \mathrm{out}_r. \end{aligned}(8)✦

Let each letter σ∈Σ\sigma \in \Sigma carry three relations M−1σM^\sigma_{-1}, M0σM^\sigma_0 and M+1σM^\sigma_{+1} on DD, and take a word ww of length nn and a final letter ℓ\ell. The chain network N(w,ℓ)N(w, \ell) is the network on mm labels obtained by joining, from left to right, the single-cell networks of the letters of wℓw\ell, where the single-cell network of a letter is the network whose summary is the single-cell diagram of its three relations; its vertices are n+1n+1 copies of DD, one for each cell 0,…,n0, \dots, n, and each vertex carries its cell and the letter in it, wi+1w_{i+1} in cell i<ni < n and ℓ\ell in cell nn.✦ The chain step relation ⇀\rightharpoonup on D×{0,…,n+1}D \times \{0, \dots, n+1\} joins (q,i)(q, i) to (r,i+μ)(r, i + \mu), for a move μ∈{−1,0,+1}\mu \in \{-1, 0, +1\}, when i≤ni \le n, i+μ≥0i + \mu \ge 0 and (q,r)∈Mμσ(q, r) \in M^\sigma_\mu for the letter σ\sigma in cell ii.✦ For all labels qq and rr, (q,0)⇀*(r,n+1)⇔(q,r)∈FN(w,ℓ)¯.(q, 0) \rightharpoonup^* (r, n + 1) \iff (q, r) \in F_{\overline{N(w, \ell)}}.(9)✦