OctoInformBeta

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

§2.1 (setting): the diagram monoid 𝒯_m and edge inclusion: Diagrams of four boundary relations have an associative product with a two-sided identity; reflection reverses products and products preserve edge inclusion ⊑\sqsubseteq

Boundary diagrams on mm labels form a monoid.

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

A two-way automaton running on a word may visit a factor of the word many times, entering across either of the factor’s two boundaries and leaving across either. Its behaviour on the factor relates entries to exits, and the behaviour on a concatenation uvuv comes from the behaviours on uu and on vv: a visit to uvuv may cross the boundary between uu and vv back and forth any number of times before it leaves.

Diagrams are these behaviours in the abstract, with entries and exits marked by mm labels. The item is the monoid 𝒯m\mathcal{T}_m they form under the product modelled on concatenation, together with two pieces of structure on it: reflection, which mirrors a diagram, and edge inclusion.

Diagrams and Their Product

Fix a set of mm labels and two copies D+D^+ and D−D^- of it: positive labels mark crossings to the right, negative labels crossings to the left. A diagram aa on mm labels is a quadruple of relations Fa⊆D+×D+,Ba⊆D−×D−,La⊆D+×D−,Ra⊆D−×D+,F_a \subseteq D^+ \times D^+, \qquad B_a \subseteq D^- \times D^-, \qquad L_a \subseteq D^+ \times D^-, \qquad R_a \subseteq D^- \times D^+,(1)✦ the forward, backward, left and right relations of aa, whose pairs 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.

Relations compose in path order: for P⊆X×YP \subseteq X \times Y and Q⊆Y×ZQ \subseteq Y \times Z, the product PQ⊆X×ZPQ \subseteq X \times Z holds (x,z)(x,z) when (x,y)∈P(x,y) \in P and (y,z)∈Q(y,z) \in Q for some y∈Yy \in Y. The reflexive transitive closure P*P^* of a relation PP on a set XX is the relation on XX P*=⋃k≥0Pk,P^* = \bigcup_{k \ge 0} P^k,(2)✦ where P0=IXP^0 = I_X is the identity relation on XX and Pk+1=PkPP^{k+1} = P^k P.

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)✦

The identity diagram 1m1_m is the diagram on mm labels with F1m=ID+,B1m=ID−,L1m=R1m=⌀.F_{1_m} = I_{D^+}, \qquad B_{1_m} = I_{D^-}, \qquad L_{1_m} = R_{1_m} = \varnothing.(4)✦

The reflection ρ(a)\rho(a) of a diagram aa on mm labels is the diagram on mm labels with Fρ(a)=Ba,Bρ(a)=Fa,Lρ(a)=Ra,Rρ(a)=La,F_{\rho(a)} = B_a, \qquad B_{\rho(a)} = F_a, \qquad L_{\rho(a)} = R_a, \qquad R_{\rho(a)} = L_a,(5)✦ where a label of D+D^+ stands for the label of D−D^- of the same name, and conversely.

Edge inclusion ⊑\sqsubseteq is the relation on diagrams on mm labels in which a⊑ba \sqsubseteq b when Fa⊆Fb,Ba⊆Bb,La⊆Lb,Ra⊆Rb.F_a \subseteq F_b, \qquad B_a \subseteq B_b, \qquad L_a \subseteq L_b, \qquad R_a \subseteq R_b.(6)✦

The Claim

Definition 1 (The diagram monoid 𝒯m\mathcal{T}_m). The diagram monoid 𝒯m\mathcal{T}_m is the set of diagrams on mm labels with the product (3) and the identity diagram 1m1_m. For diagrams aa, bb and cc on mm labels, the product is associative, (ab)c=a(bc),(ab)c = a(bc),(7)✦ the identity diagram is a unit on the left, 1ma=a,1_m\,a = a,(8)✦ and on the right, a1m=a,a\,1_m = a,(9)✦ and reflection reverses products, ρ(ab)=ρ(b)ρ(a).\rho(ab) = \rho(b)\,\rho(a).(10)✦ If aa, a′a', bb and b′b' are diagrams on mm labels with a⊑a′a \sqsubseteq a' and b⊑b′b \sqsubseteq b', then ab⊑a′b′.ab \sqsubseteq a'b'.(11)✦

In the paper, the result reads: a diagram aa is four relations Fa⊆D+×D+F_a \subseteq D^+ \times D^+, Ba⊆D−×D−B_a \subseteq D^- \times D^-, La⊆D+×D−L_a \subseteq D^+ \times D^- and Ra⊆D−×D+R_a \subseteq D^- \times D^+ on disjoint label sets D+D^+ and D−D^- of size mm; the product is given by the four formulas (2.2); the identity has FF and BB the identity and LL and RR empty; these diagrams form a finite monoid 𝒯m\mathcal{T}_m; a⊑ba \sqsubseteq b is componentwise inclusion and is preserved by products; and reflection exchanges FF with BB and LL with RR and reverses products.

What Is Checked

The claim is stated over diagrams on mm labels (1), their product (3) with the reflexive transitive closure (2), the identity diagram (4), reflection (5) and edge inclusion (6).