OctoInformBeta

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

Proposition 2.3 [Order reversal from complementation]: A word-to-diagram homomorphism detecting empty relation products yields an order-reversing surjection onto ℛH\mathcal{R}_H, and D(h)≤2mD(h) \le 2m for |H|=h≥2|H| = h \ge 2

Recognizing the complement reverses inclusion of 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

Let HH be a set. The relation monoid ℛH\mathcal{R}_H of HH is the monoid of binary relations on HH under the path-order product (x,z)∈PQ⇔(x,y)∈P and (y,z)∈Q for some y∈H,(x, z) \in PQ \iff (x, y) \in P \text{ and } (y, z) \in Q \text{ for some } y \in H,(1)✦ with unit the identity relation IHI_H. For a subset AA of HH, the restricted identity IAI_A is the relation {(x,x):x∈A}\{(x, x) : x \in A\} on HH.✦

Let ΣH\Sigma_H be the alphabet whose letters are the binary relations on HH. The relation product of a word w=x1x2⋯xkw = x_1 x_2 \cdots x_k over ΣH\Sigma_H is the relation r(w)=x1x2⋯xkr(w) = x_1 x_2 \cdots x_k on HH, the path-order product of its letters, with r(ε)=IHr(\varepsilon) = I_H.✦ The language LHL_H consists of the words whose relation product is nonempty, and its complement ΣH*\LH\Sigma_H^* \setminus L_H of the words ww with r(w)=∅r(w) = \emptyset.

Proposition 2.3 concerns two-way nondeterministic finite automata (2NFA) that recognize ΣH*\LH\Sigma_H^* \setminus L_H for a finite HH, and the number of states they need. It works with diagrams, which record how a two-way automaton traverses a block of its tape, entering it from the left or the right and leaving it on the left or the right.

For a natural number h≥2h \ge 2, the loss bound D(h)D(h) is the power of two D(h)=2⌊(h−2)/127⌋.D(h) = 2^{\lfloor (h-2)/127 \rfloor}.(2)✦

Diagrams

Let D+D^+ and D−D^- be two copies of an mm-element set of labels. A diagram aa on mm labels is a quadruple of relations: the forward relation Fa⊆D+×D+F_a \subseteq D^+ \times D^+, the backward relation Ba⊆D−×D−B_a \subseteq D^- \times D^-, the left relation La⊆D+×D−L_a \subseteq D^+ \times D^- and the right relation Ra⊆D−×D+R_a \subseteq D^- \times D^+.✦ The pairs in these relations are the edges of aa. An edge of FaF_a enters on the left and exits on the right, an edge of BaB_a enters on the right and exits on the left, an edge of LaL_a enters and exits on the left, and an edge of RaR_a enters and exits on the right.

The reflexive transitive closure P*P^* of a relation PP on a set XX is the relation on XX that relates xx to yy when there is a chain x=x0,x1,…,xk=yx = x_0, x_1, \dots, x_k = y with k≥0k \ge 0 and (xi−1,xi)∈P(x_{i-1}, x_i) \in P for each ii.✦ The product abab of diagrams aa and bb on mm labels is the diagram on mm labels with Fab=Fa(LbRa)*Fb,Bab=Bb(RaLb)*Ba,Lab=La∪Fa(LbRa)*LbBa,Rab=Rb∪BbRa(LbRa)*Fb,\begin{aligned} F_{ab} &= F_a (L_b R_a)^* F_b, & B_{ab} &= B_b (R_a L_b)^* B_a, \\ L_{ab} &= L_a \cup F_a (L_b R_a)^* L_b B_a, & R_{ab} &= R_b \cup B_b R_a (L_b R_a)^* F_b, \end{aligned}(3)✦ where relations compose in path order. The identity diagram 1m1_m on mm labels is the diagram 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 monoid 𝒯m\mathcal{T}_m is the set of diagrams on mm labels under this product, with unit 1m1_m.

Edge inclusion ⊑\sqsubseteq is the relation on 𝒯m\mathcal{T}_m that holds at z⊑z′z \sqsubseteq z' when each relation of zz is contained in the corresponding relation of z′z': z⊑z′⇔Fz⊆Fz′,Bz⊆Bz′,Lz⊆Lz′ and Rz⊆Rz′.z \sqsubseteq z' \iff F_z \subseteq F_{z'},\ B_z \subseteq B_{z'},\ L_z \subseteq L_{z'} \text{ and } R_z \subseteq R_{z'}.(4)✦

Recognizers

A diagram recognizer of ΣH*\LH\Sigma_H^* \setminus L_H on mm labels is a map τ:ΣH*→𝒯m\tau \colon \Sigma_H^* \to \mathcal{T}_m with τ(uv)=τ(u)τ(v)\tau(uv) = \tau(u)\tau(v) for all words uu and vv, together with diagrams λ,ρ∈𝒯m\lambda, \rho \in \mathcal{T}_m and labels α\alpha and β\beta, such that for every word ww over ΣH\Sigma_H (α,β)∈Fλτ(w)ρ⇔r(w)=∅.(\alpha, \beta) \in F_{\lambda \tau(w) \rho} \iff r(w) = \emptyset.(5)

The Claim

Theorem 1. Let HH be a set.

  1. For every word ww over ΣH\Sigma_H and all p,q∈Hp, q \in H, r(I{p}wI{q})≠∅⇔(p,q)∈r(w).r(I_{\{p\}}\, w\, I_{\{q\}}) \neq \emptyset \iff (p, q) \in r(w).(6)✦

  2. Let mm be a natural number and let τ\tau, λ\lambda, ρ\rho, α\alpha, β\beta be a diagram recognizer of ΣH*\LH\Sigma_H^* \setminus L_H on mm labels. For all words uu and vv over ΣH\Sigma_H with τ(u)⊑τ(v)\tau(u) \sqsubseteq \tau(v), r(v)⊆r(u).r(v) \subseteq r(u).(7)✦

  3. If moreover τ(ε)=1m\tau(\varepsilon) = 1_m, there are a submonoid SS of 𝒯m\mathcal{T}_m and a surjective monoid homomorphism φ:S→ℛH\varphi \colon S \to \mathcal{R}_H such that for all z,z′∈Sz, z' \in S z⊑z′⟹φ(z′)⊆φ(z).z \sqsubseteq z' \implies \varphi(z') \subseteq \varphi(z).(8)✦

  4. If moreover τ(ε)=1m\tau(\varepsilon) = 1_m, m≥1m \ge 1 and HH has h≥2h \ge 2 elements, then D(h)≤2m.D(h) \le 2m.(9)✦

In the paper, the result reads: if HH is finite with at least two elements and an ss-state 2NFA recognizes ΣH*\LH\Sigma_H^* \setminus L_H, then a submonoid of 𝒯s+1\mathcal{T}_{s+1} admits a surjective unital homomorphism φ\varphi onto ℛH\mathcal{R}_H with z⊑z′z \sqsubseteq z' implying φ(z′)⊆φ(z)\varphi(z') \subseteq \varphi(z).

The box states this for a diagram recognizer on mm labels in place of the automaton, with mm in the role of s+1s + 1.

What Is Checked

The claim is stated over the relation monoid ℛH\mathcal{R}_H with relation products of words and restricted identities, the monoid 𝒯m\mathcal{T}_m of diagrams with the product (3), the identity diagram 1m1_m and edge inclusion (4), diagram recognizers (5) and the loss bound (2).