A
D
V
E
R
T

I
S
E
M
E
N
T

LEVEL 2 OF 2 · Exponential state costs for two-way automata

An exponential two-way deterministic state lower bound for one-way liveness

expertly designed by an internal OpenAI model · released 2026-09-25 · original PDF

Theorems: 3	Lemmas: 7	Proofs: 13
Formulas: 754	Words: 9,069	Play time: ~1 hour

>>> How to Play <<<

One-way liveness on h points accepts a word of binary relations when their ordered product is nonempty. For every h ≥ 2, it has a nondeterministic automaton with $h+3$ states and no left moves, whereas every equivalent s-state two-way deterministic automaton satisfies $4(s+2)^2\ge2^{\lfloor(h-2)/31\rfloor}$. Partial transition rules, stay moves, and nonaccepting infinite computations are allowed. The alphabets are finite and grow with h, so the result rules out an alphabet-independent polynomial state bound for deterministic two-way simulation, already for one-way nondeterministic sources.

>>> Level Map <<<

Introduction
Model and statement
Proof architecture
Related results
Matching and relation corners
Matching diagrams, rank, and support
Reduction at an idempotent
Homomorphic images and permutation lifts
Corners of the relation monoid
An exponential rank-loss bound
Local matching representation of deterministic machines
A sink and its tree
Tours determined by cyclic orders
Cell diagrams and their composition
From relation products to the state lower bound

Introduction

Two-way deterministic automata recognize the same languages as one-way finite automata, as established by Rabin and Scott and by Shepherdson (Rabin and Scott 1959; Shepherdson 1959). Allowing the head to return to a symbol can nevertheless change the amount of finite control needed to recognize a language. How much finite control is needed to replace nondeterministic choices by deterministic head motion? Sakoda and Sipser posed the state cost of converting one-way and two-way nondeterministic finite automata to two-way deterministic automata in 1978 (Sakoda and Sipser 1978). The question concerns succinctness: the simulator may revisit the input, but must store all information other than the head position in its finite state. A polynomial simulation would make nondeterminism inexpensive in this measure even when the source machine itself moves in both directions.

The witness used here is Sakoda and Sipser’s complete family $B_h$, now called one-way liveness: each letter specifies a binary relation on an $h$-element set, and a word is live when the product of its letters is nonempty. Their Theorem 2.3 establishes this family’s completeness for one-way-nondeterministic to two-way-deterministic state conversion (Sakoda and Sipser 1978). Our proof below gives the small source automaton and the context-separation property directly, with the conventions and exact state counts used here.

Earlier exponential lower bounds restrict the motion of the deterministic target. Sipser proved an exponential separation for sweeping automata, whose head changes direction only at an endmarker (Sipser 1980b). Kapoutsis extended this phenomenon to deterministic machines constrained to make sublinearly many reversals as a function of input length (Kapoutsis 2013). An unrestricted target can instead reverse at an interior cell and make arbitrarily many reversals as the input length grows.

Quadratic lower bounds against unrestricted two-way deterministic targets already occur in Chrobak’s work on unary languages (Chrobak 1986, 2003). For the promise restriction of one-way liveness to words of exactly three relation letters, Kapoutsis proved the optimal order $\Theta(h^2/\log h)$ (Kapoutsis 2018); the alphabet there is still the full relation alphabet. Adeogun and Kapoutsis (Adeogun and C. Kapoutsis 2026) prove a quadratic lower bound for unrestricted deterministic two-way automata against one-way liveness. We prove an exponential bound for that unrestricted target model. The source automata use no left moves, whereas the lower bound permits stay moves, partial transition rules, and nonaccepting infinite computations in the target.

The main representation difficulty is to account for repeated visits to a cell while assigning each input symbol a fixed object independent of its neighbors. We use the Brauer diagram monoid, whose matchings underlie Brauer’s algebras (Brauer 1937; Auinger 2012): its elements are perfect matchings on two equally sized sets of ports, and multiplication glues the adjoining sets and contracts paths. Determinism makes the configurations reaching a designated accepting sink form a tree. A tour of that tree gives the required matching representation, with separate leaves for unused transition candidates ensuring that each cell’s wiring depends only on its own symbol. The algebraic part then proves an exponential lower bound on the number of ports whenever matching products retain all the information in arbitrary relation products. All diagram and relation-monoid facts needed for this argument are proved below.

Model and statement

An automaton has a finite state set and one read-only head on a finite word over an alphabet $\Sigma$, bracketed by two distinct endmarkers outside $\Sigma$. Its head starts at the left endmarker in a designated initial state. A transition changes the state and moves the head left, right, or not at all; the head cannot cross an endmarker. A transition depends only on the current state and scanned symbol. Deterministic transition rules may be partial. A nondeterministic rule permits several successors. There are no additional heads, writable cells, work tapes, advice, or randomness. All states, including initial and accepting states, are counted.

Acceptance means that a finite computation reaches an accepting state; a nonaccepting infinite computation rejects. We initially count an accepting initial configuration as success. If success instead requires a positive transition into an accepting state, the normalization in Section 4 uses one additional initial copy. The main bound below includes this extra state and holds with either convention.

For a finite set $H$, let $\mathcal R_{H}$ be the monoid of all binary relations on $H$. Products are in path order from left to right: \[(x,z)\in AB \quad\Longleftrightarrow\quad \text{there exists }y\in H\text{ with }(x,y)\in A,\ (y,z)\in B.\] Write $I_{F}=\{(x,x):x\in F\}$ for $F\subseteq H$; the identity is $I_{H}$ and the zero is the empty relation $0$. For $H=[h]$ define \[ \mathsf{OWL}_h=\{R_1\cdots R_\ell\in(\mathcal R_{[h]})^*: R_1\cdots R_\ell\ne0\}. \tag{1}\] The product of the empty word is $I_{[h]}$, so $\varepsilon\in\mathsf{OWL}_h$.

Theorem 1. For every integer $h\ge2$, the language $\mathsf{OWL}_h$ is recognized by a nondeterministic automaton with $h+3$ states using no left moves. Every equivalent deterministic two-way automaton with $s$ states satisfies \[ 4(s+2)^2\ge 2^{\lfloor(h-2)/31\rfloor}. \tag{2}\] If an initially accepting configuration counts as acceptance, $s+2$ in (2) may be replaced by $s+1$.

Corollary 2. There are no absolute constants $C,c>0$ such that every $n$-state two-way nondeterministic automaton over every finite alphabet has an equivalent two-way deterministic automaton with at most $Cn^c$ states.

Proof. Put $n=h+3$ in Theorem 1. Every deterministic equivalent for this family has at least \[2^{\frac12\lfloor(n-5)/31\rfloor-1}-2\] states. This bound exceeds $Cn^c$ for every fixed $C,c$ when $n$ is large enough. For each $h$ the alphabet has $2^{h^2}$ symbols and is finite. Since the constants in the proposed simulation must be independent of the alphabet, the family is within its scope. ◻

Proof architecture

Write $\mathcal D_{k}$ for the matching monoid of degree $k$. The proof compares two bounds on $k$. Theorem 9 represents each $s$-state deterministic machine by symbol diagrams in $\mathcal D_{k}$, with $k\le4(s+2)^2$. For a machine recognizing $\mathsf{OWL}_h$, Lemma 13 gives a unital surjection from the submonoid generated by its ordinary-symbol diagrams onto $\mathcal R_{[h]}$. Concretely, the map sends each word diagram to its relation product, preserves multiplication and the empty product, and reaches every relation on $[h]$. These three properties, including the full image, are the algebraic input to the lower bound. Corollary 8 then forces $k\ge2^{\lfloor(h-2)/31\rfloor}$. These three statements give the deterministic lower bound in Theorem 1.

