The problem and its mathematical context

The corresponding ordinary star-height problem omits complement. Eggan connected ordinary star height with the cycle structure of transition graphs, and Dejean and Schützenberger established unbounded ordinary star height already over a two-letter alphabet (Eggan 1963; Dejean and Schützenberger 1966). These results concern the operations allowed in ordinary expressions. Their lower bounds do not carry over merely by adding complement.

Generalized height zero already has a different character: its languages are the star-free languages, which need not be finite. A finite monoid \(M\) recognizes a language when membership depends only on the image of a morphism from \(\Sigma^*\) to \(M\). Schützenberger characterized the star-free languages as exactly those recognized by finite aperiodic monoids (Schützenberger 1965). Here a monoid is aperiodic if every element \(m\) satisfies \(m^r=m^{r+1}\) for some \(r\ge1\). A simple language requiring one star is \((aa)^*\) over \(\{a\}\): its displayed expression has height one, while every star-free unary language is finite or cofinite, as induction under union, complement, and concatenation shows.

The algebraic approach has also produced substantial families of height at most one. Pin, Straubing, and Thérien proved this bound for languages recognized by finite nilpotent groups of class two, and for further classes of finite monoids (Pin et al. 1992, Theorems 7.3 and 7.8). Another line of results concerns words in which a fixed nonempty factor occurs contiguously a prescribed number of times modulo an integer \(n\ge2\), with overlapping occurrences counted. Bourne and Ruškuc proved height-one bounds for factors of length at most three (Bourne and Ruškuc 2016, Proposition 2.5); Bourne subsequently extended the result to arbitrary fixed factors in his thesis (Bourne 2017, Theorem 2.25). These results explain how complement can simplify nontrivial counting languages, but their restricted families do not supply a bound for arbitrary regular languages.

A universal finite upper bound and a universal upper bound of one are different assertions; Straubing distinguishes them explicitly in his account of the problem (Straubing 2002, 537). Theorem 1 gives a positive answer to the boundedness question. It does not exhibit a language of generalized height greater than one, and does not decide whether one always suffices.

Two companion constructions explain the setting of this proof. The paper Finite Monoid Computations and a Uniform Generalized Star-Height Bound proves a bound of thirteen by finite computations, a prediction argument, and a decision tree that retains the complete earlier history (OpenAI 2026a, Theorem 1.1 and Sections 2–7). Generalized Star Height at Most Four proves a bound of four using constancy on affine coordinate lines, several marker scales, and product transport across moving periodic boundaries (OpenAI 2026b, Theorem 1.1 and Sections 2–6). The present construction obtains three through two split steps. Each of the three papers gives its own complete proof; the numerical theorem of one is not used to prove another. The prediction and multiscale methods remain different constructions even though the bound here is smaller.

Computing a word value with independent tests

Every regular language has a recognizing morphism \(T:\Sigma^*\to M\) into a finite monoid. We therefore seek expressions for the fibers of \(T\). The construction parses a word into complete pieces called episodes, followed by a final remainder. The episode language \(E\) is a prefix code, meaning that no member is a proper prefix of another. This makes the episode boundaries unique.

An episode will act on a finite vector space by an affine map. To propagate its state, we cut the episode and test the prefix for an input state and the suffix for an output state. The tests are languages placed in separate factors of a concatenation. Thus their auxiliary choices are independent. A valid split has to meet two separate obligations: every successful pair beginning at a true episode boundary must consume that entire first episode and transmit its update; for every input state, a successful pair must exist on each episode that is not assigned to a specified skipped class.

Section 2 proves a split identity that converts these obligations into expressions for arbitrary episode sequences. If the individual tests and the episode domain have height at most one and sequence computations on the skipped class have height at most \(H\), the identity gives height at most \(\max\{2,H+1\}\). The split and affine recovery methods are developed in the two companions (OpenAI 2026a, Lemmas 2.2–2.3) and (OpenAI 2026b, Lemmas 2.1–2.2); all versions used here are proved locally. An affine correction does not destroy the original computation: the difference between the outputs on \(x\) and on zero recovers the linear part on \(x\). Finite unions and intersections express this subtraction without another star.

Why two splits suffice

The first split uses later cuts in an episode and a finite set of tags. A tag is a tuple of states, interval products, and indices that a test proposes to use. The prefix and suffix choose their tags separately. A clock restricts the pairs they can jointly realize: either they agree, or there is only one possible unequal pair. In the second case we define the episode’s affine translation so that this one pair transmits the prescribed input to the prescribed output. To use the clock, however, both tests must calculate the same total time. A separate end guard establishes that fact; it is not a consequence of the clock.

The clock also needs room to realize its permitted choices at actual cuts. Outside an exceptional set of total times, every tag permits a whole neighborhood of compatible prefix times, with a common positive margin. The clock also supplies a finite list of candidate times for which the number of exceptional pairs is bounded uniformly under translation and sufficiently small simultaneous perturbations. These are the additional clock properties used here; Section 3 compares the quantitative bounds.

When tags agree, the first split has two ways to work. If all the marker boundaries are present, their successive intervals give a tuple of monoid products. A finite shift table makes one coordinate of this tuple irrelevant to the transmitted output. The prefix checks the earlier products, the suffix checks the later products, and a finite certificate checks every possible value of the product crossing their cut. If a marker boundary is absent, a long periodic stretch instead allows the cut to move through all clock residues while keeping its prefix product fixed. This argument uses eventual periodicity of powers in a finite monoid; it requires no cancellation.

The shift table is uniform in a stronger sense than a product-action statement. One tuple length, chosen using only the finite entry alphabet and state space, must work for every table from tuples to linear maps. A single correction table is chosen for each such map, independently of the input vector. The coordinate that can be omitted may depend on the tuple and vector. This quantifier order is proved by a finite avoidance argument of the local-lemma type of Erdős and Lovász (Erdős and Lovász 1975).

