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

Proof. Put n=h+3 in Theorem 1.1. Every deterministic equivalent for this family has at least

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. 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 \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 \rank(uau^{-1})\leq\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 \id_m is supported in every such set.□

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

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\id_m e=e^2. Since \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

Thus \gamma=p^{-1}.

Every diagram z\in e\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.

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)=\id_r. To check multiplication, let z,w\in e\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 \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

Both complements have size m-r, which proves the bound.

For (iii), consider the full glued graph e\id_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 \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 \D{0}. The reduction above is its unique map, and (iii) holds with J'=\varnothing; (ii) also holds since |\supp(e)|\leq m.□

Proof. The sets S and M are finite because \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 2.2(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=\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

The last inequality uses y\in eSe. Hence R_e(y) has rank r in \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.□

Proof. The identities P^2=P and iPi=i give

They also give iQ=iP, Qi=Pi, and iQi=i. If Z\in Q\R{H}Q, then Z=QZQ and PZP=Z. Consequently

Thus its restriction iZi determines Z uniquely.

Conversely, if A\in\R{F}, so that A=iAi, then

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

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 \R{F}. This proves unitality and the claimed isomorphism.□

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 \Lfun(h)=1. A full-rank diagram is a permutation, and an idempotent permutation is the identity. Since \phi is unital and \phi(a)\ne\Id{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

Conjugates with a common support bound. Choose pairwise disjoint sets

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,

Using the pairs (u_i,z) and (z,v_j) in this construction gives idempotents s_i,s'_j\in S such that

Conjugation by permutation diagrams preserves rank, so all these idempotents have rank m-c. By Lemma 2.2(ii), each has support of size at most 2c. Thus the set

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=\Id{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

In path order, the two added pairs in (3.2) allow the path u_i,z,v_j. The outer factors P_0 delete pairs with endpoint z, so

Figure 2 shows how the same 2t conjugates provide all t^2 choices of the pair (u_i,v_j).

Let r_0=\rank(b_0). Applying Lemma 2.2(iii) at b_0 to the single set J gives one set J_0\subseteq[r_0], with |J_0|\le4tc, such that

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

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

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

Inductively, its image before taking the power is P_\ell, by (3.3) and (3.5); the power has the same image. Hence

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

The nested corners in (3.6) and Lemma 2.1 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 (3.4). 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

The loss at one addition. We claim that for every 1\le\ell\le t^2,

Each local argument uses fresh port coordinates to certify this bound on the already defined absolute rank difference \Delta_\ell in (3.7). Fix \ell, let (i,j) be its pair, and put P=P_{\ell-1}. Reduce at b_{\ell-1} and define

Here T contains the ambient identity R_{b_{\ell-1}}(b_{\ell-1})=\id. The unital-surjection assertion of Lemma 2.3 gives

Moreover, \beta is idempotent, \theta(\beta)=P_\ell, and rank preservation gives

where support now refers to the indices [r_{\ell-1}].

A full relation corner on fewer points. Set

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

Lemma 2.4 shows that Q is idempotent, PQ=QP=Q, and restriction Z\mapsto EZE is a unital isomorphism from Q\R{H}Q onto \R{F}. In particular,

Equation (3.5) also gives PP_\ell=P_\ell P=P_\ell. Since EQ=EP and QE=PE, we obtain

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 \D{r_{\ell-1}}. Put r'=\rank(d) and reduce once more, defining

The identity of T' is R_d(d)=\id. Its induced map onto Q(P\R{H}P)Q, followed by restriction to F, is the unital surjection

By Lemma 2.3 and the minimum-rank choice of d, every unit of Q(P\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=\supp(\beta)\subseteq[r_{\ell-1}]. Apply Lemma 2.2(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

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 (3.10), the image before taking the power is \Id{F}\cup\{(u_i,v_j)\}, an idempotent relation; hence

We have obtained an identity-containing submonoid of \D{r'}, a unital surjection onto \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

This proves (3.8) 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.

Summing (3.8) and applying (3.7) yields

With t=16, it follows that

This completes the induction.□

Proof. Choose an idempotent e\in S of minimum rank among those with \phi(e)=\Id{H}. The set of choices is nonempty, since the identity of S is one such idempotent. Put r=\rank(e). By Lemmas 2.2 and 2.3, the reduced corner

contains the ambient identity and maps unitally onto \Id{H}\R{H}\Id{H}=\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 \Id{H}\cup\{(x,y)\}. A positive idempotent power of that lift is an idempotent a\in T with the same image. Theorem 3.1 applies to this representation, so

□

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.□

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

of the smaller tour by

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.□

Proof of Theorem 4.1. 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

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

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.

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:

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 \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.

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 4.3 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=\eps, 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 4.3 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.□

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\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 \Id{H}\ne0. All transitions respect the boundaries, all h+3 states are counted, and acceptance always follows a positive transition.□

Proof. For a body word w, let d(w)\in S be its diagram product and let r(w)\in\R{H} be its relation product. Suppose d(u)=d(v). For any body words x,y, associativity gives

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 \Id{\{i\}} and y the single letter \Id{\{j\}}. For any relation A,

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(\id)=\Id{H}, including when a nonempty word also has diagram product \id. Every relation is the image of its one-letter diagram, so \phi is surjective.□

Proof of Theorem 1.1. The source-state assertion is Proposition 5.1. Let an arbitrary s-state deterministic two-way automaton recognize \OWL_h on all finite words. Under initial-configuration acceptance, Theorem 4.1 gives a representation in \D{k} with k=4(s+1)^2. Lemma 5.2 supplies a unital surjection from the generated submonoid onto \R{[h]}. Corollary 3.2 then gives

With positive-transition acceptance, use the additional initial copy in Theorem 4.1; its degree is 4(s+2)^2. This proves both stated bounds.□