An exponential state lower bound for two-way nondeterministic complementation

Introduction

A two-way nondeterministic finite automaton (2NFA) has a finite set of states and a single read-only head, which may move in either direction along an input bounded by endmarkers. It accepts when some finite computation reaches an accepting state. The complementation problem asks whether every $n$-state 2NFA over a finite alphabet $\Sigma$ has a 2NFA for the complementary language with at most $p(n)$ states, for one polynomial $p$ independent of $\Sigma$. We answer this question negatively.

For exact state counts, there is one initial state and a set of accepting states. Each transition depends only on the current state and scanned symbol, updates the state, and moves the head left, right, or not at all. We start the head on the left endmarker and forbid moves beyond either endmarker. Missing transitions reject that branch; infinite nonaccepting computations do not accept. An accepting initial configuration counts as acceptance. All states, including initial and accepting states, are counted. A deterministic two-way automaton (2DFA) has at most one successor for each state and scanned symbol.

For a finite set $H$, let $\mathcal{R}_H$ denote all binary relations on $H$. Products are composed in path order: $(p,r) \in AB$ if and only if $(p,q) \in A$ and $(q,r) \in B$ for some $q$. Use $\Sigma_H = \mathcal{R}_H$ as an input alphabet. The product $r(w)$ of a word $w = R_1 \cdots R_k$ is $R_1 \cdots R_k$, and the empty product is $r(\varepsilon) = I_H = \{(p,p) : p \in H\}$. Define the relation-product liveness language

In particular, $L_H$ contains the empty word when $H$ is nonempty. For nonempty words, this is Sakoda and Sipser’s family $B_h$, where $h = |H|$ [7]; the name one-way liveness is used in [4].

Theorem 1.1. For every integer $n \ge4$, set $H = \{1,\ldots,n-2\}$ and $\Sigma_n = \mathcal{R}_H$. There is an $n$-state 2NFA $A_n$ recognizing $L_H$ such that every 2NFA recognizing $\Sigma_n^* \setminus L(A_n)$ has at least

states. In particular, there is no polynomial state bound for complementation that is independent of the finite alphabet.

The alphabet $\Sigma_n$ consists of all binary relations on a set of $n-2$ points, so $|\Sigma_n| = 2^{(n-2)^2}$. The parameter is the number of states, not the size of the transition table. Theorem 1.1 concerns bounds uniform over finite alphabets; it does not assert a lower bound over one fixed alphabet.

History and significance. Sakoda and Sipser’s work on nondeterminism and two-way finite automata [7] initiated the central state-succinctness problem of simulating two-way nondeterministic automata deterministically. Complementation is a separate question: here the target remains nondeterministic. Vardi’s construction gives an exponential-state one-way nondeterministic automaton for the complement of a two-way nondeterministic automaton [8, Theorem 3.2]. It certifies nonacceptance by locally consistent sets of states. For sweeping automata, whose head can reverse direction only at the endmarkers, Kapoutsis proved that the complement of one-way liveness requires exponentially many states in every sweeping 2NFA [4, Theorem 1]. Theorem 1.1 allows unrestricted two-way motion in the complementing automaton.

For deterministic two-way automata, complementation has a linear state bound independent of the alphabet [2]. Guillon, Prigioniero, and Taheri describe polynomial 2NFA complementation as open [3, Section 1] and give polynomial complementation by 1-limited automata [3, Theorem 4.1]. These automata may rewrite a tape cell on its first visit; this resource is absent from the read-only model considered here. Theorem 1.1 resolves the alphabet-uniform polynomial complementation question negatively. The same growing-alphabet family also requires exponentially many states in every equivalent deterministic two-way automaton: a smaller deterministic simulator could be complemented with linear state overhead. Corollary 5.3 makes this implication explicit, including the treatment of infinite nonaccepting computations.

The companion paper [6] proves a deterministic lower bound with a larger exponential rate for the same language, by an independent matching-diagram argument. We compare the exact bounds after Corollary 5.3. The new obstruction here applies even when the complementing machine is nondeterministic.

The argument. An automaton with $h+2$ states guesses a path through the relations and accepts exactly when their product is nonempty. We prove that recognizing product emptiness requires exponentially many states.

The proof separates a representation of computations from a finite algebraic lower bound. A segment of a computation is represented by four relations recording the possible entries and exits through its two boundaries. These path diagrams compose by joining boundaries. Their monoid is the monoid of partitioned binary relations introduced by Martin and Mazorczak [5, Sections 2.1–2.3], written with separate labels for the two directions of travel. Adding edges only increases the available accepting paths. On the other hand, singleton relation contexts test the absence of any prescribed pair. Consequently a machine for product emptiness induces a surjective multiplicative map from its path diagrams to the relation monoid that reverses inclusion.

To bound such maps, we attach recurrent classes of boundary labels to an idempotent diagram $e$, meaning $e^2=e$. These classes group labels joined in both directions by through paths together with returns. Their precise definition is given in Section 2. The diagrams $z$ satisfying $ez=ze=z$ form a submonoid with identity $e$, called its corner. Such a $z$ may destroy the loops on some of those classes; we record the destroyed classes as a missing set. Two structural facts control this loss. First, one common missing-set bound transports through any fixed diagram context with only a factor of two. Second, along a chain of nested idempotents the sum of successive losses is bounded by twice a single initial missing-set budget. The second fact permits the corner identity to change during the argument.

