OctoInformBeta

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

Lemma 5.1 [The source automaton]: For every set HH, an explicit two-way nondeterministic automaton accepts exactly the words over binary relations on HH with nonempty product

A two-way automaton with |H|+2|H|+2 states for nonempty relation products.

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 set HH and use the binary relations on HH as letters. A word a1a2⋯ama_1 a_2 \cdots a_m then lays out a route of mm steps through HH, the iith step allowed from xx to yy when (x,y)∈ai(x, y) \in a_i, and the words of interest are those along which some walk in HH completes every step. The question is how few states suffice for a two-way nondeterministic finite automaton (2NFA) that recognizes these words when HH is finite.

The Source Language

For a set HH, the monoid ℛH\mathcal{R}_H of binary relations on HH is the set of all binary relations on HH under the path-order product, in which (x,z)∈ab(x, z) \in ab when (x,y)∈a(x, y) \in a and (y,z)∈b(y, z) \in b for some y∈Hy \in H, with the identity relation IHI_H as its identity. The relation product r(w)r(w) of a word w=a1a2⋯amw = a_1 a_2 \cdots a_m over the alphabet ℛH\mathcal{R}_H is the product of its letters in order: r(a1a2⋯am)=a1a2⋯am,r(ε)=IH.r(a_1 a_2 \cdots a_m) = a_1 a_2 \cdots a_m, \qquad r(\varepsilon) = I_H.(1)✦

The source language LHL_H over ℛH\mathcal{R}_H is the set of words whose relation product is nonempty: LH={w∈ℛH*:r(w)≠∅}.L_H = \{\, w \in \mathcal{R}_H^{*} : r(w) \neq \emptyset \,\}.(2)✦

Two-way Automata

A two-way nondeterministic finite automaton AA over an alphabet Σ\Sigma with state set QQ, both of which may be infinite, consists of an initial state q0∈Qq_0 \in Q, a set F⊆QF \subseteq Q of accepting states and a transition function δ\delta.✦ To each state qq and each tape symbol xx, a letter of Σ\Sigma or one of the endmarkers ⊢{\vdash} and ⊣{\dashv}, the transition function assigns a set δ(q,x)⊆Q×{−1,0,+1}\delta(q, x) \subseteq Q \times \{-1, 0, +1\} of pairs of a next state and a head move, left, stay or right.

For a word w=w1⋯wmw = w_1 \cdots w_m over Σ\Sigma, the tape symbol tw(i)t_w(i) at a cell ii of the tape, numbered from 00 to m+1m+1, is tw(0)=⊢,tw(i)=wi(1≤i≤m),tw(m+1)=⊣.t_w(0) = {\vdash}, \qquad t_w(i) = w_i \quad (1 \le i \le m), \qquad t_w(m+1) = {\dashv}.(3)✦ A configuration of AA on ww is a pair (q,i)(q, i) of a state and a cell. The one-step relation →w\to_w of AA on ww is the relation on configurations given by (q,i)→w(q′,i′)when(q′,i′−i)∈δ(q,tw(i)).(q, i) \to_w (q', i') \quad\text{when}\quad (q', i' - i) \in \delta\bigl(q, t_w(i)\bigr).(4)✦ Both configurations lie on the tape, so no step moves the head past an endmarker. The reflexive transitive closure →w*\to_w^{*} of the one-step relation is the union of its powers →wn\to_w^{n} for n≥0n \ge 0, the zeroth being the identity relation on configurations.✦

The language L(A)L(A) of AA is the set of words over Σ\Sigma 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 \,\}.(5)✦

The Source Automaton

For a set HH, the source automaton AHA_H is the 2NFA over ℛH\mathcal{R}_H whose states are the points of HH and two further states, an initial state q0q_0 and a state qfq_f, the only accepting one, and whose transition function is given, for p∈Hp \in H and a∈ℛHa \in \mathcal{R}_H, by δ(q0,⊢)={(q,+1):q∈H},δ(p,a)={(q,+1):(p,q)∈a},δ(p,⊣)={(qf,0)},\begin{aligned} \delta(q_0, {\vdash}) &= \{\, (q, +1) : q \in H \,\},\\ \delta(p, a) &= \{\, (q, +1) : (p, q) \in a \,\},\\ \delta(p, {\dashv}) &= \{ (q_f, 0) \}, \end{aligned}(6)✦ and by the empty set on every other pair of a state and a tape symbol.

The Claim

Theorem 1. Let HH be a set. Then L(AH)=LH.L(A_H) = L_H.(7)✦ If HH is finite, there is a 2NFA AA over ℛH\mathcal{R}_H with exactly |H|+2|H| + 2 states such that L(A)=LH.L(A) = L_H.(8)✦

In the paper, the result reads: the language LHL_H is recognized by a 2NFA with exactly |H|+2|H| + 2 states.

What Is Checked

The claim is stated over 2NFAs and their languages (5), read on the tape (3) through the one-step relation (4) and its reflexive transitive closure, and over the relation product (1), the source language (2) and the source automaton (6).