The clock and marker conditions used to guarantee the first split’s completeness can fail on an intrinsic sublanguage \(D\subseteq E\). The second split handles every episode in \(D\), with no further skipped class. A suffix at an earlier cut can use the failed condition as a witness to the actual origin. Those early cuts form a fixed finite set, or stencil, containing many copies of every required tuple of metadata. The differences between distinct stencil positions have different residues. Marker searches with widths indexed by these residues make false witnesses sparse over all ordered pairs of positions, including pairs with incorrect metadata.

End detection needs special care in this count. A smaller bounded search fixes an episode’s end when it finds an end marker; otherwise a periodic seed is followed to its first mismatch. A larger bounded search supplies the clock anchor whenever possible. If that larger search is absent at one nearby proposed origin, all the smaller searches are absent, and their overlapping seeds have one common mismatch. If every larger search is present, all candidate clock anchors are already bounded data. In either case the true origin’s witness remains available before the suffix requires uniqueness. After identifying it, the suffix must separately check its exact endpoint. Counting over the whole stencil leaves a usable copy of every metadata tuple and supplies the second split.

From finite tests to height-three expressions

The local marker construction is a finite-window instance of the marker-versus-periodicity method (Krieger 1982, Lemma 2); its full priority construction and periodic-overlap argument are given in Section 4. Section 3 proves the robust clock. Section 5 then chooses all finite parameters in dependency order. In particular, a provisional rational clock fixes the early stencil before the marker scale is chosen. A later rational approximation preserves those fixed trials and makes the final clock period coprime to all relevant short periods.

Sections 6 and 7 construct episodes, force a common end under independently chosen roles, and prove the first split. Section 8 establishes the bound on all false origins and the suffix decoder. Section 9 uses the remaining suffix to compute a total table indexed by every hypothetical prefix product in \(M\), including values that no prefix realizes. Applying the shift-table lemma to this table gives the second split.

The last step, Section 10, controls expression height for each component on its own domain. A standalone suffix, even with false origin data, has its own exact-end test. It consequently lies in a finite union of fixed-word templates \(ac^ib\). The accepted exponents are ultimately periodic, which gives height-one expressions over the original letters. The incomplete remainder has the same kind of expression. The inner split starts from empty skip computations and gives height two; recovery makes those computations the skips for the outer split, giving height three. Finite Boolean recovery and concatenation with the remainder add no star. Tags, states, and residues serve only as finite indices in these expressions.

Monoid values and deterministic updates

If \(\Sigma=\emptyset\), its only languages are \(0\) and \(1\), both of height zero. Assume henceforth that \(\Sigma\) is nonempty, and fix a morphism \[T:\Sigma^*\longrightarrow M\] into a finite monoid \(M\). For a deterministic finite automaton, take \(M\) to be the finite monoid of state transformations induced by words, including the identity transformation. Its accepted language is a finite union of fibers of \(T\). Thus it suffices to construct a height-three expression for each fiber of every such morphism.

Letters occupy intervals \([a,a+1)\) with integer endpoints. For an available interval \([a,b)\), \(a\le b\), write \(T_{a,b}\) for its monoid value, with \(T_{a,a}=1_M\). Products are in reading order: \[T_{a,c}=T_{a,b}T_{b,c}.\] Let \(V=\mathbf F_2^M\) have basis \((e_m)_{m\in M}\). Each \(d\in M\) acts linearly on the right by \(e_m d=e_{md}\). This is the linearized right regular action (Almeida et al. 2009, sec. 3.1). It is faithful because \(e_{1_M}d=e_d\) identifies \(d\). Vectors are written on the left of their linear maps, so \(vLA\) means first apply \(L\), then \(A\). We will also use \(U=V\oplus\mathbf F_2\); the additional coordinate will turn affine maps on \(V\) into linear maps on \(U\). All vector spaces below are finite.

Put \(N_M=|M|!\). Finiteness gives \[ c^{i+N_M}=c^i\qquad(c\in M,\ i\ge |M|). \tag{1}\] Indeed two of \(c^0,\ldots,c^{|M|}\) agree, say \(c^a=c^b\) with \(0\le a<b\le |M|\). Powers are then periodic from exponent \(a\), with period \(b-a\), which divides \(N_M\). This includes \(|M|=1\).

A prefix code is a set \(E\subseteq\Sigma^+\) containing no proper-prefix pair. Its members will be called episodes. Every word in \(E^*\) has a unique factorization into episodes: the first factors of two proposed factorizations are comparable by the prefix relation and therefore equal, after which induction applies. The empty word has the empty factorization.

For \(D\subseteq E\), assign to each \(e\in D\) a deterministic total map \(G_e:S\to S\) on a fixed finite state set \(S\). On \(w=e_1\cdots e_r\), let \(G_w\) apply the updates in reading order; \(G_\varepsilon\) is the identity. The graph language from \(x\) to \(y\) on \(D^*\) is \[\{w\in D^*:G_w(x)=y\}.\] The indicated domain is part of this definition. The update is determined by the episode itself, independently of choices made by an expression that tests its graph.

Finite intersections can be expressed using union and complement and do not increase generalized star height. A finite language has height zero: write its words as concatenations of letters, use \(1\) for \(\varepsilon\), and take a finite union. Auxiliary finite indices below are never input letters.

The split identity

The next lemma separates two obligations. Every successful split must transmit the correct state and consume exactly one episode. Existence of a split is required only outside the domain that is to be skipped.