For an integer parameter $t$, the amplification step converts $2t$ conjugates of one relation with an added off-diagonal pair into $t^2$ additions sharing a common budget. Each addition, after restriction to a smaller relation corner, incurs an inductively bounded loss. Taking $t = 64$ gives the exponential recurrence. This strategy adapts the conjugate-amplification pattern of the matching-diagram rank-loss argument in [6], that argument concerns a deterministic state lower bound. Here all diagram paths may be nondeterministic, and the transport and nested-class bounds are proved anew. They are stated independently of automata and may be useful for other order-reversing images of finite path monoids.

Section 2 states the algebraic bound and derives the order-reversing map before developing recurrent classes and transport. Section 3 proves the chain bound, and Section 4 proves the algebraic lower bound. Section 5 proves the promised automata representation and completes the proof of Theorem 1.1.

The bounds impose no restriction on input length or on the running time of a successful computation. They compare finite-state machines without a work tape, and give no separation between uniform logarithmic-space complexity classes.

Path diagrams and missing recurrent classes

We first describe finite paths through a segment, without assuming that the paths come from an automaton. Our goal is a loss measure that detects edge inclusion and remains controlled when a segment is put in context.

Relations are composed in path order: $x(AB)y$ means that $xAz$ and $zBy$ for some $z$. On a single set, $A^*$ denotes the reflexive transitive closure, so it includes paths of length zero. We use the elementary path identities

The first groups successive $A$-steps between $B$-steps; the second groups the same alternating path from its opposite end. These identities hold whenever the relation types permit the displayed products.

The diagram monoid

Fix disjoint sets $D^+$ and $D^-$, each of size $m \ge1$. A diagram $a$ consists of four arbitrary relations

Entering the segment on the left uses a label of $D^+$; $F_a$ records an exit on the right and $L_a$ an exit on the left. Entering on the right uses a label of $D^-$; $B_a$ records an exit on the left and $R_a$ an exit on the right. The relations $F_a$, $B_a$ are the through relations, and $L_a$, $R_a$ are the return relations; see Figure 1.

Place diagrams in a line. At each internal boundary, identify an exit with the entry of the neighboring diagram bearing the same label. The product records finite paths from an outer entry to the first outer exit, with all earlier joins internal. A traversal of any consecutive block can be replaced by one edge of the block’s product, and that edge can conversely be expanded into a finite traversal. This proves associativity. The diagram with $F$ and $B$ identity relations and $L$, $R$ empty is the identity. Thus the diagrams form a finite monoid $\mathcal{T}_m$.

This is the degree-$m$ monoid of partitioned binary relations of Martin and Mazorchuk [5]. To identify the two descriptions, label $D^+$ and $D^-$ by a common $m$-element set. @ Bibliography keys

At each boundary, an entry and an exit with the same underlying label give one vertex. The four relations above become the four blocks of a binary relation on the left and right vertex sets. A join always switches from one factor to its neighbor, exactly as in their alternating-path composition. We have included the path expansion and contraction proof of associativity to fix the finite-path convention used below.

Write $a \sqsubseteq b$ when all four relations of $a$ are included in the corresponding relations of $b$. Products preserve this order in each argument. Joining two diagrams at one boundary gives

For example, a forward path crosses $a$, alternates returns at the join, and crosses $b$. Reflection exchanges $D^+$ with $D^-$, $F$ with $B$, and $L$ with $R$, while reversing product order. We will prove symmetric statements for the positive sign and obtain the negative sign by this reflection.

From complementation to an order-reversing image

The algebraic obstruction to complementation is the following bound. As in the introduction, $\mathcal{R}_H$ is the monoid of all binary relations on $H$, composed in path order.

Theorem 2.1 (Order-reversing image bound). Let $m \ge1$, let $H$ be a finite set of cardinality $h \ge2$, and let $S_0$ be a submonoid of $\mathcal{T}_m$. Suppose that a surjective multiplicative map $\varphi_0 : S_0 \to\mathcal{R}_H$ satisfies

Then

The map need not initially be assumed to preserve identities.

The proof is completed in Section 4. We first explain the automata reduction, using the finite-computation representation below. Its construction, proved in Section 5.2, uses one additional state to represent success by an exit past the right endmarker. Local diagram edges record finitely many stay moves followed by one move out of a cell; no bound on repeated crossings is imposed.

Lemma 2.2. Let $B$ be an $s$-state $2$NFA over a finite alphabet $\Sigma$ in the model fixed in the introduction. There are a monoid homomorphism

two fixed endmarker diagrams $\lambda, \rho\in\mathcal{T}_{s+1}$, and fixed positive labels $a, b$ such that, for every word $w$,

Consequently, if $\tau(u) \sqsubseteq\tau(v)$, then

The acceptance equivalence immediately implies the stated monotonicity in arbitrary word contexts:

Derivation of context monotonicity. Diagram multiplication is increasing in each factor. If $\tau(u) \sqsubseteq\tau(v)$, then

The designated forward edge persists under this inclusion. Applying (2.5) proves (4).

For relation-product emptiness, singleton contexts convert this increasing behavior of acceptance into a decreasing relation image. For $F \subseteq H$, write $I_F = \{(x,x): x \in F\}$. A multiplicative map is unital if it preserves identities.

Proposition 2.3. Let $H$ be a finite set with at least two elements. If an $s$-state $2$NFA recognizes $\Sigma_H^{*} \setminus L_H$, then a submonoid of $\mathcal{T}_{s+1}$ admits a surjective unital homomorphism $\phi$ onto $\mathcal{R}_H$ satisfying