We prove the algebraic bound first. The rank of a matching diagram counts its pairs joining opposite sides. A diagram $e$ is idempotent if $e^2=e$; its corner consists of the diagrams $z$ with $ez=ze=z$, with identity $e$. Section 2 reduces the corner of an idempotent of rank $r$ to degree $r$, preserving rank and controlling the indices at which the diagram differs from the identity. An idempotent of rank $r$ in $\mathcal D_{k}$ differs from the identity on at most $2(k-r)$ indices. The support control is uniform: a family supported in one set remains supported in a single set of no greater size after reduction. Section 3 uses $32$ conjugates of one idempotent to make $256$ successive relation additions. A common support set bounds their total rank loss, while each addition yields a further corner representing all relations on $h-31$ points. Comparing these bounds doubles the required rank loss every $31$ points.

Section 4 obtains local symbol diagrams by converting acceptance to reachability of a designated sink. Its undirected component is a tree, whose doubled tour supplies the matching test. This traversal has precedents in Sipser’s halting method and in the reversible simulation of Lange, McKenzie, and Tapp (Sipser 1980a; Lange et al. 2000). Candidate transition slots completed by separate leaves make the construction independent of neighboring symbols. Finally, Section 5 obtains the quotient by using singleton-identity context letters to test each pair in a relation product. No input-length or running-time bound is imposed.

Matching and relation corners

We first establish the algebraic properties used in the rank argument. All monoid products in this paper are in path order: in a product $ab$, the factor $a$ is placed to the left of the factor $b$. A homomorphism is called unital when it preserves the designated identities.

Matching diagrams, rank, and support

For an integer $m\geq 0$, let $[m]=\{1,\ldots,m\}$, with $[0]=\varnothing$. A matching diagram of degree $m$ is a perfect matching on two disjoint sets of ports, a left set and a right set, each indexed by $[m]$. Only the paired ports matter; crossings in a drawing have no significance. Let $\mathcal D_{m}$ be the set of these diagrams.

To multiply $a,b\in\mathcal D_{m}$, identify the right port indexed $i$ of $a$ with the left port indexed $i$ of $b$, for every $i\in[m]$. In the resulting finite multigraph, each outside port has degree one and each identified port has degree two. Thus every component meeting an outside port is a path with two outside endpoints. Pair these endpoints and discard the components without outside ports. The result is $ab$. Parallel edges, when they occur at the interface, are counted separately.

This multiplication is associative. Indeed, in any string of glued diagrams, a substring can be replaced by the matching of its boundary endpoints: each path through the substring is replaced by one edge with the same endpoints. This preserves the connections between the outer ports of the whole string. Components internal to the substring have no connection to those ports. Contracting the first or the last two factors in a string of three therefore gives the same outside matching. The diagram $\mathbf 1_m$ pairing each left port $i$ with right port $i$ is an identity. In particular, $\mathcal D_{0}=\{\mathbf 1_0\}$ is the one-element monoid. The monoids $\mathcal D_{m}$ are the Brauer diagram monoids, whose matchings underlie Brauer’s algebras (Brauer 1937). Their semigroup structure and transversal rank have been studied in particular by Auinger and by East and Gray (Auinger 2012; East and Gray 2017).

A pair joining opposite sides is a transversal; a pair on one side is a cap. Write $\mathop{\mathrm{rank}}(a)$ for the number of transversals of $a$, and define \[\mathop{\mathrm{supp}}(a)=\{i\in[m]: \text{$a$ does not pair left $i$ with right $i$}\}.\] We say that $a$ is supported in $J\subseteq[m]$ if $\mathop{\mathrm{supp}}(a)\subseteq J$.

Lemma 3 (Rank and support). For $a,b\in\mathcal D_{m}$, \[\mathop{\mathrm{rank}}(ab)\leq \min\{\mathop{\mathrm{rank}}(a),\mathop{\mathrm{rank}}(b)\}, \qquad m-\mathop{\mathrm{rank}}(a)\leq |\mathop{\mathrm{supp}}(a)|.\] The units of $\mathcal D_{m}$ are exactly its rank-$m$ diagrams, which are the permutation diagrams. The only rank-$m$ idempotent is $\mathbf 1_m$. Conjugation by a permutation diagram preserves rank. For every $J\subseteq[m]$, the diagrams supported in $J$ form a submonoid of $\mathcal D_{m}$.

Proof. Each transversal path in the product uses a transversal of $a$ and a transversal of $b$. Different product paths are disjoint, so they use distinct transversals of either factor. This proves the rank inequality. Every index outside $\mathop{\mathrm{supp}}(a)$ supplies a fixed transversal, proving the support inequality.

A rank-$m$ diagram is a bijection between its two sides and has the inverse permutation diagram as a two-sided inverse. Conversely, the rank inequality forces every unit to have rank $m$. An idempotent in a group is its identity, proving the assertion about idempotents. If $u$ is a permutation diagram, the rank inequality gives $\mathop{\mathrm{rank}}(uau^{-1})\leq\mathop{\mathrm{rank}}(a)$; applying it to $a=u^{-1}(uau^{-1})u$ gives the reverse inequality.

If both $a$ and $b$ fix the transversal at an index $i$, their product also fixes it. Hence any product of diagrams supported in $J$ is supported in $J$, and $\mathbf 1_m$ is supported in every such set. ◻

Reduction at an idempotent

If $e^2=e$ in a monoid and $S$ is a subset closed under multiplication and containing $e$, its corner \[eSe=\{ese:s\in S\}\] is a monoid with identity $e$. In particular, every $z\in eSe$ satisfies $ez=ze=z$. This is the standard local-monoid construction of finite-semigroup theory (Pin 1997, sec. 2.7). For $m\ge3$, Auinger observes that the corner of the standard rank-$(m-2)$ projection in $\mathcal D_{m}$ is isomorphic to $\mathcal D_{m-2}$ (Auinger 2012, sec. 3). The following reduction treats an arbitrary idempotent and realizes its matching corner on fewer ports. Its third part controls one common support set for an entire family of sandwiches.

Lemma 4 (Matching corners). Let $e\in\mathcal D_{m}$ be idempotent and let $r=\mathop{\mathrm{rank}}(e)$.