When \(D'=\emptyset\), the skip language \(W_{x,y}\) is \(1\) for \(x=y\) and \(0\) otherwise. Its height is zero, so this case of the lemma has height bound two. Notice also that condition (i) rules out a successful pair on the empty word. Independent choices in \(P_x\) and \(Q_y\) must satisfy it even when their proposed metadata disagree.

Removing affine corrections

We will deliberately alter an episode’s translation term to make its split possible. The following identity explains why this is harmless. The output on zero isolates the translation of a whole composite, even when none of its linear factors is invertible. The two computations must be required on the same word, which is why the expression uses an intersection.

A shift table that hides one entry

A cut can leave one interval product unreadable by either factor. We will replace the demand to know that product by a finite certificate that checks all of its possible values. To make such a certificate available, we need a deterministic affine correction with a constant coordinate line through every tuple, for every input state.

The order of quantifiers matters: the length is selected first, uniformly in the table of linear maps; a correction is then fixed for each table; only afterward may a tuple and input state select a successful coordinate. The product-action version in (OpenAI 2026b, Lemma 2.3) motivates this step, but an arbitrary table is needed for the second split below.

Fix one successful \(\beta_f\) for each of the finitely many possible functions \(f\) at these dimensions. The resulting map \(x\mapsto xf(\mathbf a)+\beta_f(\mathbf a)\) is now determined by the tuple and table, before any splitting choices are made. A prefix can certify its output using the other entries by checking every replacement for the omitted coordinate. The lemma promises a usable coordinate for each actual input, not one coordinate usable for all inputs at once. Nor does it restrict \(f\) to tables obtained from feasible word prefixes. This unrestricted table domain will be essential when a suffix computes hypothetical prefix values in Section 9.

A finite set of metadata and positions

Apply Lemma 5 with entry alphabet \(M\) and state spaces \(V\) and \(U\), and choose the resulting positive tuple lengths \(g\) and \(g'\), respectively. For the early schedule, a kind is a tuple \[ (j,x,y,\mathbf d_{-j},\psi),\qquad 1\le j\le g',\quad x,y\in U,\quad \mathbf d_{-j}\in M^{g'-1},\quad \psi:M\longrightarrow\operatorname{End}_{\rm lin}(U). \tag{15}\] The list \(\mathbf d_{-j}\) retains the indices and order of all entries except \(j\). The function \(\psi\) will record how later letters turn the monoid value of the early region into a linear update on \(U\). There is no feasibility restriction on any field: in particular, every total function \(\psi\) of the indicated type occurs. Let \(\kappa\) count these kinds. Make \(\mu\) distinguishable copies of each kind, for a positive integer \(\mu\) to be fixed below, and call the resulting roster \(\mathcal P\). It has \(N=\kappa\mu\) slots. Order them in consecutive blocks according to \(j=1,\ldots,g'\). The copies will let us lose some positions to false-origin ambiguity without losing any kind altogether.

Set \[ B=20(N+1)^3, \qquad r_i=4N^2i+i^2\pmod B\quad(1\le i\le N), \tag{16}\] and reserve residue \(r_i\) for slot \(i\). The ordered differences \(r_i-r_j\), for \(i\ne j\), are all nonzero and distinct modulo \(B\). To check this, suppose first that \(i>j\). As an integer the difference is \[(i-j)4N^2+(i-j)(i+j).\] The second summand lies strictly between \(0\) and \(2N^2\), so division by \(4N^2\) determines \(i-j\). The remaining summand then determines \(i+j\), and hence \(i,j\). Positive differences are distinct, as are their negatives. All signed differences lie in an interval of length less than \(B\), and no positive difference equals a negative one. Reduction modulo \(B\) therefore preserves their distinctness and nonzero values.

The later clock uses a separate tag set \(\Lambda\). A main tag has the form \[(j,u,A,C,\mathbf d_{-j},X,Y),\qquad 1\le j\le g,\quad 0\le u<B,\] where \(A,C\in M\), \(\mathbf d_{-j}\in M^{g-1}\), and \(X,Y\in V\). A periodic tag has the form \[(j,u,m_p,X,Y),\qquad 0\le j\le g,\quad 0\le u<B,\] where \(m_p\in M\) and \(X,Y\in V\). The form itself is part of the tag. The fields \(X,Y\) of a tag \(\alpha\) are denoted \(X(\alpha),Y(\alpha)\). In particular, the clock period and all marker inspection radii are absent from the tag fields. If \(m=|\Lambda|\), then \[m=B|V|^2\bigl(g|M|^{g+1}+(g+1)|M|\bigr).\] Choose \(\mu\) large enough that \[ \mu>20\bigl(c_{\rm cl}\log(2m)+4(g+1)\bigr)+10, \tag{17}\] where \(c_{\rm cl}\) is the constant in Lemma 6. Although \(m\) depends on \(\mu\), this requirement is not circular. The numbers \(\kappa,g,g'\) and the spaces \(V,U\) were fixed before \(\mu\). The displayed formulas make \(B\) polynomial in \(\mu\) and \(m\) a constant multiple of \(B\). The right side of (17) thus grows logarithmically, while the left side grows linearly. Choose and fix one such \(\mu\). From now on the roster, all residue classes, and the entire tag set are fixed; no clock period or inspection radius is a tag field.

The provisional clock and the early schedule

Apply Lemma 6 to \(\Lambda\) and the roster. Write its torus as \(\mathcal T\), its sets as \(I_\alpha,J_\alpha,W\), its roster targets as \(v_p\), and its common ball radius as \(\rho>0\). We first select a provisional additive map \(\varphi^0:\mathbf Z\to\mathcal T\). In each circle coordinate choose its speed to be \(1/n_i^0\), where the \(n_i^0\) are distinct sufficiently large primes greater than \(B\), and put \[R=\prod_i n_i^0.\] The set \[ \{\varphi^0(aB):0\le a<R\} \tag{18}\] is the full product grid with coordinate orders \(n_i^0\). Indeed, multiplication by \(B\) is invertible modulo every \(n_i^0\), and the Chinese remainder theorem prescribes all coordinate residues independently. The same assertion holds for any \(R\) consecutive representatives of a fixed residue class modulo \(B\). Choose these primes so large that the grid has covering radius less than \(\rho/3\) in the maximum circular metric, and is fine enough to approximate each target \(v_p\) strictly inside the perturbation tolerances of Lemma 6.

Put \(w_0=BR\). Realize the ordered roster by positive increasing integers \(p_1,\ldots,p_N\) such that \[ p_i\equiv r_i\pmod B, \qquad \varphi^0(p_i)\text{ is within the chosen tolerance of }v_{p_i}, \tag{19}\] and all ordered nonzero differences \(p_i-p_j\) are at distance greater than \(2w_0+2\) from each other and from \(0\). These requirements can be met inductively. For each slot, the grid property supplies an admissible integer in its reserved class, and adding multiples of \(BR\) leaves both that class and its provisional clock value unchanged. At the next insertion, place the new point so far to the right that all new positive differences exceed every old positive difference by more than \(2w_0+2\). The differences between two of these new differences are differences of previous points, which already have the required separation. Their negatives satisfy the same conditions. Also leave an integer gap between successive blocks of slots.

From this point, \(\mathcal P\) denotes this set of integer offsets, with each offset still carrying its original kind and copy label. Write \(h=\operatorname{diam}\mathcal P\). Choose fixed integer boundary offsets \[0=\beta_0<\beta_1<\cdots<\beta_{g'}\] so that every slot of block \(j\) lies strictly between \(\beta_{j-1}\) and \(\beta_j\). For a word beginning at \(s\), the corresponding early boundaries are \[ b'_j=s+\beta_j\qquad(0\le j\le g'), \tag{20}\] and its early candidate cuts are \(s+p\), \(p\in\mathcal P\).

The final clock and inner marker searches

The early positions are now fixed. We next choose the inner marker rule, and only then the prime factors of the final clock. Choose integers \[ d>10(2h+2w_0+5),\qquad K>3d^2, \tag{21}\] and obtain an inner marker rule of radius \(r\ge K\) from Lemma 7. Put \(N_M=|M|!\).

In each coordinate, approximate the provisional speed \(1/n_i^0\) by \(a_i/n_i\), where the \(n_i\) are distinct primes greater than \(d,N_M,B\) and \(1\le a_i<n_i\). Arbitrarily accurate such approximations exist by taking the primes sufficiently large and rounding \(n_i/n_i^0\) to an integer. Let \(\varphi\) be the resulting additive map and put \[ n=\prod_i n_i. \tag{22}\] The map \(\varphi\) factors through \(\mathbf Z/n\mathbf Z\). Approximate closely enough on the already fixed finite sets \(\mathcal P\) and \(\{aB:0\le a<R\}\) that \[ \begin{aligned} &\#\{(p,p')\in\mathcal P^2:p\ne p',\ a+\varphi(p')-\varphi(p)\in W\}\\ &\qquad\le c_{\rm cl}\log(2m)\qquad(a\in\mathcal T). \end{aligned} \tag{23}\] \[ \{\varphi(aB):0\le a<R\} \text{ has covering radius less than }\rho. \tag{24}\] For the first assertion, keep every \(\varphi(p)\) within the clock’s single allowed perturbation tolerance of its target. For the second, keep every value at an argument \(aB\), \(0\le a<R\), within the unused margin between the provisional covering radius and \(\rho\). Only finitely many arguments are involved, so one sufficiently accurate approximation satisfies both requirements. Every translate of this fixed net meets every clock ball of radius \(\rho\).

The construction now has the two properties it will use separately: the clock period has no small prime factors, while the useful \(R\)-term net and \(w_0=BR\) keep their earlier sizes. Replacing \(R\) by the final period here would lose this independence and is unnecessary.

Choose positive integers \(L_{\rm lag}\) and \(H_{\rm ext}\) with \[ B\mid L_{\rm lag},\qquad L_{\rm lag}>r+(|M|+2)d,\qquad H_{\rm ext}>L_{\rm lag}+ndN_MB+2d. \tag{25}\] Choose positive widths \(H_u\), indexed by \(0\le u<B\), each divisible by \(B\) and greater than \(2d\), with pairwise distances \[ |H_u-H_v|>2h+2\max(H_{\rm ext},w_0)+2 \qquad(u\ne v). \tag{26}\] For each fixed anchor in the false-origin count, distinct displacement residues will give distinct width indices. This spacing will separate the right endpoints of searches whose left endpoints lie in one short interval. Finally choose a positive multiple \(G\) of \(2B\) such that \[ G>10\bigl(\max_u H_u+H_{\rm ext}+r+K+d+w_0+1\bigr). \tag{27}\] All these requirements are lower bounds on successively chosen integers, so they are simultaneously satisfiable.

An episode beginning at \(s\) will have a sampling origin \(t=s+L\), where the fixed positive lag \(L\) will be chosen after all bounded windows are known. For any integer origin \(t\), define \[ o_j=(j+1)G,\qquad z_j(t)=t+o_j,\qquad f_j^u(t)=\text{the first inner marker in }[z_j(t),z_j(t)+H_u], \tag{28}\] for \(0\le j\le g\) and \(0\le u<B\). The value is \(\bot\) when the search finds no marker. Equality of search values means equality of absolute positions, or that both values are \(\bot\).

Let \(\mathcal H\) be the full finite set of offsets \(k-t\) in (29) and (30), over all their indicated indices. Choose an integer \[ w>\max(2h,\operatorname{diam}\mathcal H)+1. \tag{31}\] The next observation records exactly how the periodic schedule will supply clock choices when an inner marker search is absent.

The schedule is now complete except for its placement inside an episode. Main cuts separate the required marker products, and periodic cuts provide a fixed prefix product while sweeping the clock image. Both schedules have offsets divisible by \(B\). The next section puts all their windows, including the displaced windows used by false suffix hypotheses, strictly inside each episode. A separate marker rule there determines the end.

Two bounded end searches

Use Lemma 7 independently of the inner markers, with integer parameters \[ S_\bullet>4(h+w+1),\qquad d_\bullet>10BS_\bullet+10(h+w+1),\qquad K_\bullet>3d_\bullet^2. \tag{33}\] Call the resulting markers end markers and their inspection radius \(r_\bullet\ge K_\bullet\). For \(0\le u<B\) set \[ D_u^0=d_\bullet+uS_\bullet, \qquad D_u^1=3d_\bullet+uS_\bullet. \tag{34}\] The center of an end search is \(z_\bullet(t)=t+o_\bullet\), where the fixed offset \(o_\bullet\) will be placed below. At an integer origin \(t\), define \(\eta(t)\) and \(\zeta(t)\) by the following rule, using \(\sigma=0\) and \(1\), respectively: return the leftmost end marker \(m_e\) such that \[ |m_e-z_\bullet(t)|\le D_u^\sigma, \qquad u=(m_e-z_\bullet(t))\bmod B. \tag{35}\] Return \(\bot\) if there is no such marker. Residues used as indices always have representatives in \(\{0,\ldots,B-1\}\). These are bounded searches: the whole inspection is contained in the interval obtained by enlarging \([z_\bullet(t)-\max_uD_u^\sigma,z_\bullet(t)+\max_uD_u^\sigma]\) by \(r_\bullet\) on each side.

The eligible set for \(\eta(t)\) is contained in that for \(\zeta(t)\). This does not say that their returned markers coincide: the larger search may have an earlier eligible marker. The implication we will need also holds across nearby origins: \[ |t-t'|\le2h\text{ and }\eta(t')\ne\bot \quad\Longrightarrow\quad \zeta(t)\ne\bot. \tag{36}\] Indeed, the marker returned at \(t'\) is within \(\max_uD_u^0+2h\) of \(z_\bullet(t)\), whereas \[\min_uD_u^1=3d_\bullet> d_\bullet+(B-1)S_\bullet+2h=\max_uD_u^0+2h.\] It is therefore eligible at \(t\) regardless of its new residue index. This implication is why two search sizes are used.

If \(\eta(t)=\bot\), there is no end marker in \([z_\bullet(t)-d_\bullet,z_\bullet(t)+d_\bullet]\). The seed \[ [z_\bullet(t),z_\bullet(t)+K_\bullet) \tag{37}\] then has a period less than \(d_\bullet\) by Lemma 7. Its two-sided continuation with a period less than \(d_\bullet\) is unique: any two such continuations agree on the seed, whose length exceeds the product of their periods, so Lemma 8 identifies them. We shall use this continuation only when \(\eta(t)\) is absent.

Margins and the episode rule

We first identify every bounded window that must remain inside a complete episode. This prevents an incorrect origin or endpoint from making a required check disappear. Set \[\Delta=(\mathcal H-\mathcal H)\cup(\mathcal P-\mathcal P)\cup\{0\}.\] The first difference set contains every displacement of an outer suffix origin from the true origin at a genuine outer cut, even if the two factors choose different roles. The second contains all origin displacements used to decode an early cut. Both are fixed finite sets.

For inner data allow every origin displacement in \(\Delta\), followed by every additional integer shift in \([-w_0,w_0]\). Include all indices \(0\le u<B\), all inner marker inspections, the extended searches through \(H_u+H_{\rm ext}\), the short-period blocks and the finite portions of their continuations used in Lemma 10, and the finite cut schedules. This gives a bounded integer offset interval \([A_{\rm in},B_{\rm in}]\) relative to \(t\). For example, it may be chosen to contain every enlarged interval \[[o_j+\delta-v-r, o_j+\delta+v+H_u+H_{\rm ext}+K+r] \quad (\delta\in\Delta,\ 0\le v\le w_0),\] and every cut offset; enlarge it further if necessary to contain the \(|M|\) periods before the base cuts in Lemma 10. All these enlargements are finite and fixed at this point.

For end data allow every displacement in \(\Delta\) and every additional integer shift in \([-w,w]\). Include both end-search inspection windows, every seed, every possible bounded marker return, and the right endpoint of every seed. Collect them in a bounded integer interval \([A_{\rm end},B_{\rm end}]\) relative to \(z_\bullet(t)\). For clarity, an interval containing the following sets, over all \(\delta\in\Delta\) and \(|v|\le w\), is sufficient: \[[\delta+v-\max_uD_u^1-r_\bullet, \delta+v+\max(\max_uD_u^1+r_\bullet,K_\bullet)].\] In particular these intervals cover full sweeps of the allowed shifts, not merely the finitely many nominal origins. Neither interval depends on the still unchosen \(L,o_\bullet,L_{\rm tail}\).

Choose positive integers \(L,o_\bullet,L_{\rm tail}\) in this order so that \[ \begin{split} L+A_{\rm in}&>\beta_{g'},\\ o_\bullet+A_{\rm end}&>B_{\rm in},\\ L_{\rm tail}&>\max\{1,\max_uD_u^0+B_{\rm end}\}. \end{split} \tag{38}\] Now fix \(t=s+L\) for a word beginning at \(s\). Define its end anchor \(q_0\) as follows. If \(\eta(t)\) is present, put \(q_0=\eta(t)\). Otherwise use the unique periodic continuation of the seed in (37), and let \(q_0\) be the first letter position at or beyond the seed’s right endpoint where the word differs from that continuation. If that mismatch has not yet occurred in a finite word, the rule supplies no complete episode in that word. When \(q_0\) exists, the required endpoint is \[ b=q_0+L_{\rm tail}. \tag{39}\] All bounded end inspections and seed data required by the rule must be available, as must the letters through \(b-1\). A word is a complete episode if its own endpoint is exactly this \(b\). Let \(E\) be the language of such words, with their beginning normalized to \(s=0\). For each complete episode define the clock anchor \[ q=\begin{cases} \zeta(t),&\zeta(t)\ne\bot,\\ q_0,&\zeta(t)=\bot. \end{cases} \tag{40}\] These two anchors have different roles and may coincide. The endpoint is always \(q_0+L_{\rm tail}\). The clock instead uses \(q\), which is a bounded marker return whenever \(\zeta\) is present. For example, \(\eta\) may be absent and \(\zeta\) present; then the endpoint can occur arbitrarily late at a first mismatch while its clock anchor remains bounded. No later argument identifies \(q\) with \(q_0\) in this case.

Figure 1 summarizes the order just established. The large gaps also accommodate the false origins; they are not chosen anew after a suffix has made its guesses.

For every prefix or suffix test below, the letters needed for a check must be present in that test’s own argument and on its own reading side. An unavailable inspection or an invalid required product interval causes rejection; it never removes an origin from a universal check. The unbounded portions of the episode rule are continuation tests up to a proposed end. They do not require moving an unbounded inspection window before a cut. Lemma 9 supplies the more precise division of inner data between the two sides of an outer cut.

All these definitions commute with translation of positions. A standalone prefix reads from its beginning \(s\) to its end \(k\). A standalone suffix begins at \(k\); an origin specified as an offset from \(k\) need not itself carry a visible letter in that suffix. Applying the end rule at such an origin requires the end searches and seed in the suffix and its prescribed exact endpoint. It does not ask the suffix to validate omitted prefix letters.

A guard that forces the true end

At a proposed outer cut \(k\), let the suffix test all origins \[ \mathcal O_k=\{k-a:a\in\mathcal H\}. \tag{41}\] Choose once and for all a reference offset in \(\mathcal H\). The common end guard requires both \(\eta\) and \(\zeta\) to be constant across \(\mathcal O_k\), with equality of absolute positions or of the value \(\bot\). Require all the associated bounded inspections and seed blocks. The suffix must end exactly where the episode rule at the reference origin prescribes, and uses the clock anchor calculated there by (40).

We can now use the clock with genuinely independent prefix and suffix metadata. Even if their proposed roles differ, the guard ensures that the two clock arguments add to the true total \(\varphi(q-t)\).

The exceptional domain and a total affine update

Define \(Z(t)\) to mean that at least one of \(\eta,\zeta\) is not constant on \[\{t+v:v\in B\mathbb Z,\ |v|\le w\}.\] For a position \(Q\), let \(u=(Q-t)\bmod B\), with residues represented in \(\{0,\ldots,B-1\}\). Define \(A_*(t,Q)\) to be the disjunction of the following three conditions:

1. \(\varphi(Q-t)\in W\);

2. for some \(0\le j\le g\) and some integer \(v\) with \(|v|\le w_0\), \(f_j^u(t+v)\ne f_j^u(t)\);

3. for some \(0\le j\le g\), \(f_j^u(t)=\bot\), but the inclusive interval \([z_j(t),z_j(t)+H_u+H_{\rm ext}]\) contains an inner marker.

In the second condition the index \(u\) is held fixed as \(t\) is shifted. The search values are absolute positions, with \(\bot\) equal only to \(\bot\). Set \[ D=\{e\in E: Z(t)\ \text{or}\ A_*(t,q)\}. \tag{42}\] The episode determines both predicates without choosing a split. Thus \(D\) is a fixed language. In particular, failure of a particular choice of tag is not its definition; the same \(D\) must serve every input state and every pair of independently chosen tags.

For \(A,C\in M\), write \[ f_{A,C}(a_1,\ldots,a_g)\colon v\longmapsto vA a_1\cdots a_g C. \tag{43}\] This is a map from \(M^g\) into \(\operatorname{End}_{\rm lin}(V)\). For every such map, use the shift table \(\beta_{f_{A,C}}\) fixed in Lemma 5. We define \(F_e\colon V\to V\) on every complete episode, including every episode in \(D\):

1. If \(\mathcal E_{\varphi(q-t)}\) is the singleton off-diagonal edge \(\{(\alpha,\lambda)\}\), put \[ F_e(v)=vT_{s,b}+Y(\lambda)-X(\alpha)T_{s,b}. \tag{44}\]

2. Otherwise put \(u=(q-t)\bmod B\). If at least one \(f_j^u(t)\) is absent, put \(F_e(v)=vT_{s,b}\).

3. In the remaining case let \(l_j=f_j^u(t)\) for \(0\le j\le g\). Their order is \(l_0<\cdots<l_g\) by the schedule. Set \[A=T_{s,l_0},\qquad C=T_{l_g,b},\qquad d_i=T_{l_{i-1},l_i}\quad(1\le i\le g).\] Then put \[ F_e(v)=v f_{A,C}(\mathbf d)+\beta_{f_{A,C}}(\mathbf d). \tag{45}\]

These three cases define exactly one map on every episode. The first case is unambiguous by the clock alternative. The other cases cover all graphs contained in the diagonal, including the empty graph, with the actual residue and actual marker data. In the third case, \(A d_1\cdots d_g C=T_{s,b}\), so all three formulas have the same prescribed linear part. Hence \(F_e\) is total and deterministic even on \(D\), and no cancellation or inverse in \(M\) has entered its definition.

The two independently chosen tags

For each \(x,y\in V\) we define languages \(P_x,Q_y\) by finite unions over tags. A prefix factor is read on \([s,k)\), and a suffix factor on \([k,b)\). These positions describe the tests in their own relative coordinates; they do not give either factor access to the other one.

Every prefix test chooses a tag \(\alpha\), requires \(x=X(\alpha)\), chooses a cut of the form specified by that tag, and requires \[ \varphi(k-t)\in I_\alpha. \tag{46}\] Every suffix test chooses an independent tag \(\lambda\). It performs the shared-end guard of Lemma 13, using all origins \(k-a\), \(a\in\mathcal H\). More explicitly, both end searches \(\eta,\zeta\) must be constant over these origins; the suffix must end exactly as prescribed at one fixed reference origin; all the required seed and inspection data must be present. Let \(q\) denote the clock anchor so obtained. The suffix requires \[ y=Y(\lambda),\qquad \varphi(q-k)\in J_\lambda,\qquad u(\lambda)=(q-k)\bmod B. \tag{47}\] The field \(u(\lambda)\) is part of the suffix’s tag. The additional tests depend on the tag’s form as follows.

Correctness for arbitrary successful pairs

We now have the first split interface on all of \(E\), with the same updates \(F_e\) reserved for its skipped episodes. To complete the sequence computation, it remains to handle \(D^*\). The defining exceptional predicate, which was an obstruction to the clock construction, will serve as a witness to the origin at an earlier stencil cut. The next section proves that this witness is usually unique across the entire stencil.

A bounded list of possible clock anchors

Fix a complete episode \([s,b)\) and its actual origin \(t=s+L\). For every pair \(p,p'\in\mathcal P\), set \[\delta=p-p',\qquad \tau=t+\delta.\] The distinct-slot differences are distinct as integers and modulo \(B\), are separated from one another by more than \(2w_0+2\), and satisfy \(|\delta|\le h\). The identical-slot pairs all give \(t\). Evaluate the bounded larger end search \(\zeta(\tau)\) on the actual episode.

If one of these larger searches is absent, then every smaller search \(\eta(\tau)\) in this collection is absent. Indeed, a marker eligible for a smaller search at any one origin has distance at most \(\max_u D^0_u+2h\) from the end-search center at any other origin. The inequality \[ \max_u D^0_u+2h<\min_u D^1_u \tag{52}\] makes it eligible for that larger search, whatever residue index it has at the latter origin. This would contradict the absent larger search.

In this absence case the seeds at all these origins have short periods. Their starting positions differ by at most \(2h\); the seed length and marker separation ensure an overlap of at least \(d_\bullet^2\). Lemma 8 gives the same two-sided periodic continuation for all seeds. They agree with the episode on their union, so their first subsequent mismatch is the same position \(q_0\). This is the actual episode’s mismatch anchor, because its own smaller search is absent. Define \[ Q_\tau= \begin{cases} \zeta(\tau),&\zeta(\tau)\ne\bot,\\ q_0,&\zeta(\tau)=\bot. \end{cases} \tag{53}\] The second case is used only when a larger search is absent, so the preceding argument always supplies its \(q_0\). In particular \(Q_t=q\).

Counting every false origin in the stencil

We now count the ordered pairs with \(p\ne p'\) for which the translated origin satisfies the exceptional predicate. All marker decisions can be made in one common two-sided extension: the margin construction makes every inspection used below internal to the episode, including the shifted searches.

There are two levels to this estimate. At a fixed anchor \(Q\), distinct displacement residues give distinct width indices, so right-end failures are sparse. The anchor list then permits at most twenty such counts. The estimate includes all ordered pairs; no knowledge of the correct kind was used to obtain it. We can now turn it into a decoder without assuming that a suffix’s proposed endpoint is correct.

A decoder that also verifies its endpoint

We next give an actual test on a suffix beginning at \(k\). For each slot \(p'\in\mathcal P\) form the candidate origin \[ \tau_{p'}=k+L-p'. \tag{57}\] These are positions relative to the suffix; the origin itself need not be a visible letter. All of the following inspections, including every shifted search needed to evaluate \(Z\) and \(A_*\), are mandatory. If a required window is absent from the suffix, the test rejects.

First compute every \(\zeta(\tau_{p'})\). If at least one is absent, require all \(\eta(\tau_{p'})\) to be absent, read every candidate seed, and require the suffix to end exactly according to the end rule at one fixed reference candidate. This includes agreement with that reference seed’s periodic continuation up to its first subsequent mismatch, and exactly \(L_{\rm tail}\) letters from that mismatch to the proposed endpoint. Denote its verified mismatch position by \(q_{\rm ref}\). For candidate origins with absent \(\zeta\), use \(Q_{\tau_{p'}}=q_{\rm ref}\). For every candidate with present \(\zeta\), always use \(Q_{\tau_{p'}}=\zeta(\tau_{p'})\). If all the larger searches are present, no reference mismatch test is needed at this step; all these \(Q\)’s are bounded search returns.

Now require that exactly one slot \(p'\) satisfy \[ Z(\tau_{p'})\ \text{or}\ A_*(\tau_{p'},Q_{\tau_{p'}}). \tag{58}\] This is uniqueness over all slots, without any restriction to particular kinds or guessed table values. Finally, after decoding this slot, require exact consumption according to the end rule at its candidate origin in all cases, including the case where all larger searches were present.

Figure 2 separates the two anchor roles and records the order of these end checks. The reference guard belongs only to the branch with an absent larger search. The decoded origin’s exact end is checked in both branches.

The two end-search sizes are essential to this test. If a false origin has absent larger search, all the smaller searches, including the true one, are absent and the shared mismatch is already the actual endpoint anchor. Otherwise every candidate clock anchor is bounded data. Thus the decoder never needs to look for an unverified future mismatch beyond a short true episode merely to decide a false origin’s witness.

A total table computed from later letters

Write \(b'_*=b'_{g'}\), the last fixed stencil boundary, and let \(e=[s,b)\in D\). The homogeneous lift of \(F_e\) is the linear map \(\widehat F_e\colon U\to U\), where \(U=V\oplus\mathbf F_2\). If \(F_e(v)=vL_e+\gamma_e\), then \[ \widehat F_e(v,c)=(vL_e+c\gamma_e,c). \tag{59}\] All marker searches, outer boundaries, and end data occur after \(b'_*\) by Lemma 11. Hence the suffix of the episode starting at \(b'_*\), together with its origin and anchors, determines the following table for every \(m'\in M\).

Set \(D_b=T_{b'_*,b}\) and \(m_b(m')=m'D_b\). Define an affine map \(H_{e,m'}\colon V\to V\) by the same three cases as \(F_e\):

1. If the actual clock graph is the singleton off-diagonal edge \(\{(\alpha,\lambda)\}\), put \[H_{e,m'}(v)=v m_b(m')+Y(\lambda)-X(\alpha)m_b(m').\]

2. Otherwise use \(u=(q-t)\bmod B\). If at least one actual \(f_j^u(t)\) is absent, put \(H_{e,m'}(v)=v m_b(m')\).

3. In the remaining case all these searches are present; write their values as \(l_0<\cdots<l_g\), and put \[A(m')=m'T_{b'_*,l_0},\qquad C=T_{l_g,b},\qquad d_i=T_{l_{i-1},l_i}.\] With \(f_{A(m'),C}\) from (43), put \[H_{e,m'}(v)= v f_{A(m'),C}(\mathbf d) +\beta_{f_{A(m'),C}}(\mathbf d).\]

Define \[ \psi_e\colon M\longrightarrow\operatorname{End}_{\rm lin}(U), \qquad \psi_e(m')=\widehat H_{e,m'}. \tag{60}\] The hat denotes the homogeneous lift in (59). For every \(m'\), including an impossible prefix product, associativity in the third case gives \[A(m')d_1\cdots d_g C =m'T_{b'_*,l_0}T_{l_0,l_g}T_{l_g,b} =m'T_{b'_*,b}=m_b(m').\] Thus the affine formula and its linear lift are defined for every entry. Only after the table has been defined do we substitute the actual early product, obtaining \[ \psi_e(T_{s,b'_*})=\widehat F_e. \tag{61}\]

Every letter-dependent quantity here is read after \(b'_*\): marker positions, anchor data, inter-boundary products, and products from \(b'_*\) to later positions. The hypothetical value \(m'\) is simply a finite algebraic input. The calculation does not search for omitted prefix letters, and it does not query graph languages for sequences of episodes.

Apply exactly the same formulas under a proposed suffix origin once its end rule and all necessary data are available. If a required interval is missing or its endpoints are in the wrong order, reject the entire suffix test. Do not discard that origin, and do not discard individual values of \(m'\) from the table. This separates the availability of actual suffix letters from the total algebraic domain of \(\psi_e\). At the true origin all required intervals are available by the margin lemma.

The affine update on the exceptional domain

For \(1\le i\le g'\) put \[d'_i=T_{b'_{i-1},b'_i}.\] For any table \(\psi\colon M\to\operatorname{End}_{\rm lin}(U)\), define \[ f'_\psi(a_1,\ldots,a_{g'})=\psi(a_1\cdots a_{g'}). \tag{62}\] Use the fixed shift table \(\beta_{f'_\psi}\) supplied by Lemma 5 with state space \(U\) and dimension \(g'\). On every \(e\in D\) define \[ G_e(x)=x f'_{\psi_e}(\mathbf d')+ \beta_{f'_{\psi_e}}(\mathbf d'), \qquad x\in U. \tag{63}\] This is a deterministic total affine map on \(U\). Its linear part is \(\widehat F_e\), because \(d'_1\cdots d'_{g'}=T_{s,b'_*}\) and (61) applies.

The kinds in the stencil were chosen to contain all tuples \[(j,x,y,\mathbf d'_{-j},\psi),\] where \(1\le j\le g'\), \(x,y\in U\), \(\mathbf d'_{-j}\in M^{g'-1}\), and \(\psi\colon M\to\operatorname{End}_{\rm lin}(U)\) is arbitrary. The \(\mu\) copies of a kind have distinct cut offsets but the same fields. A cut of block \(j\) lies strictly inside \((b'_{j-1},b'_j)\), so all listed block products except the omitted \(j\)th product can be checked on one side or the other.

For \(x,y\in U\) define inner prefix and suffix languages \(\widetilde P_x,\widetilde Q_y\) as follows. A prefix chooses a slot \(p\in\mathcal P\) and has exactly length \(p\), so its endpoint is \(k=s+p\). If the slot’s kind is \((j,x_p,y_p,\mathbf a_{-j},\psi)\), it requires \(x_p=x\) and checks all listed earlier block products \(a_i=d'_i\) for \(i<j\). For \(a\in M\), write \(\mathbf a[j\leftarrow a]\) for the tuple formed by inserting \(a\) into the listed entries at position \(j\). The prefix also checks the finite certificate \[ x_p f'_\psi(\mathbf a[j\leftarrow a]) +\beta_{f'_\psi}(\mathbf a[j\leftarrow a]) =y_p\qquad(a\in M). \tag{64}\] The prefix does not try to check the later entries or the table \(\psi\) against letters it cannot see.

A suffix beginning at \(k\) performs the complete decoder of Lemma 17, including its reference end guard when called for and its final decoded-origin end guard. Let \(p\) be its decoded slot and use its kind \((j,x_p,y_p,\mathbf a_{-j},\psi)\). At the decoded origin the suffix computes the actual searches, anchors, and all entries of (60). It requires that resulting table equal the slot’s \(\psi\), checks \(a_i=d'_i\) for \(i>j\), and requires \(y_p=y\). The comparison of tables is equality on every input \(m'\in M\). Each required interval starts on or after the suffix’s beginning: in particular, the displacement of \(b'_*\) from \(k\) is the fixed positive offset \((b'_*-s)-p\), since every stencil slot precedes the last stencil boundary. The margin lemma places all the data for the table after that boundary.

We have now obtained both split constructions with their full all-input guarantees. The inner updates \(G_e\) have linear parts \(\widehat F_e\), and the outer updates \(F_e\) have linear parts equal to the original monoid action. The remaining task is to express each domain and each individual prefix or suffix test with the claimed height over the original alphabet, and then apply affine recovery and the split identity in this order.

Periodic templates and exact-end checks

An exact end check at a fixed candidate origin provides precisely the template cover required by this lemma. If the smaller end search \(\eta\) returns a marker, that marker has a bounded offset and the end is bounded. Otherwise its seed is a fixed-length word at a fixed position, with a short-period continuation. Let \(a\) be the bounded word from the argument’s own beginning to the seed’s right endpoint. Make finite choices of \(a\), the continuation’s period and phase, and the tail of length \(L_{\rm tail}\) starting at the first mismatch. If the mismatch follows \(i\) full copies of the period word and one partial copy, put the fixed partial copy and tail into \(b\) in (65). Require the first letter of the tail to differ from the periodic continuation. These choices give a finite template cover, with bounded cases handled separately.

This is a statement about the suffix language itself. Its proposed origin is one of finitely many offsets from its own beginning, and its own end check yields the cover whether or not that origin could belong to a successful paired split. There is no ambient-episode assumption here.

Multiple end guards also cause no additional unbounded search. Every guard that uses a mismatch requires that mismatch at the proposed argument end minus \(L_{\rm tail}\). After choosing its seed and period in finite cases, it tests agreement up to that position and disagreement there. The reference guard and decoded-origin guard are therefore both among the comparisons of Lemma 19. A missing seed or window rejects the test, rather than making the template argument conditional on inaccessible letters.

The individual component languages

Words with no complete episode prefix

Define the final remainder language \[N_{\rm end}=\neg(E\,\neg0).\] Since \(\neg0=\Sigma^*\) has height zero, this language has height at most one by Proposition 20. We also need to retain the monoid product on a remainder.

Two splits and the main theorem