Proof. Apply Lemma 2.2 to the complementing machine, and let $S = \tau(\Sigma_H^{*})$. Suppose $\tau(u) \sqsubseteq\tau(v)$. For each $p,q \in H$, take the one-letter words

They belong to $\Sigma_H$, and

Since the machine accepts exactly the words with empty relation product, (4) implies

Thus

If $\tau(u) = \tau(v)$, applying (2.8) in both directions yields $r(u) = r(v)$. Therefore

is well-defined. Concatenation of words proves multiplicativity, and the empty word proves preservation of the identity. It is surjective because every relation in $\mathcal{R}_H$ is itself a letter of $\Sigma_H$. Equation (2.8) is exactly the required order reversal (2.7).

With $m=s+1$, Theorem 2.1 therefore bounds the states of a complementing machine. Section 5 constructs the $h+2$-state source machine and completes the numerical deduction. It remains to prove the algebraic bound. The next subsection associates at most $2m$ recurrent classes with an idempotent diagram. We will measure loss by the classes whose through loops are missing, and force that loss to grow exponentially with $h$.

Recurrent classes in a corner

For an idempotent $e \in\mathcal{T}_m$, define

When working only with the positive sign we omit superscripts. By $e^2=e$ and eq:2,

In particular, $P_e$ is transitive. A point $x \in D^\sigma$ is recurrent if $xP_e^\sigma x$. Mutual relatedness under $P_e^\sigma$ is an equivalence relation on the recurrent points. Let $\mathcal{C}_e$ be the collection of its classes for both signs, keeping the signs distinct. Then

For the identity diagram, $K_e^\sigma=P_e^\sigma$ is the identity relation on $D^\sigma$, so all $2m$ directional labels form singleton recurrent classes.

The corner $e\mathcal{T}_me=\{eae:a\in\mathcal{T}_m\}$ is a monoid with identity $e$; membership is equivalent to $ez=ze=z$. For $z$ in this corner put

The return formulas and the two corner identities give

Consequently

The last two inclusions follow by multiplying the first two by $K_e$ on the appropriate sides. If $x,y$ belong to one recurrent class, then $yP_ex$, $xP_ey$, and (2.13) show that a loop $xU_e(z)x$ implies $yU_e(z)y$. Reflection gives the same fact for the negative sign. Hence the following is well-defined:

We call $\mathcal{M}_e(z)$ the missing set of $z$ relative to $e$.

Lemma 2.4 (Products of missing sets). Let $e\in\mathcal{T}_m$ be idempotent. For $z,w\in e\mathcal{T}_me$,

In particular, $\mathcal{M}_e(z^k)\subseteq\mathcal{M}_e(z)$ for every positive integer $k$.

Proof. The returns of $e$ persist in both $z$ and $w$, so $(L_wR_z)^*\supseteq K_e$. Formula eq:2 therefore gives $U_e^{+}(zw)\supseteq U_e^{+}(z)U_e^{+}(w)$. Two loops at the same point compose to a loop. For the negative sign the corresponding product is $U_e^{-}(w)U_e^{-}(z)$, which gives the same conclusion. Finally $U_e^\sigma(e)=P_e^\sigma$, so no recurrent class is missing from $e$. $\square$

Lemma 2.5 (Rectangles of through edges). Let $e\in\mathcal{T}_m$ be idempotent and let $z\in e\mathcal{T}_me$. For a positive recurrent class $C\in\mathcal{C}_e$ and any $p\in C$, set

The rectangle $A_C\times B_C$ is independent of $p$ and is contained in $F_e$. These rectangles cover $F_e$. If $C\notin\mathcal{M}_e(z)$, its rectangle is contained in $F_z$. The reflected assertions hold for negative classes and $B_e$. In particular,

Proof. Containment in $F_e$ follows from $F_eK_eF_e = F_e$. The identities

show that replacing $p$ by a mutually $P_e$-related point does not change either factor of the rectangle.

To prove coverage, (2.10) implies $F_eP_e^kF_e = F_e$ for every $k \ge1$. Given a pair in $F_e$, choose a witness for this expression with $k > m$. Some label repeats along the $P_e$ portion. That label $p$ is recurrent, since a nonempty $P_e$-path from $p$ back to itself is a $P_e$-edge by transitivity. The portions before and after $p$ belong to $F_eK_e$ and $K_eF_e$: indeed $F_eP_e^j \subseteq F_eK_e$ and $P_e^jF_e \subseteq K_eF_e$ for $j \ge0$, including $j = 0$ since $K_e$ is reflexive.

If $C$ is not missing from $z$, insert $pK_eF_zK_ep$ between the two halves of its rectangle. The resulting relation is contained in $F_eK_eF_zK_eF_e \subseteq F_z$ by (2.13). Reflection proves the backward assertion. When the missing set is empty all through edges of $e$ are thus present in $z$, and its return edges persist by (2.12).

Transport through a fixed context

The next statement controls a whole family of replacements at once. The common target set, rather than merely a bound for each replacement, will be essential in the amplification argument.

Lemma 2.6 (Transport). Let $e,d \in\mathcal{T}_m$ be idempotents and let $u,v \in\mathcal{T}_m$ satisfy $uev = d$. For every $J \subseteq C_e$ there exists a single set $J' \subseteq C_d$, with $|J'| \le2|J|$, such that

for every $z \in e\mathcal{T}_me$ satisfying $\mathcal{M}_e(z) \subseteq J$ and $uzv \in d\mathcal{T}_md$.

Proof. For each positive class of $C_d$, choose a representative $x$ and a witness for $xK_d^+F_duevK_d^+x$. Expand the middle edge into an actual finite path through the three diagrams $u,e,v$. For a negative class do the same with $xK_d^-BuevK_d^-x$. Make these choices once, independently of $z$.

