OctoInformBeta

OpenAI preprint, September 2026 · §1. Introduction · §1

§1 (setting): the 2NFA model and the relation-product liveness language: Nondeterministic and deterministic machines on an endmarked tape, and the words of relations on HH whose product is nonempty

Two-way automata and a language of binary relations.

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

Two-way finite automata read their input written between a left endmarker ⊢\vdash and a right endmarker ⊣\dashv, and at each step move the head one cell to the left, keep it in place or move it one cell to the right. The model here is the two-way nondeterministic finite automaton (2NFA), with the two-way deterministic finite automaton (2DFA) as its deterministic case.

The input alphabet of interest is ℛH\mathcal{R}_H, the set of binary relations on a set HH.

The Tape

For a word w=a1a2⋯anw = a_1 a_2 \cdots a_n over an alphabet Σ\Sigma, the tape of ww is ⊢w⊣\vdash w \dashv, with cells numbered 0,1,…,n+10, 1, \dots, n+1 from the left. The tape symbol tw(p)t_w(p) at a cell pp is the letter or endmarker written there: tw(p)={⊢if p=0,apif 1≤p≤n,⊣if p=n+1.t_w(p) = \begin{cases} \vdash & \text{if } p = 0,\\ a_p & \text{if } 1 \le p \le n,\\ \dashv & \text{if } p = n+1. \end{cases}(1)✦

Relations and Their Products

The relation monoid ℛH\mathcal{R}_H of a set HH is the set of all binary relations P⊆H×HP \subseteq H \times H with the product taken in path order and the identity relation IHI_H: PR={(x,z):(x,y)∈P and (y,z)∈R for some y∈H},IH={(x,x):x∈H}.PR = \{(x, z) : (x, y) \in P \text{ and } (y, z) \in R \text{ for some } y \in H\}, \qquad I_H = \{(x, x) : x \in H\}.(2)✦

The relation product of a word w=P1P2⋯Pkw = P_1 P_2 \cdots P_k over the alphabet ℛH\mathcal{R}_H is the element r(w)r(w) of ℛH\mathcal{R}_H given by r(P1P2⋯Pk)=P1P2⋯Pk,r(ε)=IH.r(P_1 P_2 \cdots P_k) = P_1 P_2 \cdots P_k, \qquad r(\varepsilon) = I_H.(3)✦

The reflexive transitive closure R*R^* of a relation RR on a set XX is the relation on XX joining xx to yy when a chain of zero or more RR-steps leads from xx to yy, the powers taken in ℛX\mathcal{R}_X: R*=⋃k≥0Rk,R0=IX,Rk+1=RkR.R^* = \bigcup_{k \ge 0} R^k, \qquad R^0 = I_X, \quad R^{k+1} = R^k R.(4)✦

The Definition

Definition 1. Let Σ\Sigma be an input alphabet and QQ a set of states. A two-way nondeterministic finite automaton AA over Σ\Sigma with state set QQ consists of an initial state q0∈Qq_0 \in Q, a set F⊆QF \subseteq Q of accepting states and a transition function δ:Q×(Σ∪{⊢,⊣})→2Q×{−1,0,+1}\delta \colon Q \times (\Sigma \cup \{\vdash, \dashv\}) \to 2^{Q \times \{-1, 0, +1\}}(5)✦ giving, for each state and each scanned symbol, the allowed pairs of a next state and a move: −1-1 to the left, 00 to stay, +1+1 to the right.

On an input ww of length nn, a configuration is a pair (q,p)(q, p) of a state q∈Qq \in Q and a cell 0≤p≤n+10 \le p \le n+1, and the step relation →w\to_w of AA on ww is the relation on configurations given by (q,p)→w(q′,p′)⇔(q′,p′−p)∈δ(q,tw(p)).(q, p) \to_w (q', p') \iff (q', p' - p) \in \delta\bigl(q, t_w(p)\bigr).(6)✦

The language L(A)L(A) of AA is the set of words on which a run of zero or more steps leads from the initial configuration (q0,0)(q_0, 0), the head on ⊢\vdash, to a configuration in an accepting state, with →w*\to_w^* the reflexive transitive closure (4) of →w\to_w: L(A)={w∈Σ*:(q0,0)→w*(q,p) for some q∈F and some cell p}.L(A) = \{ w \in \Sigma^* : (q_0, 0) \to_w^* (q, p) \text{ for some } q \in F \text{ and some cell } p \}.(7)✦

The automaton AA is a two-way deterministic finite automaton when each state and scanned symbol allow at most one move: |δ(q,s)|≤1for every q∈Q and every s∈Σ∪{⊢,⊣}.|\delta(q, s)| \le 1 \quad \text{for every } q \in Q \text{ and every } s \in \Sigma \cup \{\vdash, \dashv\}.(8)✦

For a set HH, the language LHL_H over the alphabet ℛH\mathcal{R}_H is the set of words whose relation product (3) is nonempty: LH={w∈ℛH*:r(w)≠∅}.L_H = \{ w \in \mathcal{R}_H^* : r(w) \ne \emptyset \}.(9)✦

In the paper, the definitions read: a 2NFA has one initial state, a set of accepting states and transitions that depend on the state and the scanned symbol, with the moves left, stay and right, its head starts on the left endmarker and may not leave the endmarked tape, and it accepts when some finite computation reaches an accepting state, the initial configuration included; a 2DFA has at most one successor per state and symbol; and over the alphabet ΣH=ℛH\Sigma_H = \mathcal{R}_H of binary relations on HH, with r(w)r(w) the path-order product and r(ε)=IHr(\varepsilon) = I_H, the language is LH={w:r(w)≠∅}L_H = \{ w : r(w) \ne \emptyset \}.

What Is Checked

The automaton (5) with its step relation (6), its language (7) and the deterministic case (8), and the language LHL_H of (9), are stated over any input alphabet Σ\Sigma, any set QQ of states and any set HH, on the tape symbols (1), the reflexive transitive closure (4), and the relation monoid (2) with its relation product (3).