There is a unital injective homomorphism \[R_e:e\mathcal D_{m}e\longrightarrow\mathcal D_{r}\] satisfying $\mathop{\mathrm{rank}}(R_e(z))=\mathop{\mathrm{rank}}(z)$ for all $z\in e\mathcal D_{m}e$.
The idempotent satisfies \[|\mathop{\mathrm{supp}}(e)|\leq 2(m-r).\]
For every $J\subseteq[m]$ there is a set $J'\subseteq[r]$, depending only on $e$, $J$, and the numbering chosen for $R_e$, such that $|J'|\leq |J|$ and \[\mathop{\mathrm{supp}}(R_e(eae))\subseteq J' \quad\text{for every $a\in\mathcal D_{m}$ supported in $J$}.\]

Proof. Let $X,Y\subseteq[m]$ be the indices of the left and right transversal endpoints of $e$, respectively. Its transversals define a bijection $p:X\to Y$, with $|X|=|Y|=r$.

We describe the connector at the interface between two copies of $e$. Keep two distinct tagged rows of vertices, $R_i$ and $L_i$ for $i\in[m]$, and put an edge $R_iL_i$ between each matching pair of indices. On the $R$ row put the right caps of $e$, and on the $L$ row put the left caps of $e$. Thus the degree-one vertices are precisely \[\{R_y:y\in Y\}\ \cup\ \{L_x:x\in X\},\] and all other vertices have degree two. These tagged vertices remain distinct even when $X$ and $Y$ overlap. Pairing the endpoints of its paths, and discarding its closed components, gives a matching on the $2r$ displayed vertices.

This is exactly the connector encountered by the transversals in $e\mathbf 1_m e=e^2$. Since $\mathop{\mathrm{rank}}(e^2)=r$, all $r$ left transversal endpoints of the first copy must reach the right boundary of the second. Consequently the connector cannot pair two $R$ endpoints or two $L$ endpoints: it pairs $R_y$ with $L_{\gamma(y)}$ for a bijection $\gamma:Y\to X$. The path from an outer left endpoint $x\in X$ ends at the right endpoint $p(\gamma(p(x)))$. Equality $e^2=e$ gives \[p(\gamma(p(x)))=p(x), \qquad\text{hence}\qquad \gamma(p(x))=x.\] Thus $\gamma=p^{-1}$.

Every diagram $z\in e\mathcal D_{m}e$ contains the left caps of $e$ on its outer left side and the right caps of $e$ on its outer right side. Delete precisely these prescribed caps. The remaining ports are the left ports indexed by $X$ and the right ports indexed by $Y$, and they retain a perfect matching. In particular, any additional caps among these retained ports remain in the reduced diagram. Number $X$ by $[r]$ in any fixed way, and give the right endpoint $p(x)$ the same number as $x$. This defines $R_e(z)$.

Figure 1 illustrates the connector and the numbering for a rank-$2$ idempotent.

A rank-$2$ idempotent of degree $4$ and its reduction. In the left panel, the gray caps are prescribed and the colored transversals are retained. The connector paths are $R_1$–$L_1$ and $R_4$–$L_4$–$L_3$–$R_3$–$R_2$–$L_2$, giving $\gamma=p^{-1}$. Numbering left $x$ and right $p(x)$ alike yields $R_e(e)=\mathbf 1_2$. For a general corner element $z$, only the prescribed outer caps are deleted; every pair among retained ports, including caps, remains.

Restoring the prescribed caps and the original indices reconstructs $z$, so $R_e$ is injective. Only nontransversal pairs were deleted, so it preserves rank, and by construction $R_e(e)=\mathbf 1_r$. To check multiplication, let $z,w\in e\mathcal D_{m}e$. The fixed caps at their middle interface are the right caps and left caps of $e$. Their connector is therefore the one just computed: the retained right port $p(x)$ of $z$ is connected to the retained left port $x$ of $w$. In the reduced numbering these ports have the same index. Contracting the connector, including when the reduced diagrams have caps of their own, thus gives ordinary multiplication in $\mathcal D_{r}$. It follows that $R_e(zw)=R_e(z)R_e(w)$, proving (i).

For (ii), suppose that $i\in X\cap Y$. The vertices $R_i,L_i$ in the connector have no incident caps, so their edge $R_iL_i$ is an entire connector path. Hence $\gamma(i)=i$, and $\gamma=p^{-1}$ implies $p(i)=i$. Thus every index in $X\cap Y$ is fixed by $e$, and \[\mathop{\mathrm{supp}}(e)\subseteq([m]\setminus X)\cup([m]\setminus Y).\] Both complements have size $m-r$, which proves the bound.

For (iii), consider the full glued graph $e\mathbf 1_m e$, keeping the middle identity diagram explicit. Its transversal paths have the same outside endpoint pairs as $e$, and so are indexed by the $r$ numbers used in the reduction. Mark a transversal path if it uses any middle identity edge whose index belongs to $J$. Let $J'$ be the numbers of the marked paths. A transversal path may use several middle identity edges; the only counting fact needed is that different paths are disjoint. Each middle identity edge therefore marks at most one transversal path, and $|J'|\leq|J|$.

Now replace the middle identity by any diagram $a$ supported in $J$. Every middle identity edge at an index outside $J$ remains present. An unmarked transversal path used only such edges, so that entire path survives with the same outside endpoints. Each of its internal vertices still has its two original incident edges; a new path cannot attach to it. In particular, changes to closed components or to paths with both endpoints on the same side cannot join an unmarked transversal: all its middle ports are already paired by the unchanged identity edges. Its corresponding reduced port is therefore still paired with the equally indexed port on the other side. Only numbers in $J'$ can belong to $\mathop{\mathrm{supp}}(R_e(eae))$. The construction of $J'$ did not depend on $a$, as required.

When $r=0$, the prescribed caps exhaust all outside ports. Then $eae=e$ for every $a$, and the corner is identified with the singleton $\mathcal D_{0}$. The reduction above is its unique map, and (iii) holds with $J'=\varnothing$; (ii) also holds since $|\mathop{\mathrm{supp}}(e)|\leq m$. ◻

The reduction will also be applied to a submonoid $eSe$. We write $R_e(eSe)$ for its image in $\mathcal D_{r}$. It contains the ambient identity $\mathbf 1_r$. When discussing support in this reduced monoid, the port set is $[r]$; support in the original monoid still refers to $[m]$.

Homomorphic images and permutation lifts

Every element of a finite semigroup has an idempotent positive power. Indeed, for an element $x$ there are integers $a\geq1$ and $d\geq1$ such that $x^{k+d}=x^k$ for all $k\geq a$. Choose $N\geq a$ divisible by $d$. Then $x^{2N}=x^N$. If a multiplicative map sends $x$ to an idempotent $q$, the same is true of every positive power of $x$, including this idempotent power.

Lemma 5 (Unit lifts from a minimum-rank corner). Let $S\subseteq\mathcal D_{m}$ be nonempty and closed under multiplication, and let $\phi:S\to M$ be an onto multiplicative map to a monoid $M$. Let $q\in M$ be idempotent. There is an idempotent $e\in S$ with $\phi(e)=q$. For every such $e$, the reduced monoid $R_e(eSe)$ has a unital surjection \[\phi_e:R_e(eSe)\longrightarrow qMq, \qquad \phi_e(R_e(z))=\phi(z).\] If $e$ has minimum rank among all idempotents in $S$ mapping to $q$, then every element of $eSe$ mapping to a unit of $qMq$ reduces to a permutation diagram. In particular, every unit of $qMq$ has a permutation lift in $R_e(eSe)$, and that lift is a unit of the reduced monoid.

Proof. The sets $S$ and $M$ are finite because $\mathcal D_{m}$ is finite and $\phi$ is onto. Take any preimage of $q$ and then an idempotent positive power to obtain $e$. The image of $eSe$ under $\phi$ is exactly $qMq$: for any $v\in M$, a preimage $s\in S$ gives $\phi(ese)=qvq$. Its identity $e$ maps to the identity $q$ of this corner. Lemma 4(i) makes the displayed definition of $\phi_e$ well-defined and transfers both multiplication and surjectivity.

Suppose now that $e$ has the stated minimum rank, put $r=\mathop{\mathrm{rank}}(e)$, and let $y\in eSe$ map to a unit $u$ of $qMq$. The group of units of $qMq$ is finite, so $u^t=q$ for some positive integer $t$. Take an idempotent positive power $z$ of $y^t$. Then $z\in S$ is idempotent and $\phi(z)=q$. The rank inequalities and minimum choice of $e$ give \[r\leq\mathop{\mathrm{rank}}(z)\leq\mathop{\mathrm{rank}}(y)\leq r.\] The last inequality uses $y\in eSe$. Hence $R_e(y)$ has rank $r$ in $\mathcal D_{r}$ and is a permutation diagram. Its inverse is a power of the same finite-order permutation, so lies in $R_e(eSe)$. Surjectivity of $\phi_e$ supplies a lift for each unit $u$ and completes the proof. ◻

Corners of the relation monoid

For a finite set $H$ and a subset $F\subseteq H$, we regard a relation on $F$ as a relation on $H$ containing no pairs outside $F\times F$. With $i=I_{F}$, these are precisely the relations $A$ satisfying $A=iAi$. Under this identification their monoid is $i\mathcal R_{H}i$ with identity $i$. Permutations of a finite set are identified with their graph relations.

Lemma 6 (A relation corner). Let $P\in\mathcal R_{H}$ be idempotent, and let $F\subseteq H$ satisfy $I_{F}PI_{F}=I_{F}$. Put $i=I_{F}$ and $Q=PiP$. Then $Q$ is idempotent, $PQ=QP=Q$, and restriction is a unital isomorphism \[\theta:Q\mathcal R_{H}Q\longrightarrow\mathcal R_{F}, \qquad \theta(Z)=iZi.\] Its inverse sends $A\in\mathcal R_{F}$ to $PAP=QAQ$.

Proof. The identities $P^2=P$ and $iPi=i$ give \[Q^2=PiP^2iP=P(iPi)P=Q, \qquad PQ=QP=Q.\] They also give $iQ=iP$, $Qi=Pi$, and $iQi=i$. If $Z\in Q\mathcal R_{H}Q$, then $Z=QZQ$ and $PZP=Z$. Consequently \[Z=PiPZPiP=PiZiP. \tag{$*$}\] Thus its restriction $iZi$ determines $Z$ uniquely.

Conversely, if $A\in\mathcal R_{F}$, so that $A=iAi$, then \[QAQ=QiAiQ=PiAiP=PAP, \qquad i(PAP)i=iPiAiPi=A.\] Hence every relation on $F$ is a restriction of an element of the corner, and $A\mapsto PAP$ is the inverse bijection by $(*)$.

For multiplication, write $Z=PAP$ and $W=PBP$, where $A=iZi$ and $B=iWi$ are relations on $F$. Since $A=Ai$ and $B=iB$, we have \[ZW=PAP^2BP=PAPBP =PA(iPi)BP=PABP.\] Restricting this equality gives $\theta(ZW)=AB=\theta(Z)\theta(W)$. Finally, the identity $Q$ of the source corner restricts to $i$, the identity of $\mathcal R_{F}$. This proves unitality and the claimed isomorphism. ◻

An exponential rank-loss bound

We now bound the rank lost by an idempotent diagram whose image adds one off-diagonal pair to the identity relation. The amplification step uses $32$ conjugates of that diagram to construct $256$ successive relation additions. Their joint support bounds the total rank loss, while a smaller relation corner bounds the loss at each addition.

For every integer $h\ge2$, set \[ L(h)=2^{\lfloor(h-2)/31\rfloor}. \tag{3}\] All reductions below are the maps $R_e$ of Lemma 4. Their ranges are regarded as submonoids of the indicated smaller matching monoids. In particular, their identities are the ambient identity diagrams, and they preserve absolute rank.

The theorem first assumes permutation lifts in addition to a unital surjection onto the entire relation monoid. A surjection onto only the relations generated by the displayed additions would not suffice: the proof must also lift arbitrary elements of smaller relation corners. Corollary 8 removes the extra lift assumption by passing to a minimum-rank idempotent corner.

Theorem 7 (Rank loss for a single relation addition). Let $H$ be a finite set of size $h\ge2$, let $m\ge0$, and let $S\subseteq\mathcal D_{m}$ be a submonoid containing $\mathbf 1$. Suppose that $\phi:S\to\mathcal R_{H}$ is a unital surjection and that every permutation of $H$ has a lift in $S$ which is a permutation diagram. If $a\in S$ is idempotent and \[\phi(a)=I_{H}\cup\{(x,y)\},\qquad x,y\in H,\quad x\ne y,\] then \[m-\mathop{\mathrm{rank}}(a)\ge L(h).\]

Proof. We induct on $h$, simultaneously for every ambient degree $m$ and every choice of $S,\phi,a$ satisfying the hypotheses. Put $t=16$. For $2\le h<2t+1=33$, one has $L(h)=1$. A full-rank diagram is a permutation, and an idempotent permutation is the identity. Since $\phi$ is unital and $\phi(a)\ne I_{H}$, the rank of $a$ is strictly smaller than $m$. This proves the base cases.

Now let $h\ge33$ and assume the theorem for every smaller size at least two. Write \[c=m-\mathop{\mathrm{rank}}(a).\]

Conjugates with a common support bound.

Choose pairwise disjoint sets \[U=\{u_1,\ldots,u_t\},\qquad V=\{v_1,\ldots,v_t\},\qquad \{z\}\] in $H$. For each ordered pair of distinct points of $H$, a permutation $\pi$ can send $(x,y)$ to that pair. Choose a permutation-diagram lift $\widetilde\pi\in S$. Its inverse belongs to $S$ because a permutation diagram has finite order. In path order, \[\phi(\widetilde\pi^{-1}a\widetilde\pi) =\pi^{-1}\bigl(I_{H}\cup\{(x,y)\}\bigr)\pi =I_{H}\cup\{(\pi(x),\pi(y))\}.\] Using the pairs $(u_i,z)$ and $(z,v_j)$ in this construction gives idempotents $s_i,s'_j\in S$ such that \[ \phi(s_i)=I_{H}\cup\{(u_i,z)\},\qquad \phi(s'_j)=I_{H}\cup\{(z,v_j)\} \quad(1\le i,j\le t). \tag{4}\] Conjugation by permutation diagrams preserves rank, so all these idempotents have rank $m-c$. By Lemma 4(ii), each has support of size at most $2c$. Thus the set \[J=\bigcup_{i=1}^{t}\mathop{\mathrm{supp}}(s_i) \ \cup\ \bigcup_{j=1}^{t}\mathop{\mathrm{supp}}(s'_j) \subseteq[m]\] has size at most $4tc$. Every product $s_i s'_j$ is supported in $J$, because diagrams supported in a fixed set form a submonoid.

A chain of $t^2$ additions.

Put $P_0=I_{H\setminus\{z\}}$. Choose an idempotent $b_0\in S$ with $\phi(b_0)=P_0$: take any lift of $P_0$ and then a positive idempotent power. The image stays $P_0$ because $P_0$ is idempotent. For $1\le i,j\le t$, define \[g_{ij}=b_0s_i s'_j b_0\in b_0Sb_0.\] In path order, the two added pairs in (4) allow the path $u_i,z,v_j$. The outer factors $P_0$ delete pairs with endpoint $z$, so \[ \phi(g_{ij})=P_0\cup\{(u_i,v_j)\}. \tag{5}\] Figure 2 shows how the same $2t$ conjugates provide all $t^2$ choices of the pair $(u_i,v_j)$.

The gray arrows are alternatives from the two families of relation images; each individual image has one added arrow. The highlighted path creates the selected pair after both outer factors delete endpoints at $z$. Identity loops are omitted. Only relations on $H$ are shown. The common matching support bound comes from taking the union of the supports of the $32$ conjugates and reducing at $b_0$; the same conjugates provide all $256$ choices.

Let $r_0=\mathop{\mathrm{rank}}(b_0)$. Applying Lemma 4(iii) at $b_0$ to the single set $J$ gives one set $J_0\subseteq[r_0]$, with $|J_0|\le4tc$, such that \[ \mathop{\mathrm{supp}}\bigl(R_{b_0}(g_{ij})\bigr)\subseteq J_0 \qquad(1\le i,j\le t). \tag{6}\] This set is common to all $t^2$ generators.

List the pairs $(i,j)\in[t]\times[t]$ in any order, without repetition. Let $E_\ell$ be the set of relation pairs $(u_i,v_j)$ in the first $\ell$ positions, and set \[P_\ell=P_0\cup E_\ell\qquad(0\le\ell\le t^2).\] All additional pairs go from $U$ to $V$, and $U\cap V=\varnothing$. Consequently two additional pairs cannot be composed with each other; the identity pairs in $P_0$ preserve their endpoints. Thus \[ (P_0\cup A)(P_0\cup B)=P_0\cup(A\cup B) \qquad(A,B\subseteq U\times V). \tag{7}\] In particular, $P_\ell^2=P_\ell$.

Starting from $b_0$, construct $b_\ell$ as follows. If $(i,j)$ occupies position $\ell$, take $b_\ell$ to be a positive idempotent power of \[b_{\ell-1}g_{ij}b_{\ell-1}.\] Inductively, its image before taking the power is $P_\ell$, by (5) and (7); the power has the same image. Hence \[ b_\ell^2=b_\ell,\qquad b_\ell\in b_{\ell-1}Sb_{\ell-1},\qquad \phi(b_\ell)=P_\ell. \tag{8}\] Every $b_\ell$ also belongs to $b_0Sb_0$. Indeed, this is true initially, and this latter set is a submonoid containing every $g_{ij}$; it is therefore preserved by the construction.

Write \[r_\ell=\mathop{\mathrm{rank}}(b_\ell)\quad(0\le\ell\le t^2), \qquad \Delta_\ell=r_{\ell-1}-r_\ell\quad(1\le\ell\le t^2).\] The nested corners in (8) and Lemma 3 give $\Delta_\ell\ge0$. In the single coordinate system obtained by reducing at $b_0$, the starting element is the identity and all generators are supported in $J_0$ by (6). The same is true of every constructed product and power, in particular $R_{b_0}(b_{t^2})$. Rank preservation and the elementary bound of rank defect by support size give \[ \sum_{\ell=1}^{t^2}\Delta_\ell =r_0-r_{t^2} \le\bigl|\mathop{\mathrm{supp}}(R_{b_0}(b_{t^2}))\bigr| \le|J_0|\le4tc. \tag{9}\]

The loss at one addition.

We claim that for every $1\le\ell\le t^2$, \[ 2\Delta_\ell\ge L(h-2t+1). \tag{10}\] Each local argument uses fresh port coordinates to certify this bound on the already defined absolute rank difference $\Delta_\ell$ in (9). Fix $\ell$, let $(i,j)$ be its pair, and put $P=P_{\ell-1}$. Reduce at $b_{\ell-1}$ and define \[T=R_{b_{\ell-1}}(b_{\ell-1}Sb_{\ell-1}) \subseteq\mathcal D_{r_{\ell-1}},\qquad \beta=R_{b_{\ell-1}}(b_\ell)\in T.\] Here $T$ contains the ambient identity $R_{b_{\ell-1}}(b_{\ell-1})=\mathbf 1$. The unital-surjection assertion of Lemma 5 gives \[\theta:T\longrightarrow P\mathcal R_{H}P, \qquad \theta(R_{b_{\ell-1}}(w))=\phi(w) \quad(w\in b_{\ell-1}Sb_{\ell-1}).\] Moreover, $\beta$ is idempotent, $\theta(\beta)=P_\ell$, and rank preservation gives \[ \mathop{\mathrm{rank}}(\beta)=r_\ell, \qquad |\mathop{\mathrm{supp}}(\beta)|\le2\Delta_\ell, \tag{11}\] where support now refers to the indices $[r_{\ell-1}]$.

A full relation corner on fewer points.

Set \[F=\{u_i,v_j\}\cup\bigl(H\setminus(U\cup V\cup\{z\})\bigr), \qquad E=I_{F},\qquad Q=PEP.\] Thus $|F|=h-2t+1=h-31$. Among the possible extra pairs in $P$, the only one with both endpoints in $F$ is $(u_i,v_j)$, which has not yet been added. Every point of $F$ is different from $z$. Therefore \[EPE=E.\] Lemma 6 shows that $Q$ is idempotent, $PQ=QP=Q$, and restriction $Z\mapsto EZE$ is a unital isomorphism from $Q\mathcal R_{H}Q$ onto $\mathcal R_{F}$. In particular, \[Q(P\mathcal R_{H}P)Q=Q\mathcal R_{H}Q.\] Equation (7) also gives $PP_\ell=P_\ell P=P_\ell$. Since $EQ=EP$ and $QE=PE$, we obtain \[ E(QP_\ell Q)E =EP P_\ell PE =EP_\ell E =I_{F}\cup\{(u_i,v_j)\}. \tag{12}\]

The second reduction and the induction hypotheses.

Among the idempotents $d\in T$ with $\theta(d)=Q$, choose one of minimum rank. Such idempotents exist because $\theta$ is onto and an idempotent power of a lift of $Q$ still maps to $Q$. This minimum is taken inside $T$, in its current coordinates in $\mathcal D_{r_{\ell-1}}$. Put $r'=\mathop{\mathrm{rank}}(d)$ and reduce once more, defining \[T'=R_d(dTd)\subseteq\mathcal D_{r'}.\] The identity of $T'$ is $R_d(d)=\mathbf 1$. Its induced map onto $Q(P\mathcal R_{H}P)Q$, followed by restriction to $F$, is the unital surjection \[\psi:T'\longrightarrow\mathcal R_{F},\qquad \psi(R_d(w))=E\theta(w)E\quad(w\in dTd).\] By Lemma 5 and the minimum-rank choice of $d$, every unit of $Q(P\mathcal R_{H}P)Q$ has a permutation-diagram lift in $T'$. The restriction isomorphism preserves units, so every permutation of $F$ has such a lift under $\psi$.

Let $J_\ell=\mathop{\mathrm{supp}}(\beta)\subseteq[r_{\ell-1}]$. Apply Lemma 4(iii) to the idempotent $d$ in this ambient matching monoid. There is a set $K\subseteq[r']$ with $|K|\le|J_\ell|\le2\Delta_\ell$ such that \[\mathop{\mathrm{supp}}\bigl(R_d(d\beta d)\bigr)\subseteq K.\] The sandwich $d\beta d$ need not be idempotent. Choose a positive idempotent power $v$ of its reduction $R_d(d\beta d)$ in $T'$. Support remains in $K$ under taking powers. By (12), the image before taking the power is $I_{F}\cup\{(u_i,v_j)\}$, an idempotent relation; hence \[v^2=v, \qquad \psi(v)=I_{F}\cup\{(u_i,v_j)\}, \qquad |\mathop{\mathrm{supp}}(v)|\le2\Delta_\ell.\] We have obtained an identity-containing submonoid of $\mathcal D_{r'}$, a unital surjection onto $\mathcal R_{F}$ with permutation lifts, and the required idempotent above a single off-diagonal addition. These are all the hypotheses of the theorem at size $|F|=h-31$, which lies between $2$ and $h-1$. The induction hypothesis and the support bound therefore give \[L(h-31)\le r'-\mathop{\mathrm{rank}}(v) \le|\mathop{\mathrm{supp}}(v)|\le2\Delta_\ell.\] This proves (10) for the chosen $\ell$, and hence for every step of the chain.

Completion of the recurrence.

The bounds established above are collected in Table 1. The support is measured once, in the coordinates of $b_0$; the separate smaller corners certify each summand in the resulting rank-loss budget.

The support upper bound and the inductive rank-loss lower bound are applied to the same chain. Here $c=m-\mathop{\mathrm{rank}}(a)$.
Quantity	General expression	$t=16$
Conjugates	$2t$	$32$
Successive additions	$t^2$	$256$
Common support budget	$4tc$	$64c$
Retained relation points	$h-2t+1$	$h-31$
Loss per addition	$\frac12L(h-2t+1)$	$\frac12L(h-31)$
Total required loss	$\frac{t^2}{2}L(h-2t+1)$	$128L(h-31)$

Summing (10) and applying (9) yields \[4tc\ge\sum_{\ell=1}^{t^2}\Delta_\ell \ge\frac{t^2}{2}L(h-2t+1).\] With $t=16$, it follows that \[c\ge2L(h-31) =2^{1+\lfloor(h-33)/31\rfloor} =2^{\lfloor(h-2)/31\rfloor} =L(h).\] This completes the induction. ◻

Corollary 8 (Degree bound for a unital relation-monoid divisor). Let $H$ be a finite set of size $h\ge2$. If an identity-containing submonoid $S\subseteq\mathcal D_{k}$ admits a unital surjection $\phi:S\to\mathcal R_{H}$, then \[k\ge L(h)=2^{\lfloor(h-2)/31\rfloor}.\] No hypothesis about permutation lifts is required here.

Proof. Choose an idempotent $e\in S$ of minimum rank among those with $\phi(e)=I_{H}$. The set of choices is nonempty, since the identity of $S$ is one such idempotent. Put $r=\mathop{\mathrm{rank}}(e)$. By Lemmas 4 and 5, the reduced corner \[T=R_e(eSe)\subseteq\mathcal D_{r}\] contains the ambient identity and maps unitally onto $I_{H}\mathcal R_{H}I_{H}=\mathcal R_{H}$. The minimum-rank choice supplies permutation-diagram lifts for all permutations of $H$.

Choose distinct $x,y\in H$. Surjectivity supplies a lift in $T$ of $I_{H}\cup\{(x,y)\}$. A positive idempotent power of that lift is an idempotent $a\in T$ with the same image. Theorem 7 applies to this representation, so \[L(h)\le r-\mathop{\mathrm{rank}}(a)\le r\le k.\qedhere\] ◻

Local matching representation of deterministic machines

Fix a finite alphabet $\Sigma$. We use one read-only head on an input $\vdash w\dashv$, where $w\in\Sigma^*$ and the two endmarkers are distinct symbols outside $\Sigma$. A deterministic machine has a finite state set $Q$, an initial state $q_0$, a set $A\subseteq Q$ of accepting states, and a partial transition function \[\delta:Q\times(\Sigma\cup\{\vdash,\dashv\}) \rightharpoonup Q\times\{-1,0,1\}.\] The three moves are left, stay, and right. A transition at an endmarker never moves beyond that endmarker. The initial configuration is $(0,q_0)$, with cell $0$ carrying $\vdash$. In this section a computation accepts when an accepting state occurs at any time, including time $0$. A missing transition halts the computation; an infinite computation without an accepting state rejects. All states, including initial and accepting states, count toward $s=|Q|$.

Theorem 9 (Local matching representation). For every $s$-state deterministic machine in this model, there is a map \[\eta:\Sigma\cup\{\vdash,\dashv\}\longrightarrow\mathcal D_{k}, \qquad k=4(s+1)^2,\] with the following property. Designate ports $1,2$ on each of the two sides as test ports. For every word $w=a_1\cdots a_\ell$, the machine accepts $w$ if and only if the diagram \[\eta(\vdash)\eta(a_1)\cdots\eta(a_\ell)\eta(\dashv)\] pairs a left test port with a right test port. Each symbol diagram is independent of the input length, the symbol’s position, and its neighboring symbols.

If acceptance instead requires entry into an accepting state after a positive number of transitions, the same conclusion holds with $k=4(s+2)^2$.

The diagrams will encode a tour of an undirected graph. Determinism is used to ensure that the component of one designated vertex is a tree; no condition is imposed on the other components. Configuration-tree traversal also underlies Sipser’s halting method (Sipser 1980a) and the reversible simulation of Lange, McKenzie, and Tapp (Lange et al. 2000, sec. 3.1). We prove the traversal facts needed here and then realize them by matching diagrams. The candidate-slot construction below supplies the further requirement that each diagram depend only on the symbol at its own cell, with the stated quadratic degree.

A sink and its tree

Lemma 10 (Sink component). Let $V$ be finite, let $\sigma:V\rightharpoonup V$ be a partial function, and let $t\in V$ have no successor. Make an undirected multigraph on $V$ with one edge for each defined successor $v\mapsto\sigma(v)$, retaining self-loops and distinct edges with the same endpoints. Then a vertex lies in the connected component of $t$ if and only if some finite sequence of successor steps takes it to $t$. This component is a tree.

Proof. Let $B$ be the set of vertices reaching $t$, allowing a sequence of length zero. For every successor edge $u\mapsto v$, one has $u\in B$ if and only if $v\in B$. One implication prepends that edge to a path to $t$; the other removes the first step of the unique successor path from $u$ to $t$. This removal is legitimate because $u\ne t$. Thus membership in $B$ is constant along undirected edges. Since $t\in B$, its entire component lies in $B$. Conversely, a successor path is an undirected path, so every element of $B$ belongs to that component.

If the component has $v$ vertices, each of its vertices other than $t$ has exactly one outgoing edge, and $t$ has none. All these edges stay in the component, and every edge in the component is counted once at its source. Hence the connected multigraph has $v-1$ edges and is a tree. In particular, it has neither self-loops nor parallel edges. ◻

To apply the lemma, add one new state $f$ to the machine and put $N=s+1$. This is an auxiliary successor rule for a reachability test, not a change in the language to be recognized. For every $b\in\Sigma\cup\{\vdash,\dashv\}$, define \[\widehat\delta(q,b)= \begin{cases} (f,0),&q\in A,\\ \delta(q,b),&q\in Q\setminus A,\\ (f,1),&q=f,\ b\ne\dashv,\\ \text{undefined},&q=f,\ b=\dashv. \end{cases}\] The first case applies even when the old transition was undefined. Only the rows at old nonaccepting states retain their old partial rules, including undefined entries.

For a fixed input of length $\ell$, let \[c_0=(0,q_0),\qquad t=(\ell+1,f).\] The original machine accepts precisely when the modified successor rule reaches $t$ from $c_0$. Indeed, the computations agree until the first accepting state, which now leads into $f$ and then to $t$. Conversely, the first entry into $f$ must come from an old accepting state. This also covers acceptance initially or on an endmarker. Let $G$ be the undirected successor multigraph on all configurations $(i,q)$, where $0\le i\le\ell+1$ and $q\in Q\cup\{f\}$. Lemma 10 shows that the component of $t$ is a tree, and that $c_0$ belongs to it exactly on accepted inputs. Nonaccepting cycles in other components require no further modification.

Tours determined by cyclic orders

An incidence of an edge at a vertex records its endpoint there. A loop has two incidences at its vertex. Choose a cyclic order of the incidences at every vertex of positive degree. Regard each edge as having two directed traversals. Upon arriving at a vertex along one incidence, depart along the next incidence in its cyclic order. At a vertex of degree one this means returning along the same edge.

Lemma 11 (Tree tour). For a finite tree with at least one edge, this rule has a single cycle on its directed edge traversals, for every choice of cyclic orders. If the two joins at two distinct leaves are opened, the resulting two paths each connect a tip at one leaf to a tip at the other.

Proof. The rule is a permutation of the directed traversals: a departure has exactly one preceding arrival, determined by the preceding incidence in the cyclic order. A tree consisting of one edge gives a cycle of its two traversals.

For the induction step, remove a leaf $z$ with neighbor $v$ from a tree with more than one edge. Restrict the cyclic order at $v$ by removing the incidence of $vz$. The smaller tree has one tour cycle by induction. Inserting $vz$ back into that order replaces one transition \[(u,v)\longmapsto(v,w)\] of the smaller tour by \[(u,v)\longmapsto(v,z)\longmapsto(z,v)\longmapsto(v,w).\] Here $u=w$ is allowed. No other transition changes. Thus two new traversals are inserted into the existing cycle, proving the first assertion.

Realize the tour as a circular wire, using one lane for each directed traversal and a join for each arrival-to-departure step. The joins at two different leaves are two different points on this circle. Opening both cuts the circle into two paths, each running between the two cuts. Each path consequently has one tip at each of the two leaves. ◻

Cell diagrams and their composition

Proof of Theorem 9. Use the modified successor rule with its $N=s+1$ states, numbered by $[N]$. We first augment its undirected graph by leaves so that each cell’s portion of the graph can be determined from that cell’s symbol alone.

Candidate edges at an internal boundary.

At every boundary between two neighboring cells, reserve one slot for each triple \[(d,p,q)\in\{\leftarrow,\rightarrow\}\times[N]\times[N].\] The direction $d$ specifies which cell is the prospective source and which is the prospective target. The slot represents a candidate transition from state $p$ in the source cell to state $q$ in the target cell. It carries two lane ports, labeled by the absolute directions of travel $\rightarrow$ and $\leftarrow$. These labels, together with $(d,p,q)$, give a fixed enumeration of the \[k=2\cdot N^2\cdot 2=4N^2\] ports on either side of a cell. Equal labels are identified when neighboring cell diagrams are multiplied.

For each slot put an undirected edge across the boundary. At its target end, always attach it to the target cell’s state vertex $q$. At its source end, attach it to state vertex $p$ if the modified transition from $p$ on the source cell’s symbol is exactly the transition specified by the slot. Otherwise attach that end to a new degree-one vertex in the source cell. Use a different new vertex for each unused slot.

Every actual crossing successor edge is represented once, in its own slot. Each other slot contributes a single leaf edge attached to a state vertex. Keep every actual stay edge inside its cell, with two distinct incidences when it is a loop. The resulting graph is therefore $G$ with additional leaves and leaf edges. It has the same connectivity between state vertices as $G$, and the component of $t$ is still a tree.

The target-end attachment makes the construction local: a target cell does not need to know whether its neighbor uses a slot. Every possible incoming slot is attached to its indicated state there. Only the source cell decides between its state vertex and a fresh leaf, using its own scanned symbol and successor rule. Figure 3 isolates this choice for one slot.

One candidate transition slot with $d=\rightarrow$, with its two travel lanes. The target end is always attached to state $q$. Only the source attachment changes: an actual transition uses state $p$, and an unused slot uses its own new leaf, adding no state-to-state connection. Thus the target cell needs no information about the source symbol. Other slots and local cyclic joins are omitted; lane arrows indicate traversal, not two machine transitions.

The two outward boundaries.

An ordinary cell has a neighbor on each side. The left-marker cell has only its right neighbor, and the right-marker cell only its left neighbor. Use candidate slots exactly on these inward boundaries. On the outward side of the left marker, instead attach a test edge from $c_0$ to a new outer leaf $z_L$. On the outward side of the right marker attach a test edge from $t$ to another new outer leaf $z_R$.

Each test edge has two lanes whose outer tips occupy ports $1,2$ of the corresponding outward side; the same indices serve as ordinary candidate-lane ports on internal sides. These tips will remain unjoined at the outer leaf. Pair the other outward ports as $(3,4),(5,6),\ldots,(k-1,k)$, independently of all graph edges. This uses all remaining ports because $k$ is even. Denote the graph including the two test leaves by $\widehat G$. Its component containing $t$ is a tree, and its two test leaves are connected if and only if the machine accepts.

Lanes and local joins.

Place two travel lanes on every edge of $\widehat G$, one in each direction of traversal. Each incidence consequently has an incoming tip and an outgoing tip. For an edge with incidences $i$ and $j$, its lanes connect the outgoing tip at $i$ to the incoming tip at $j$, and the outgoing tip at $j$ to the incoming tip at $i$. This prescription applies also to a loop, whose incidences are different even though their vertices coincide.

For a crossing edge, each half-lane ends at the corresponding boundary port. Absolute travel directions determine the following local correspondence: \[\begin{array}{c|cc} \text{side of the cell}&\rightarrow\text{ lane}&\leftarrow\text{ lane}\\ \hline \text{left}&\text{incoming tip}&\text{outgoing tip}\\ \text{right}&\text{outgoing tip}&\text{incoming tip} \end{array}\] Thus equal-index gluing connects an outgoing half-lane in one cell to an incoming half-lane in its neighbor, as required.

At every vertex other than $z_L,z_R$, choose a cyclic order of its incidences and join the incoming tip at each incidence to the outgoing tip at the next incidence. A leaf reflects one lane into the other; a vertex of degree zero requires no joins. Choose these orders separately for each symbol type and then use the same orders at every occurrence of that symbol. This is possible because all incidences are local: incoming crossing slots are always present, outgoing attachments depend only on the scanned symbol, and stay edges are internal. Marker incidences, including their test edges, are likewise fixed by marker type. Incidences can, for example, be ordered by their slot labels and their roles in internal edges.

Contracting one cell.

Inside a cell, every lane tip is incident with one lane and one local join. The only exposed ends are its boundary ports, each used exactly once, including the separately paired outward ports. Hence the finite wiring inside the cell has degree two at internal points and degree one at its ports. Every component containing a port is a path ending at exactly one other port. Discard components without ports and pair the two endpoints of each remaining path. The result is a perfect matching on the cell’s $2k$ ports, hence an element of $\mathcal D_{k}$. Let $\eta(a)$ be this matching for symbol $a$.

All preceding choices for one cell depend only on $a$, which proves the asserted symbol locality. Gluing cells with equal port indices reconstructs their full wiring. Contracting paths first within cells or only after gluing yields the same pairing of outside ports, by the definition of diagram multiplication. Consequently the whole-input diagram in the theorem is precisely the pairing obtained from the wires of $\widehat G$, with the two test-leaf joins omitted and the unused outward ports separately paired. Figure 4 shows the test-port part of this contraction in the accepted case.

The accepted case, restricted to the four test ports already exposed on the marker outward sides: $L_i$ and $R_i$ name port $i$ at the left and right. For the connected sink tree, Lemma 11 shows that restoring the dashed test-leaf reflections closes one tour cycle; opening them leaves two arcs, each joining the two sides. Contracting within cells before gluing or after gluing preserves these outside endpoints and their pairing. The displayed cross pairing is one possibility. Other ports, caps, and wire components of the degree-$k$ construction are omitted.

Reading acceptance.

If a wire pairs a left test port to a right test port, it travels only along edges and joins within one component of $\widehat G$. The separately paired outward ports are disconnected from these wires. Thus $z_L$ and $z_R$ lie in the same component, and the machine accepts.

Conversely, on an accepted input both test leaves lie in the tree component containing $t$. Temporarily add their degree-one reflection joins. Lemma 11 gives a single circular wire containing both joins. Removing them again gives two paths, each from a left test port to a right test port. This proves the acceptance criterion. Other components, including components with cycles, cannot affect these paths.

When $w=\varepsilon$, the input still has two distinct adjacent marker cells. Their inward sides glue by exactly the same slot scheme, and both outward test edges are present. In the connected case the tree has at least these two edges, so the nonempty-tree hypothesis of Lemma 11 holds. Thus the argument also gives the criterion for $\eta(\vdash)\eta(\dashv)$.

Finally, under the positive-transition acceptance convention, first perform the following operation on the original machine, before the sink normalization above. Add a new nonaccepting initial state $q_0'$ with partial row $\delta'(q_0',b)=\delta(q_0,b)$ for every scanned symbol $b$, using the original partial transition function. Keep all old states and accepting states, and leave every transition destination in the old state set. Starting at $q_0'$ simulates exactly the original computation from its first transition onward, so acceptance with the time-zero convention for this $(s+1)$-state machine is the desired positive-transition acceptance of the original. Apply the construction already proved to obtain degree $4(s+2)^2$. ◻

Extend $\eta$ to body words by multiplication, with $\eta(\varepsilon)=\mathbf 1$. If $\eta(u)=\eta(v)$, then for every $x,y\in\Sigma^*$ the whole-input diagrams of $xuy$ and $xvy$ coincide. The theorem therefore makes $u$ and $v$ indistinguishable in all input contexts, including empty contexts.

From relation products to the state lower bound

We now connect the two representations. The use of the full relation alphabet makes this step elementary: every relation occurs as a single letter, and two additional letters select any one entry of a product. This is the context-separation property of one-way liveness (Adeogun and C. Kapoutsis 2026).

Proposition 12. For $h\ge2$, the language $\mathsf{OWL}_h$ has a nondeterministic automaton with $h+3$ states, with no left moves.

Proof. Use the $h$ elements of $H=[h]$ as path states, together with three distinct states $q_{\mathrm{in}},q_{\mathrm{acc}},q_{\mathrm{rej}}$. Start in $q_{\mathrm{in}}$ on the left endmarker and move right into any path state $p\in H$. At a letter $R\in\mathcal R_{H}$ in path state $p$, move right into any $q$ with $(p,q)\in R$. If there is no such $q$, enter $q_{\mathrm{rej}}$ by a stay move. At the right endmarker in any path state, enter $q_{\mathrm{acc}}$ by a stay move. Declare only $q_{\mathrm{acc}}$ accepting. The rejecting state stays forever, and all unused rules may enter it by a stay move.

An accepting computation on $R_1\cdots R_\ell$ specifies states $p_0,\ldots,p_\ell$ with $(p_{j-1},p_j)\in R_j$ for every $j$. Such states exist exactly when $R_1\cdots R_\ell\ne0$. For the empty word, the first right move goes directly from the left marker to the right marker in a path state, and the next step accepts. This agrees with $I_{H}\ne0$. All transitions respect the boundaries, all $h+3$ states are counted, and acceptance always follows a positive transition. ◻

Lemma 13. Let $H$ be a nonempty finite set. Suppose a deterministic automaton recognizing nonzero relation products over $\mathcal R_{H}$ has a symbol-diagram representation in $\mathcal D_{k}$ as in Theorem 9. Let $S\subseteq\mathcal D_{k}$ be the submonoid generated by the ordinary-symbol diagrams, including the empty product. Then there is a unital surjection $S\to\mathcal R_{H}$ sending each ordinary-symbol diagram to its relation letter.

Proof. For a body word $w$, let $d(w)\in S$ be its diagram product and let $r(w)\in\mathcal R_{H}$ be its relation product. Suppose $d(u)=d(v)$. For any body words $x,y$, associativity gives \[d_{\mathrm L}\,d(x)d(u)d(y)\,d_{\mathrm R} =d_{\mathrm L}\,d(x)d(v)d(y)\,d_{\mathrm R},\] where $d_{\mathrm L},d_{\mathrm R}$ are the fixed marker diagrams. The recognition rule therefore gives the same membership decision for $xuy$ and $xvy$.

If $r(u)\ne r(v)$, choose $(i,j)$ belonging to exactly one of them. Take $x$ to be the single letter $I_{\{i\}}$ and $y$ the single letter $I_{\{j\}}$. For any relation $A$, \[I_{\{i\}}AI_{\{j\}} =\begin{cases} \{(i,j)\}, & (i,j)\in A,\\ 0, & (i,j)\notin A. \end{cases}\] Exactly one of the two surrounded words would belong to the language, a contradiction. Thus $d(u)=d(v)$ implies $r(u)=r(v)$, and $\phi(d(w))=r(w)$ is well-defined on $S$.

Concatenation proves that $\phi$ preserves multiplication. The empty word gives $\phi(\mathbf 1)=I_{H}$, including when a nonempty word also has diagram product $\mathbf 1$. Every relation is the image of its one-letter diagram, so $\phi$ is surjective. ◻

Proof of Theorem 1. The source-state assertion is Proposition 12. Let an arbitrary $s$-state deterministic two-way automaton recognize $\mathsf{OWL}_h$ on all finite words. Under initial-configuration acceptance, Theorem 9 gives a representation in $\mathcal D_{k}$ with $k=4(s+1)^2$. Lemma 13 supplies a unital surjection from the generated submonoid onto $\mathcal R_{[h]}$. Corollary 8 then gives \[4(s+1)^2=k\ge L(h)=2^{\lfloor(h-2)/31\rfloor}.\] With positive-transition acceptance, use the additional initial copy in Theorem 9; its degree is $4(s+2)^2$. This proves both stated bounds. ◻

Remark 14. The auxiliary vertices and wires used in the matching representation are an algebraic encoding of a computation graph, not additional memory granted to the deterministic simulator. The lower bound is proved for every machine in the ordinary model stated in the introduction. The family uses a growing finite alphabet, as permitted by the required alphabet-independent constants; the proof makes no separate fixed-alphabet claim.

Adeogun, Kehinde, and Christos Kapoutsis. 2026. A Quadratic Lower Bound for 2DFAs Against One-Way Liveness. arXiv:2602.24279v2 [cs.FL]. https://doi.org/10.48550/arXiv.2602.24279.

Adeogun, Kehinde, and Christos A. Kapoutsis. 2026. Unrestricted 2DFA Simulation of 1NFAs: A Quadratic Limitation to a New Lower Bound. arXiv:2609.13793v2 [cs.FL]. https://arxiv.org/abs/2609.13793v2.

Auinger, Karl. 2012. “Krohn–Rhodes Complexity of Brauer Type Semigroups.” Portugaliae Mathematica 69 (4): 341–60. https://doi.org/10.4171/PM/1921.

Brauer, Richard. 1937. “On Algebras Which Are Connected with the Semisimple Continuous Groups.” Annals of Mathematics, Second series, vol. 38 (4): 857–72. https://doi.org/10.2307/1968843.

Chrobak, Marek. 1986. “Finite Automata and Unary Languages.” Theoretical Computer Science 47: 149–58. https://doi.org/10.1016/0304-3975(86)90142-8.

Chrobak, Marek. 2003. “Errata to: ‘Finite Automata and Unary Languages’.” Theoretical Computer Science 302: 497–98. https://doi.org/10.1016/S0304-3975(03)00136-1.

East, James, and Robert D. Gray. 2017. “Diagram Monoids and Graham–Houghton Graphs: Idempotents and Generating Sets of Ideals.” Journal of Combinatorial Theory, Series A 146: 63–128. https://doi.org/10.1016/j.jcta.2016.09.001.

Kapoutsis, Christos. 2013. “Nondeterminism Is Essential in Small Two-Way Finite Automata with Few Reversals.” Information and Computation 222: 208–27. https://doi.org/10.1016/j.ic.2012.11.001.

Kapoutsis, Christos A. 2018. “Optimal 2DFA Algorithms for One-Way Liveness on Two and Three Symbols.” In Adventures Between Lower Bounds and Higher Altitudes: Essays Dedicated to Juraj Hromkovič on the Occasion of His 60th Birthday, edited by Hans-Joachim Böckenhauer, Dennis Komm, and Walter Unger, vol. 11011. Lecture Notes in Computer Science. Springer. https://doi.org/10.1007/978-3-319-98355-4_3.

Lange, Klaus-Jörn, Pierre McKenzie, and Alain Tapp. 2000. “Reversible Space Equals Deterministic Space.” Journal of Computer and System Sciences 60 (2): 354–67. https://doi.org/10.1006/jcss.1999.1672.

OpenAI. 2026. An exponential state lower bound for two-way nondeterministic complementation. OpenAI Math Release preprint OAI:An-exponential-state-lower-bound-for-two-way-nondeterministic-complementation-September-25-2026.

Pin, Jean-Éric. 1997. “Syntactic Semigroups.” In Handbook of Formal Languages, edited by Grzegorz Rozenberg and Arto Salomaa, vol. 1. Springer. https://doi.org/10.1007/978-3-642-59136-5_10.

Rabin, Michael O., and Dana Scott. 1959. “Finite Automata and Their Decision Problems.” IBM Journal of Research and Development 3 (2): 114–25. https://doi.org/10.1147/rd.32.0114.

Sakoda, William J., and Michael Sipser. 1978. “Nondeterminism and the Size of Two Way Finite Automata.” Proceedings of the Tenth Annual ACM Symposium on Theory of Computing (New York, NY, USA), STOC ’78, May, 275–86. https://doi.org/10.1145/800133.804357.

Shepherdson, John C. 1959. “The Reduction of Two-Way Automata to One-Way Automata.” IBM Journal of Research and Development 3 (2): 198–200. https://doi.org/10.1147/rd.32.0198.

Sipser, Michael. 1980a. “Halting Space-Bounded Computations.” Theoretical Computer Science 10 (3): 335–38. https://doi.org/10.1016/0304-3975(80)90053-5.

Sipser, Michael. 1980b. “Lower Bounds on the Size of Sweeping Automata.” Journal of Computer and System Sciences 21 (2): 195–202. https://doi.org/10.1016/0022-0000(80)90034-3.

LEVEL 2 COMPLETE!

You read 9,069 words and 754 formulas. Your math teacher would be proud.
Converted from the LaTeX source. Something look off? The original PDF is the real thing.

« Level 1 Back to game page

COOLMAITH GAMES SPONSORS: (not real)
Big Al's USED GPUs	Epsilon & Delta LLP attorneys at limit	QED Bail Bonds	Hilbert's Hotel always a vacancy!

Cool Links: openai/math Lean Mathlib arXiv the real Coolmath Games

You are visitor number 000719

Thanks for visiting CoolmAIth Games
© 1997-2026 CoolmAIth Games. A parody. Not affiliated with Coolmath.com LLC or OpenAI.
Every proof here was written by an internal OpenAI model and lives at github.com/openai/math.
Best viewed in Netscape Navigator 4.0 at 800x600