For every occurrence of a through edge of the middle factor $e$ on a chosen path, choose an $e$-class whose rectangle covers that edge, using Lemma 2.5. Mark a $d$-class if any class chosen along its witness lies in $J$; let $J'$ be the marked set. If a class is unmarked, all its chosen through edges survive replacement of $e$ by $z$, as do all return edges of $e$. Its original outer $K_d^\sigma$ pieces remain fixed. Thus its witness is a loop in $U_d(uzv)$, and the class is not missing. This proves the required common-set inclusion.

It remains to count marked classes. For each $d$-class $C$, let $S_C$ be the set of $e$-classes chosen along its fixed witness. We show that the sets $S_C$ are pairwise disjoint among $d$-classes of a fixed sign. Consider two positive witnesses, written as

where $\alpha,\beta,\alpha',\beta' \in D^+$ and the displayed $F_d$-edges have been expanded through $u,e,v$. Suppose the expanded paths use occurrences of middle-factor edges $(a,b)$ and $(a',b')$ covered by one $e$-class. Its rectangle also contains $(a,b')$ and $(a',b)$. The sign of that $e$-class fixes the orientation of both edges and their entry and exit boundaries inside the three-factor product. Thus the prefix ending at $a$, the crossed edge $(a,b')$, and the suffix starting at $b'$ concatenate to a path from $\alpha$ to $\beta'$. Neither retained subpath has an earlier outer exit. The concatenation is therefore a valid finite path for $F_d$, even if it repeats internal crossings or its selected middle edge points backward. Interchanging the two prefixes and suffixes similarly gives $\alpha'F_d\beta$. The original exterior factors now give $xP_d^+y$ and $yP_d^+x$, so $x$ and $y$ belong to the same recurrent class. Reflection gives the same conclusion for negative witnesses, with $B_d$ in place of $F_d$. This proves the asserted disjointness for each sign. A witness using only returns of $e$ has $S_C=\varnothing$ and is never marked. Since $J'=\{C:S_C\cap J\ne\varnothing\}$, at most $|J|$ classes of each sign are marked, and $|J'|\le2|J|$.

A loss budget for nested idempotents

For idempotents in a semigroup, write $d\trianglelefteq e$ if $de=ed=d$, and say that $d$ is nested under $e$. This is a partial order: reflexivity and antisymmetry are immediate, and if $d\trianglelefteq e\trianglelefteq f$, then $df=(de)f=d(ef)=de=d$ and $fd=f(ed)=(fe)d=ed=d$. Nesting is distinct from the edge-inclusion order $\sqsubseteq$.

We will bound the sum of the losses incurred along a nested chain, even though the identity, the recurrent classes, and hence the meaning of a loss change at every step. The key fact is a containment dichotomy: a new recurrent class contains either an old class that is not lost, or at least two old classes.

Lemma 3.1 (Absorption under nesting). Let $d,e\in\mathcal{T}_m$ be idempotents with $d\trianglelefteq e$. For either sign $\sigma$,

In the positive sign one also has

The corresponding negative-sign inclusions use $B_e$.

Proof. We prove the positive-sign statements and suppress the superscript $+$. Because $d\in e\mathcal{T}_m e$, its returns contain those of $e$: $L_e\subseteq L_d$ and $R_e\subseteq R_d$. Set

Then $K_e\subseteq S,T\subseteq K_d$. The multiplication formulas applied to $ed=de=d$ give

We spell out the two star rearrangements needed below, using the finite-path identities in (2.1).

Expanding $R_d$ in $K_d=(L_dR_d)^*$, we obtain

Indeed, $F_eSL_dB_e\subseteq L_d$ by eq:3, so the relation inside the last star is contained in $L_dR_dT\subseteq K_d$. For the other side, expand $L_d$ instead:

Here $B_eR_dT F_e \subseteq R_d$, so the relation inside the star is contained in $SL_dR_d \subseteq K_d$. These inclusions, multiplied by the remaining $K_d$, prove (3.1) because $P_d = K_dF_dK_d$. Finally, $K_dP_d = P_dK_d = P_d$ and $K_e \subseteq K_d$ imply

Reflection proves all negative-sign statements.

Lemma 3.2 (Containment of recurrent classes). Let $d,e \in\mathcal{T}_m$ be idempotents with $d \leq e$. Every class in $C_d$ contains either

1. a whole class in $C_e \setminus M_e(d)$; or

2. two distinct whole classes in $C_e$.

All classes in either containment have the same sign.

Proof. Again work in the positive sign and omit its superscript. Fix a recurrent point $x$ of $P_d$. Using (8) twice, its recurrence gives

By the rectangle cover in Lemma 2.5, each of the two displayed $F_e$-edges can be factored through an $e$-recurrent point. Denote the first point by $p$ and the second by $q$. The resulting witness has the form

where

Here $\beta\subseteq P_d$ because $K_e \subseteq K_d$. Moreover, Lemma 3.1 shows that multiplying $P_d$ on either side by $\alpha$ or $\gamma$ gives a subrelation of $P_d$. Thus all four endpoint relations needed for class membership follow from (10) and $xP_dx$:

In particular $p$ and $q$ are recurrent for $P_d$ and belong to the class of $x$. In the first and last lines, inserting the recurrence at $x$ is essential: the shorter witness portion alone need not contain a $d$-through edge.

The entire $P_e$-class of $p$ lies in the $P_d$-class of $x$. Indeed, if $r$ is in the former class, then $xP_dpP_er$ and $rP_epP_dx$, and the two mixed absorptions of Lemma 3.1 give $xP_dr$ and $rP_dx$. The same argument applies to $q$. If their $P_e$-classes are distinct, this proves the second alternative. If they coincide, then $pU_e^{+}(d)q$ by (10) and $qP_ep$. The corner absorption $U_e^{+}(d)P_e \subseteq U_e^{+}(d)$ gives $pU_e^{+}(d)p$, so that class is not in $M_e(d)$. This proves the first alternative. Reflection handles the negative sign.

Proposition 3.3 (Chain bound). Let $b_0,b_1,\ldots,b_k \in\mathcal{T}_m$ be idempotents such that $b_j \leq b_{j-1}$ for $1 \leq j \leq k$. Suppose a single set $J_0 \subseteq C_{b_0}$ satisfies

Then

Proof. Choose one protected label in every class of $\mathcal{C}_{b_0} \setminus J_0$, and keep these choices fixed. Every protected label $x$ of sign $\sigma$ satisfies $xU^{\sigma}_{b_0}(b_j)x$ at every stage $j$. By transitivity of nesting and Lemma 3.1, $K^{\sigma}_{b_0} \subseteq K^{\sigma}_{b_j}$, so this loop also belongs to $P^{\sigma}_{b_j}$. Thus every protected label remains recurrent. Let $s_j$ count the classes in $\mathcal{C}_{b_j}$ containing no protected label. In particular $s_0 = \lvert J_0\rvert$.

Write $\delta_j = \lvert\mathcal{M}_{b_{j-1}}(b_j)\rvert$. Every class missing at step $j$ is unprotected. Otherwise it would contain a protected label $x$ of sign $\sigma$; the loop $xU^{\sigma}_{b_0}(b_j)x$ and the inclusion $K^{\sigma}_{b_0} \subseteq K^{\sigma}_{b_{j-1}}$ would then give $xU^{\sigma}_{b_{j-1}}(b_j)x$, contradicting missingness.

Assign weight $1/2$ to each missing unprotected class of $\mathcal{C}_{b_{j-1}}$, and weight $1$ to each other unprotected class there. Their total weight is $s_{j-1} - \delta_j/2$. Figure 2 illustrates the two ways that an unprotected new class can obtain weight at least one from the previous stage.

By Lemma 3.2, each unprotected class at stage $j$ contains previous classes of total weight at least $1$: either one nonmissing class, or two distinct classes. Every contained previous class is unprotected, since a protected label in it would also protect the new class. Distinct new classes cannot use the same previous class, because classes of a fixed sign are disjoint and the two sign-label sets are disjoint. Consequently

Summing and using $s_k \ge0$ yields $\sum_{j=1}^{k} \delta_j \le2(s_0 - s_k) \le2\lvert J_0\rvert$.

An exponential bound for order-reversing images

We now prove Theorem 2.1, combining transport and the nested-chain inequality to bound order-reversing relation images. Write $\mathcal{R}_H$ for the monoid of all binary relations on a finite set $H$, with multiplication in path order. For $F \subseteq H$, write $I_F = \{(x,x): x \in F\}$; relations on $F$ are also regarded as relations on $H$ supported on $F \times F$.

The proof amplifies one off-diagonal pair in the image into a family of pair additions. The chain inequality bounds their total cost in missing recurrent classes; restriction to smaller relation monoids bounds each cost from below. We first record two elementary facts that allow these restrictions without losing the hypotheses. The pattern of relation additions follows the matching-diagram argument in [6]; all loss estimates needed here are supplied by the path-diagram results just proved.

Corners and unit lifts

For an idempotent $d$ in a semigroup $A$, its corner $dAd = \{dad : a \in A\}$ is a monoid with identity $d$. A unit means an element with a two-sided inverse relative to the specified monoid identity.

Lemma 4.1 (Minimal idempotent corners). Let $A$ be a finite semigroup, let $M$ be a monoid, and let $\theta: A \to M$ be a surjective multiplicative map. For every idempotent $q \in M$, there is an idempotent $d \in A$ with $\theta(d) = q$ that is minimal among such idempotents under $\trianglelefteq$. For every such minimal $d$, restriction of $\theta$ gives a unital surjection

Every element of $dAd$ whose image is a unit of $qMq$ is itself a unit of $dAd$. In particular, every unit of $qMq$ has a unit lift.

Proof. Every element $w$ of a finite semigroup has an idempotent positive power: the sequence of powers is eventually periodic, so a sufficiently large exponent divisible by its eventual period gives $w^{2k} = w^k$. Applying this to a preimage of $q$ gives an idempotent preimage of $q$. Finiteness then gives one minimal in the nesting order.

For any $y \in qMq$, choose $x \in A$ with $\theta(x) = y$. Then $\theta(dxd) = qyq = y$, proving surjectivity on the corner; its identity $d$ maps to $q$. Now let $w \in dAd$ have unit image. An idempotent power $w^k$ has an image that is both a unit and an idempotent in $qMq$, hence equals $q$. Since $w^k \trianglelefteq d$, minimality gives $w^k = d$. If $k > 1$, the element $w^{k-1}$ is a two-sided inverse of $w$ in $dAd$; if $k = 1$, then $w = d$ is already the identity.

The next lemma identifies a smaller full relation monoid inside an idempotent corner. Its hypothesis says that the old relation restricts to the identity on the retained points.

Lemma 4.2 (Restriction of a relation corner). Let $P \in\mathcal{R}_H$ be idempotent, let $F \subseteq H$, and put $i = I_F$. Suppose that $iPi = i$, and define $Q = PiP$. Then $Q$ is idempotent, $Q \trianglelefteq P$, and restriction is a unital monoid isomorphism

Its inverse sends $A \in\mathcal{R}_F$ to $PAP$.

Proof. Using $P^2 = P$ and $iPi = i$, we obtain

If $Z = QZQ$, then $PZP = Z$, and therefore

Thus restriction determines $Z$ uniquely. Conversely, for a relation $A = iAi$ supported on $F$, the relation $PAP$ belongs to $Q\mathcal{R}_H Q$, since $PAP = QAQ$, and

This proves bijectivity with the claimed inverse. For supported relations $A, B \in\mathcal{R}_F$,

Hence the inverse, and therefore restriction, preserves multiplication. Finally $\rho(Q) = i$, the identity of $\mathcal{R}_F$.

Amplifying a single added pair

Set

The choice $t = 64$ balances the two estimates proved below: $t^2$ pair additions each cost at least half the smaller-instance bound, while their total cost is at most $16t$ times the original loss. The resulting gain is $t/32 = 2$, at a reduction of $2t - 1 = 127$ points. We prove a missing-set bound strong enough to survive passage to any of the corners above. The additional unit-lifting hypothesis permits conjugation by arbitrary permutations of $H$; Lemma 4.1 will supply it when we return to Theorem 2.1.

Proposition 4.3 (Cost of one added pair). Let $m \ge1$, let $e \in\mathcal{T}_m$ be idempotent, and let $S \subseteq e\mathcal{T}_m e$ be a submonoid with identity $e$. Let $H$ be a finite set of cardinality $h \ge2$. Suppose that $\phi: S \to\mathcal{R}_H$ is a unital surjective homomorphism such that

and suppose that each permutation of $H$ has a lift that is a unit of $S$. If $a \in S$ is idempotent and, for distinct $x,y \in H$,

then $|\mathcal{M}_e(a)| \ge D(h)$.

Proof. We induct on $h$, simultaneously over all the data in the statement, including $m$, $e$, $S$, and $\phi$. For $2 \le h \le2t$, we have $D(h) = 1$. If $\mathcal{M}_e(a)$ were empty, Lemma 2.5 would give $e \sqsubseteq a$. Order reversal would then give $I_H \cup\{(x,y)\} \subseteq I_H$, a contradiction.

Assume henceforth that $h \ge2t + 1$, and put $c = |\mathcal{M}_e(a)|$. We will construct $t^2$ nested steps with total missing-set size at most $16tc$. Each step will contain a smaller instance of the Proposition, on $h - 2t + 1$ points.

Step 1: A common budget for all pair additions. Choose disjoint sets

in $H$. Conjugating $a$ by unit lifts of permutations gives elements $s_i,s'_j \in S$ with

Indeed, permutation conjugation acts transitively on ordered pairs of distinct points, and the inverse of a unit lift maps to the inverse permutation. Explicitly, a unit $p \in S$ gives the conjugate $pap^{-1}$, with $pep^{-1} = e$. Applying Lemma 2.6 with $J = \mathcal{M}_e(a)$ therefore gives

Consequently the single set

has $|J| \le4tc$, and the product inequality of Lemma 2.4 gives $\mathcal{M}_e(s_i s'_j) \subseteq J$ for every $i,j$. Let $P_0 = I_H \setminus\{z\}$. Choose an idempotent lift $b_0 \in S$ of $P_0$, by taking an idempotent positive power of any lift, and define

The image of $s_i s'_j$ consists of the identity and the three pairs $(u_i,z)$, $(z,v_j)$, and $(u_i,v_j)$. The outer factors $P_0$ remove the first two, so

Figure 3 illustrates this conversion of two generator families into a family indexed by $U \times V$.

Since $b_0 e b_0 = b_0$, the common-set conclusion of Lemma 2.6 gives a single set $J_0 \subseteq C_{b_0}$ such that

Step 2: A nested chain spending that budget. List the $t^2$ pairs of $U \times V$ in any order, without repetitions. Let $E_\ell$ be the set of the first $\ell$ pairs, and put $P_\ell= P_0 \cup E_\ell$ for $0 \le\ell\le t^2$. For any $E,E' \subseteq U \times V$,

To check this, $P_0$ acts as the identity on all the endpoints in question, and no pair of $E$ can be followed by a pair of $E'$, because $U \cap V = \varnothing$. In particular, every $P_\ell$ is idempotent.

If the pair at position $\ell$ is $(u_i,v_j)$, choose $b_\ell$ to be an idempotent positive power of $b_{\ell-1}g_{ij}b_{\ell-1}$. Inductively, Equation (4.6) gives $\phi(b_\ell) = P_\ell$. The sandwich, and hence all its positive powers, is absorbed on both sides by $b_{\ell-1}$. Thus

All these elements lie in the $b_0$-corner. Starting with $\mathcal{M}_{b_0}(b_0) = \varnothing$, repeated use of Lemma 2.4 and Equation (15) shows that

Here taking a positive power cannot enlarge the missing set: all factors have the same missing set, and their union is unchanged. Proposition 3.3 now yields

We have bounded the total cost of the chain using only the $2t$ original conjugates. It remains to give an inductive lower bound for each of its $t^2$ steps.

Step 3: A smaller instance inside every step. Fix $\ell$, let $(u_i,v_j)$ be its newly added pair, and write $b = b_{\ell-1}$ and $P = P_{\ell-1}$. Retain the two endpoints of this pair and all points outside the construction:

Then $|F| = h - 2t + 1 \ge2$. Among the possible extra pairs of $P$, only $(u_i,v_j)$ has both endpoints in $F$, and this pair has not yet been added. Therefore $i_F P i_F = i_F$. By Lemma 4.2, $Q \leq P$ and restriction gives $\mathcal{R}_H Q \cong\mathcal{R}_F$. Moreover, Equation (4.6) gives $P P_\ell P = P_\ell$. Using $i_F Q = i_F P$ and $Q i_F = P i_F$, we obtain

Consider the finite monoid $A = bSb$. The restriction of $\phi$ maps it onto $P\mathcal{R}_H P$: sandwiching any preimage by $b$ gives a preimage of its $P$-sandwich. Apply Lemma 4.1 inside $A$ to the idempotent $Q$. We obtain an idempotent $d \in A$ with $\phi(d) = Q$, minimal there among idempotent lifts of $Q$. Its corner $dAd$ maps unitally onto

and all units of this image have unit lifts. Composing with restriction gives a unital surjective homomorphism

This map is order-reversing because $\phi$ is and restriction preserves inclusion. It has unit lifts of every permutation of $F$, by the isomorphism in Lemma 4.2. Also $dAd$ is a submonoid of $dT_m d$ with identity $d$. These observations verify all the map and domain hypotheses needed for induction.

Because $b_\ell\leq b$, we have $b_\ell\in A$. By Equation (4.8), the element $db_\ell d \in dAd$ maps under $\psi$ to $I_F \cup\{(u_i,v_j)\}$. This relation is idempotent, so an idempotent positive power $v$ of $db_\ell d$ has the same image. Since $d \in A$ is idempotent, $dbd = d$. Apply Lemma 2.6 from the identity $b$ to the identity $d$, with context $(d,d)$ and missing set $\mathcal{M}_b(b_\ell)$. Then apply the power consequence of Lemma 2.4 in the $d$-corner. This gives

The induction hypothesis applies to $d$, $dAd$, $\psi$, and $v$, with the smaller parameter $|F| = h - 2t + 1$. It follows that

Summing this lower bound and using Equation (16), we conclude that

For $t = 64$, the last expression is $2D(h - 127) = D(h)$, by the definition of $D$. This completes the induction.

Proof of Theorem 2.1. Apply Lemma 4.1 to $\phi_0$ and the idempotent $I_H$. It supplies an idempotent $e \in S_0$ such that $S = eS_0e$ maps unitally onto $\mathcal{R}_H$ and every permutation has a unit lift. The restricted map retains order reversal, and $S$ is a submonoid of $eT_m e$ with identity $e$.

Choose distinct $x,y \in H$ and any lift in $S$ of $I_H \cup\{(x,y)\}$. An idempotent positive power $a$ of that lift has the same image. Proposition 4.3 therefore gives

as required.

Finite computations and the main lower bound

We complete the concrete obligations deferred in Section 2: constructing the small source automaton and proving the finite-computation representation. The order-reversing map has already been derived in Proposition 2.3; we then combine it with Theorem 2.1 to finish the main proof. Throughout, we use the automaton model fixed in the introduction, including stay moves, finite acceptance, and acceptance in the initial configuration.

The source automaton

Fix a set $H$ of size $h \ge2$. Recall that the alphabet is $\Sigma_H = \mathcal{R}_H$, the word product is $r(w)$ with $r(\varepsilon) = I_H$, and

Lemma 5.1. The language $L_H$ is recognized by a $2$NFA with exactly $h + 2$ states.

Proof. Use one initial state $q_{\mathrm{in}}$, the $h$ states in $H$, and one accepting state $q_{\mathrm{acc}}$, all distinct. From $q_{\mathrm{in}}$ on the left endmarker, the machine moves right into any chosen state of $H$. On a letter $R \in\mathcal{R}_H$, it may move right from $p \in H$ to $q \in H$ precisely when $(p,q) \in R$. At the right endmarker, every state in $H$ has a stay transition to $q_{\mathrm{acc}}$. There are no other transitions, and $q_{\mathrm{acc}}$ is the only accepting state.

On $R_1 \cdots R_k$, an accepting computation is exactly a sequence $p_0,\ldots,p_k \in H$ with $(p_{i-1},p_i) \in R_i$ for $1 \le i \le k$. Such a sequence exists exactly when the relation product is nonempty. For $k = 0$, the initial move reaches the right endmarker directly, and the machine accepts. This agrees with $r(\varepsilon) = I_H \ne\varnothing$.

Finite computations as diagram paths

We now prove the representation promised in Lemma 2.2. The construction records arbitrary finite computations, including stay moves and repeated crossings of the same cut. It does not require termination of every computation.

Proof of Lemma 2.2. Let $B$ be the $s$-state automaton in the lemma, with state set $Q$ and initial state $q_0$. Introduce one new state $q_{\dagger}$. From every original accepting state, at every cell, add a stay transition to $q_{\dagger}$. In state $q_{\dagger}$, move right regardless of the scanned symbol, finally exiting past the right endmarker in state $q_{\dagger}$. This last exit is only a device for representing acceptance, not a transition of the original machine. All original transitions remain subject to the endmarker restrictions.

A finite augmented computation from the original initial configuration to the designated exit exists if and only if $B$ accepts. Indeed, an accepting original computation can be followed by the added stay and rightward sweep. Conversely, the first entry into $q_{\dagger}$ must come from an original accepting configuration. This argument includes the case that $q_0$ itself is accepting. Infinite computations create no additional finite successful computation.

Put $\widehat{Q} = Q \cup\{q_{\dagger}\}$ and $m = s + 1$. Take the directional label sets to be two disjoint copies

For a cell symbol $c$, including either endmarker with its boundary rules, let $E_c$ be the relation on $\widehat{Q}$ given by the augmented stay transitions. Let $T_c^+$ and $T_c^-$ be the relations given by the augmented rightward and leftward transitions, respectively; their second coordinates record the state after the move. At the right endmarker, $T_c^+$ includes only the designated augmented exit, and at the left endmarker $T_c^-$ is empty. Define a diagram $d_c$ by

Thus each local diagram edge represents a finite sequence of stays, possibly empty, followed by one move out of the cell. The incoming sign specifies the side of entry, not additional machine memory; the transition rules themselves depend only on the state and symbol.

Set $\lambda=d_{\mathrm{left}}$ and $\rho=d_{\mathrm{right}}$ for the two endmarkers, and set

This is a monoid homomorphism. Every finite augmented computation ending in the designated exit decomposes into successive visits to individual cells, each consisting of finitely many stays and one exit move. These visits give a path through the product of the cell diagrams. In the opposite direction, each local edge in a finite diagram path has a finite transition witness. Expanding these witnesses and concatenating them gives an augmented computation, because the exit state from one cell is exactly the entry state to the next. Neither direction assumes that a cut is crossed at most once.

The fictitious entry into the left endmarker with label $q_0^+$ represents the initial configuration; it is not an additional machine transition. No path can leave the tape to the left, and a path can leave to the right only through the designated exit. Hence (2.5) holds with $a=q_0^+$ and $b=q_\dagger^+$. For the empty word, the two endmarker cells are adjacent, and the identity $\tau(\varepsilon)$ gives precisely their product. A stay cycle causes no difficulty: only its finite traversals are represented in $E_c^*$.

Remark 5.2 (Other standard conventions). The exponential conclusion also survives the usual changes of starting position or acceptance convention, with possible changes to the additive state offsets. To use our representation for a machine whose convention requires a positive transition into an accepting state, add a fresh nonaccepting initial copy with the same outgoing transitions, keeping all original states and transition destinations. This prevents the initial configuration alone from accepting, while preserving every acceptance after a transition. Starting on the first input cell can be simulated from the left endmarker by one additional initial state. If success must occur at a designated marker or on a specified exit, enable the added success routine only at that local accepting event. These versions of the path representation use $m=s+O(1)$ labels per sign, and the source automaton still uses $h+O(1)$ states. The exact offsets in Theorem 1.1 refer to the convention fixed in the introduction.

Proof of Theorem 1.1. For any $n \ge4$, let $h=n-2$, choose a set $H$ of size $h$, and use the $n$-state source automaton from Lemma 5.1. If an $s$-state 2NFA recognizes its complement, then Proposition 2.3 supplies the order-reversing relation image required by Theorem 2.1. With $m=s+1$, that bound gives

Rearranging proves the stated lower bound. Since its right-hand side grows exponentially with $n$, no fixed polynomial can bound the complementation cost for all finite alphabets.

The determinization consequence

The lower bound also applies indirectly to deterministic simulation. Here we use one external automata transformation: deterministic two-way automata can be complemented with linear state overhead independent of the alphabet, even when the original computation may fail to halt [2]. The possible nonaccepting loops are the reason that exchanging accepting and rejecting states alone does not give this transformation.

Corollary 5.3. There are absolute constants $c > 0$ and $n_0$ such that, for every $n \ge n_0$, every $2$DFA recognizing the language of the $n$-state $2$NFA $A_n$ in Theorem 1.1 has at least

states. Hence no polynomial state bound independent of the finite alphabet can determinize all $2$NFAs.

Proof. We use only the linear-overhead conclusion of [2], allowing constant-factor changes for model conventions. The standard marker model and its normalization are described in the precursor [1]. Stay moves can be replaced by a two-step excursion that stores the destination state and the return direction in a fixed number of copies of the state set. The excursion goes left at the right endmarker and right elsewhere. Even on the empty word, the two distinct endmarker cells provide the needed adjacent cell. Auxiliary states are nonaccepting, and the destination state is entered only on returning to the original cell. A reached accepting configuration, including the initial configuration, can instead start a fixed marker sweep to a designated accepting halt. Missing transitions can halt and reject. These changes require $O(s + 1)$ states for an $s$-state $2$DFA and preserve finite acceptance. The cited transformation supplies the substantive additional step of handling infinite nonaccepting computations.

Thus an $s$-state deterministic recognizer for $L(A_n)$ has a deterministic complement, also a $2$NFA, with at most $C(s + 1)$ states for an absolute constant $C$. Theorem 1.1 gives

For all sufficiently large $n$ this implies the asserted bound with an absolute $c > 0$. Since the same alphabets are finite for every $n$, it also excludes every polynomial bound uniform over alphabets.

For comparison, the companion theorem [6] gives

for an $s$-state deterministic recognizer of the same language $L_H$. That theorem also states the improvement from $s + 2$ to $s + 1$ when the initial configuration counts as acceptance, as it does here. Its exponent therefore grows as $h/62$, compared with $h/127$ in Corollary 5.3. The source constructions use $h + 3$ and $h + 2$ states, respectively: the companion includes a rejecting sink, which the partial source automaton above does not need. Its matching-diagram proof gives a stronger deterministic bound independently of the complementation theorem proved here.