A word over a finite alphabet Sigma is a finite sequence of letters. The empty word is epsilon. A language is any set of words. A finite automaton recognizes a language by reading a word left to right and updating a state after each letter; a deterministic finite automaton (DFA) has one transition per letter and state, one starting state, and a set of accepting states. A language is regular if some DFA accepts exactly its words.
Generalized regular expressions construct languages from the constants 0 (the empty language) and 1 = {epsilon} and from the letter languages {a} for a in Sigma, using four operations: union (alternation), concatenation (sequence), complementation inside Sigma* (negation), and Kleene iteration (repetition, written P*). Height measures nested iteration. It is defined recursively: 0, 1, and each {a} have height zero; union and concatenation contribute the maximum of their operands' heights; complement contributes the same height as its operand; and P* contributes one more than the height of P. Expressions of height zero are exactly the star-free ones, built from constants and letters by the first three operations alone.
The generalized star height h_Sigma(L) of a regular L subset of Sigma* is the least height of a generalized expression over Sigma denoting L. Uniform boundedness asserts that one integer dominates h_Sigma(L) over all choices of Sigma and L.
Theorem. For every finite alphabet Sigma and every regular language L over Sigma, h_Sigma(L) <= 13.
The theorem answers the uniform question affirmatively. It does not settle whether height one suffices for every regular language, nor does it produce the minimum of h_Sigma(L) for a particular L. Straubing's 2002 LATIN lecture separates the two questions and observes that no regular language of generalized height greater than one was then known.
./straubing-2002.pdf
The ordinary star height counts the same way but forbids complement. Eggan introduced it and tied its lower bounds to the transition graph of a deterministic automaton. Dejean and Schutzenberger produced ordinary-height examples over a binary alphabet. Those lower bounds use expressions without complement and so do not transfer to the generalized model. Schutzenberger's 1965 theorem locates the star-free languages exactly at height zero: a language is star-free if and only if it is recognized by a finite aperiodic monoid, and the whole alphabet is the complement of the empty language.
./eggan-1963.pdf
./dejean-schutzenberger-1966.pdf
./schutzenberger-1965.pdf
Several algebraic classes are known to have height one. The 1992 Pin-Straubing-Therien survey recalls Henneman's result for finite abelian groups and extends height one to languages recognized by finite nilpotent groups of class two. Bourne and Ruskuc reached height one for languages recognized by finite Rees zero-matrix semigroups over abelian groups. Place and Zeitoun's 2017 CSR lecture places the ordinary and generalized problems in the broader concatenation-hierarchy landscape. Cotumaccio's 2025 Bulletin of the European Association for Theoretical Computer Science column still lists generalized star height among open problems connecting automata and data compression.
./pst-1992.pdf
./bourne-ruskuc-2016.pdf
./place-zeitoun-2017.pdf
./cotumaccio-2025.pdf
A separated-marker device from topological dynamics supplies the last external ingredient. Krieger's 1982 lemma places markers at mutual distance at least d while forcing the markerless regions to be locally periodic blocks of bounded length. Meyerovitch's 2025 embedding theorem for multidimensional subshifts uses a clopen form of the same idea together with a finite merging argument. The precise finite-window statement on which the affine construction relies is proved from first principles with explicit bounds.
./krieger-1982.pdf
./meyerovitch-2025.pdf
The argument runs through a finite monoid attached to the DFA. Let M be the monoid of state transformations induced by words of Sigma, the identity included. The product of a word in M determines acceptance: if q_0 is the initial state, a word w is accepted exactly when q_0 T_w is accepting. The desired language is the union, over the finitely many m in M sending q_0 into the accepting set, of the languages {w : T_w = m}. Finitely many height-bounded languages combine by union without increasing height, so the theorem reduces to bounding, for each m, the generalized height of {w : T_w = m}.
Positions are the integer gaps between successive letters; the letter at position j occupies the unit interval [j, j+1). A factor on [a, b) has length b - a and monoid value T[a, b]. Composition follows reading order: T[a, b] T[b, c] = T[a, c]. A right action of T[a, b] on a finite vector space maps v to v T[a, b]; the space with formal basis (e_m)_m in M carries a faithful action by e_m d = e_{md} for each letter transformation d, and the distinguished vector e_1 then determines d. Every vector space has finitely many basis elements and lives over the two-element field.
A prefix code is a set E of nonempty words none of which is a proper prefix of another. Every word in E* factors uniquely into members of E: two distinct factorizations must disagree at a first factor, and one of the two would be a proper prefix of the other. Members of E are called episodes. For D subset of E, let each e in D carry a deterministic total update G_e on a finite state set S. For a sequence w = e_1 ... e_r in D*, write G_w for the reading-order composite; the empty sequence corresponds to the identity. The graph test from x to y on D* is the language of w in D* with G_w(x) = y. Totality and determinism refer to the word itself, not to any metadata or decomposition of a test expression.
Intersections are expressed over Sigma as negations of negations, so they do not increase height; the remaining Boolean combinations are assembled similarly. A fixed finite language has height zero, being a finite union of concatenations of letters with the empty word represented by 1. That remark applies only when the entire argument of the test has bounded length.
Strategy. The recursion replaces graph languages on a class D of episodes by graph languages on a subclass D', one episode class at a time. At each step, prefix languages P_x and suffix languages Q_y split each episode at a cut. The prefix verifies the local state before the cut; the suffix verifies the local state after. A single split identity assembles the sequence of successful splits into a graph language, using the D' graph language for episodes that never get split. Height cost is explicit: if D, P_x, and Q_y have height at most 1, 0, and 1, and all D' graph languages have height at most H, then the D graph languages have height at most max(2, H + 1).
Three constructions make a bounded chain of splits sufficient. First, an affine update is recoverable from its values at any two points, so a split identity valid for linear updates extends to affine ones once a controlled error is absorbed into a fixed correction. Second, an algebraic tag clock confines every disagreement between the two independent sides of a split to a unique bilinear edge, and that edge yields a constrained affine correction whose linear part equals the target. Third, prediction trials and markerless windows produce cuts for every input; failure of either mechanism falls into one of five explicit residual types, each eliminated in one aligned stage that itself costs two splits.
The chain has twelve split applications. Two are outer, one main and one periodic-window. Five aligned stages contribute two each. A final affine-to-linear recovery converts the composed updates into the original graph language. Heights rise from 0 at the base to 13 at the top.
Fix a class D subset of E, a subclass D' subset of D, and deterministic total updates G_e for each e in D. Let P_x and Q_y be families of languages over Sigma indexed by x, y in S. The split identity requires two conditions on these data:
(i) whenever w in D* and uv is a prefix of w with u in P_x and v in Q_y, the word w begins with a single episode e, the factorization uv equals e, and G_e(x) = y;
(ii) for every e in D minus D' and every x in S there exists a split e = uv with u in P_x and v in Q_{G_e(x)}.
Condition (i) quantifies over every pair of independently accepted witnesses. Equality of the metadata attached to a cut is not automatic; it must be forced by the actual tests, or any disagreement must be absorbed into the declared update without disturbing the target map.
Lemma (Split identity). Write W_{x,y} for the graph test on (D')*. Under (i) and (ii) the exact graph test on D* equals
D* intersect ( W_{x,y} union (union over a of W_{x,a} P_a) (union over b, c of Q_b W_{b,c} P_c)^* (union over r of Q_r W_{r,y}) ).
Height accounting follows immediately: if D, P_x, Q_y have height at most 1, 0, 1 respectively, and every W_{x,y} has height at most H, then the new graph tests have height at most max(2, H+1).
Proof. Take a word accepted by the right side. Its membership in D* fixes its actual episode parsing. In the nontrivial branch, the initial W-factor is a sequence of D'-episodes, and prefix-code uniqueness forces these to be the actual initial episodes. The adjoining P_x Q_y factor now begins at a true episode boundary, and (i) forces it to be exactly the next episode and to supply the correct indexed update. The next W-factor consumes actual skipped episodes. Induction over the finite number of starred factors establishes the claimed whole-update result. The W_{x,y} branch handles words that admit no explicit split.
Conversely, given a genuine episode sequence in D*, split every episode outside D' using (ii) and collect consecutive skipped episodes into W-factors. Deterministic composition supplies the intervening state indices. If every episode is skipped, use W_{x,y}; that branch also covers the empty word.
For the height claim, D* has height at most 2. The starred middle factor has height at most 1 + max(1, H). All Boolean operations and concatenations fit the stated maximum.
When D' is empty, the bottom graph tests are 1 for equal states and 0 for unequal states; thus the recursion terminates with height-zero initial tests.
Lemma (Affine recovery). Suppose each episode update acts on a fixed finite vector space V by the affine map v -> v A_e + b_e. Exact graph tests for the composed affine update on V determine, by finite Boolean operations, the graph tests for the composition of the linear parts A_e.
Proof. Composing v A + b with v C + d gives v (A C) + (b C + d), so the linear part of the composed update g_w is g_w(v) - g_w(0). If R_{x,z} denote the graph tests for g_w, the language for linear output y from linear input x is the union over z of R_{x, y+z} intersect R_{0,z}, both on the same word and hence describing the same map.
Associated with any affine map f(v) = v A + b is the homogeneous linear self-map of V plus F_2 defined by (v, c) -> (v A + cb, c). These lifts compose, and on the slice c = 1 they recover f. Every map of a finite set has, similarly, a unique linear extension sending each basis vector to the basis vector of its image; neither device needs invertibility.
Prediction trials. Fix a representation of M on a finite vector space U and put J = |U|^2. A trial has endpoints and checkpoints B = z_0 < z_1 < ... < z_J < z_{J+1} = C. Its block j is an ordered set of potential cuts strictly between z_{j-1} and z_j. Enumerate all pairs of vectors in U as (x_j, y_j) for 1 <= j <= J. A prediction is a tuple p = (p_1, ..., p_{J+1}) in M^{J+1}; write T_* for the product p_1 ... p_{J+1}, and T for the actual interval product T[B, C].
Call block j ideally eligible if x_j T_* = y_j, and T[z_{i-1}, z_i] = p_i for 1 <= i < j, and T[z_j, C] = p_{j+1} ... p_{J+1}. Call the trial perfectly predicted if every actual interval product equals its predicted p_i.
Lemma (Prediction trial). There is a deterministic shift beta in U, defined from the actual trial word and its prediction, such that every ideally eligible pair satisfies y_j = x_j T + beta. A perfectly predicted trial has an eligible block for every possible input vector.
Proof. Suppose h < j are eligible blocks. The prefix conditions for j determine every actual interval through z_h, and the suffix condition for h determines the product from z_h to C. Hence T = T[B, z_h] T[z_h, C] = (p_1 ... p_h)(p_{h+1} ... p_{J+1}) = T_*. This uses multiplication only, without cancellation.
If T = T_*, every eligible pair fits beta = 0. If T is not T_*, at most one block is eligible; set beta to its forced shift y_j - x_j T, or to zero if no block is eligible. These rules define beta on every trial. For a perfect prediction, the block for (x, x T) is eligible for each x.
The conclusion for two eligible blocks is equality of the whole products T = T_*. It does not assert that the individual factors in the prediction tuple are correct; perfect prediction is the separate stronger condition that yields eligibility at every input.
The trial is instrumented as an affine action v -> v T + beta, implemented by adding beta at its end. At a cut inside block j, the prefix verifies arrival at B with vector x_j, the predicted transfer, and every preceding interval condition. The suffix verifies the product from z_j to C and continues from vector y_j at C. If these checks share the same trial data, the previous lemma proves the transfer without either side learning the whole shift.
Whenever the eventual computation passes through an entire other trial, the associated shift is computed using ideal eligibility from the definition above. Tag failures, decoding failures, and the choice of a split never affect that shift; this convention will keep every episode update deterministic.
The tag clock. A prefix and a suffix may independently choose metadata. The clock is a finite residue construction that forces either agreement of the two choices or a single permitted off-diagonal pair, at the cost of spoiling at most logarithmically many ordered pairs of cut copies. Concretely, the tags are elements of a finite set Lambda of size m; the roster is a finite set R whose elements are the potential cut copies; a multiplicative bound B > 0 is fixed in advance.
Lemma (Tag clock). For every finite set Lambda of size m, every finite set R, and every B > 0 there are a positive integer n, subsets I_alpha, J_alpha of Z/n for alpha in Lambda, a set W subset of Z/n, and residues v_p in Z/n for p in R, with the following four properties.
(i) Every prime factor of n exceeds B.
(ii) For every ell in Z/n the directed graph E_ell = {(alpha, beta) in Lambda^2 : ell in I_alpha + J_beta} is either contained in the diagonal or is exactly one ordered pair (alpha, beta) with alpha != beta.
(iii) If ell not in W, then E_ell is the full diagonal.
(iv) For every u in Z/n, |{(p, p') in R^2 : p != p', u + v_{p'} - v_p in W}| <= c_cl log(2m), where the absolute constant c_cl = 1,300,000 is valid. It does not depend on B, m, or |R|.
The ordered-pair estimate controls false guesses of a word's origin. Choose integer cut offsets congruent to their assigned roster residues. If an actual cut has offset p from an origin t, reading it as offset p' instead gives candidate origin t + p - p'. For a fixed end anchor q its total residue is q - t + p' - p. Property (iv) therefore bounds, even when the roster has many copies of each kind, how many such wrong candidates have bad total residue.
Proof. The construction is carried out in a product of finitely many cyclic coordinates, and the product is identified with a single cyclic group at the end. Set a = ceil(64 log(2m)), b = ceil(log_2 m), K_cl = 400, r = |R|. The constant K_cl is fixed once and for all.
First coordinates. Choose a left/right partitions of Lambda (empty sides permitted) so that, whenever alpha != beta and {alpha, beta} != {gamma, delta}, some partition places alpha on the left, beta on the right, and gamma, delta on the same side. To see that such a family exists, assign each tag a side independently with probability 1/2. The required assignment for a fixed quadruple is feasible: send both members of {gamma, delta} to the left if the set meets alpha, to the right if the set meets beta, and either way if it avoids {alpha, beta}. The excluded equality ensures alpha and beta cannot be forced onto the same side. Specifying sides for at most four distinct tags then has probability at least 1/16. With a independent partitions the expected number missed is at most m^4 (15/16)^a <= m^4 exp(-a/16) <= m^4 (2m)^{-4} = 1/16 < 1. The number missed is an integer, so some choice misses none.
Choose b partitions of Lambda into Type 1 and Type 2 that separate every two distinct tags; when m = 1 set b = 0 and there are no such partitions. Each Type partition receives a batch of coordinates as follows. List every ordered list of K_cl directed pairs (p, p') of distinct roster labels whose underlying undirected edges are distinct and form a forest. A forest here is a finite simple graph with no cycles. Give each such list its own dedicated coordinate in the batch, and add spare coordinates if necessary to make the batch size positive and odd. All such lists together form a finite set. This defines a finite coordinate set C_before any prime orders are chosen.
First coordinates: tag semantics. Choose pairwise distinct primes N_c, one for each coordinate c in C, exceeding max(B, 400, 2^{r+1}). Such primes exist recursively: the product of all primes at most any finite bound, plus one, has a prime divisor exceeding that bound. Write G for the product of Z/N_c over c in C. On the circle T = R/Z identify x/N_c with its point and write ||z||_T = min over integers k of |z - k|, with dist_T to a finite set taken as the minimum.
In a coordinate attached to a left/right partition, impose the following requirements. If alpha is on the left, I_alpha contains {0} and J_alpha excludes 0. If alpha is on the right, I_alpha excludes 0 and J_alpha contains {0}. A nonzero total is produced by a diagonal pair: put the total in the required nonzero summand and zero in the other. At total zero, no edge between two tags on the same side is possible, since it would have exactly one nonzero summand.
Suppose now that an off-diagonal edge alpha -> beta occurs at a total ell in G. For any (gamma, delta) with the same separation constraint, choose its separating partition. The edge alpha -> beta forces zero total in that coordinate because both its summands are required to vanish. The competing edge gamma -> delta is impossible there because its tags sit on the same side. The only other edge that could coexist with alpha -> beta is therefore its reversal beta -> alpha; and this argument also excludes every diagonal edge, because the constraints explicitly allow gamma = delta.
Type 1 batches. In a batch of coordinates, put A = {0, 1, 3}/6 and D = {2, 4, 5}/6 inside T. For a tag of Type 1 in this batch, require in every coordinate c of the batch that every element of I_alpha stay within circle distance 1/16 of A and every element of J_alpha stay within 1/16 of D.
The sums of the two centre sets cover every sixth of the circle: {0, 1, 3} + {2, 4, 5} = Z/6. Any target z in T therefore lies within 1/12 of a sum a' + d' of two centres. Choose a signed correction theta with |theta| <= 1/12 so that z = a' + d' + theta on the circle. The continuous summands a' + theta/2 and d' + theta/2 are then each within 1/24 of their respective centres. If z happens to be a grid point of Z/N_c, round the first summand to the nearest grid point and let the second be z minus that rounded value. Both summands land on the grid and each changes by circular distance at most 1/(2 N_c). Since N_c > 24, 1/24 + 1/(2 N_c) < 1/16. The Type 1 sumset is therefore the entire batch group, with independent choices in each coordinate.
The two centre sets are at circular distance at least 1/6. Consequently every Type 1 difference i - j satisfies ||(i_c - j_c)/N_c||_T >= 1/6 - 2/16 = 1/24 in every coordinate of its batch.
Type 2 batches. Suppose a batch has 2s + 1 coordinates. Call a coordinate value small if its circular distance from zero is at most 1/100. For a tag of Type 2 in this batch, require that at least s + 1 of the batch coordinates be small, for both I_alpha and J_alpha. There are no restrictions on the remaining coordinates.
Their sumset contains every target vector z with at least one small coordinate. At that coordinate set the first summand equal to z and the second to zero, both small. Partition the other 2s coordinates into two sets of size s. On the first set make the first summand zero, and on the second set make the second summand zero; in each coordinate the remaining summand is determined by the target. Both vectors have at least s + 1 small coordinates. Conversely, two vectors both satisfying the majority condition must have overlapping sets of small coordinates. Every Type 2 difference therefore has ||(i_c - j_c)/N_c||_T <= 2/100 in at least one coordinate of its batch. This argument also handles a one-coordinate batch with s = 0.
Exclusive graph alternative. Define each I_alpha, J_alpha inside G by imposing all its first-coordinate and every batch requirement; these concern disjoint blocks. An off-diagonal edge can coexist only with its reversal inside G. Suppose both alpha -> beta and beta -> alpha occur. Then there are vectors i_alpha in I_alpha, j_alpha in J_alpha, i_beta in I_beta, and j_beta in J_beta with i_alpha + j_beta = ell = i_beta + j_alpha and i_alpha - j_alpha = i_beta - j_beta. Choose a Type partition separating alpha and beta. In its batch the common difference would satisfy both the 1/24 lower bound from Type 1 and the 2/100 upper bound from Type 2, which is impossible because 2/100 < 1/24. This proves part (ii) inside G.
Let W be the union inside G of two kinds of obstruction: (a) a first coordinate of the total is zero; (b) in some Type batch none of the total's coordinates is small. If ell not in W, every diagonal pair has a decomposition of ell in every first coordinate and every batch, by the sumset arguments above. Combining these decompositions gives ell in I_alpha + J_alpha for every alpha. The exclusive graph alternative then forces the graph to be the full diagonal, giving (iii). No converse statement about W is needed.
Roster values in first coordinates. Enumerate R as p_0, ..., p_{r-1}. In every first coordinate set (v_{p_j})_c = 2^j mod N_c. The nonzero ordered integer differences 2^j - 2^i (with j > i) are all distinct: the factorization 2^j - 2^i = 2^i (2^{j-i} - 1) determines i as the largest power of two dividing the difference, and then determines j; the sign distinguishes the reverse ordering. For r >= 2 every signed difference lies between -(2^{r-1}-1) and 2^{r-1}-1; by the prime threshold its range has length less than N_c, so the differences remain distinct modulo N_c. Given any u in G, at most one ordered pair p != p' can satisfy u_c + (v_{p'})_c - (v_p)_c = 0 in this coordinate. The same conclusion holds when r <= 1, since there are no such pairs.
Roster values in a dedicated coordinate. Consider a coordinate c dedicated to a list of directed pairs (pi_j, pi'_j) for 0 <= j < K_cl. Choose d_j in Z/N_c by rounding j/K_cl to the nearest grid point, so ||d_j/N_c - j/K_cl||_T <= 1/(2 N_c). Prescribe (v_{pi'_j})_c - (v_{pi_j})_c = d_j. To realise these prescriptions, root each tree component and assign its root value zero. On traversing an edge to a previously unassigned vertex, add d_j if traversing from pi_j to pi'_j, and subtract d_j if traversing in the opposite direction. Absence of cycles means that each new vertex is assigned once, with no further consistency condition. Give isolated roster labels value zero and spare coordinates arbitrary roster values, for example all zero.
For every u_c in Z/N_c, one of the equally spaced points j/K_cl lies within 1/(2 K_cl) of -u_c/N_c. At that edge, ||(u_c + (v_{pi'_j})_c - (v_{pi_j})_c)/N_c||_T <= 1/(2 K_cl) + 1/(2 N_c) < 1/100, using K_cl = 400 and N_c > 400. Every translate therefore makes at least one edge of the dedicated forest small in this coordinate.
Bound for one batch. Fix u in G and a batch, and let S be the set of ordered pairs p != p' for which u + v_{p'} - v_p has no small coordinate in that batch. Suppose |S| > 4 K_cl^2. Forget orientations and identify the two directions of each unordered edge to obtain a simple graph on the non-isolated roster labels. The graph contains a forest with K_cl edges. To see this, take a spanning forest, grown one tree at a time until all vertices are reached. If its edge count f were less than K_cl, then, writing v for its vertex count and t for its component count with each component having at least two vertices, f = v - t and t <= v/2, so v <= 2f < 2 K_cl, whence |S| <= v(v-1) < 4 K_cl^2, a contradiction.
Choose K_cl edges of that forest, orient each one along a direction belonging to S, and order the resulting list. The batch already has a coordinate dedicated to this list. By the previous estimate, some pair on that list has a small translated difference in the dedicated coordinate, contradicting the membership in S. Every batch therefore contributes at most 4 K_cl^2 ordered pairs to the obstruction. The forest may depend on u; every possible directed list was allocated a coordinate in advance. If no such forest can be formed from the roster, the spanning-forest count alone gives the required bound, and the spare coordinates do not affect it.
Combining the estimates and forming the cyclic group. Taking the union over the a first coordinates and the b batches gives |{(p, p') in R^2 : p != p', u + v_{p'} - v_p in W}| <= a + 4 K_cl^2 b. Since log 2 > 1/2, a <= 66 log(2m) and b <= log(2m)/log 2 <= 2 log(2m), so the last bound is at most (66 + 8 * 400^2) log(2m) <= c_cl log(2m). Only the number of partitions enters this estimate; the number of coordinates inside a batch, and the eventual modulus, may depend on the entire roster.
Finally put n = product of N_c over c in C. The residue map Z/n -> G, x -> (x mod N_c), is an isomorphism of additive groups. Surjectivity is direct: n/N_c is nonzero modulo N_c, so some multiple e_c of it equals 1 modulo N_c and zero in every other coordinate; a prescribed tuple is then the image of the sum of x_c e_c. The kernel consists of integers divisible by every N_c and hence by their product, giving injectivity. Transport I_alpha, J_alpha, W, and all v_p through this isomorphism; every sum, difference, and translation statement is preserved, and every prime factor of n satisfies (i).
For m = 1 the first-coordinate construction still has a positive number of coordinates, while no Type batches are needed. The separation constraints are vacuous and the diagonal is available whenever all first totals are nonzero. Empty and singleton rosters have no ordered distinct pairs and were already included above. That completes the proof.
Interpretation at a cut. Suppose a prefix test selects a tag alpha and knows an integer i, while a suffix test independently selects a tag beta and knows an integer j. Their clock requirements are i mod n in I_alpha and j mod n in J_beta. Whenever i + j = ell stays fixed across all successful cuts under consideration, the tag clock applies to every such pair. In the diagonal case the two tags must agree. In the off-diagonal case every successful pair uses the same prefix tag alpha and the same suffix tag beta. In the episode applications below, i = k - t, j = q - k, and ell = q - t.
Tags will contain a claimed input X and output Y in a vector space, with the prefix checking x = X(alpha) and the suffix checking y = Y(beta). If the unique edge is off-diagonal, every successful transfer therefore has the same input and output and is consistent with the affine map v -> v T + Y(beta) - X(alpha) T for any specified linear part T. This explains why the exclusive alternative of the tag clock always suffices for affine updates. An empty graph simply permits no successful transfer.
For availability, if ell not in W every desired diagonal tag alpha has some decomposition ell = i + j with i in I_alpha and j in J_alpha. A family of candidate cuts whose first residues exhaust Z/n therefore contains a cut meeting both requirements for that tag, provided its other checks hold throughout the family. Consecutive n cuts have this property, as does a progression of n cuts whose step is coprime to n; multiplication by a coprime step permutes the residue classes.
Finally, suppose the integer offsets p have been assigned the residues v_p, and q, t, gamma are fixed integers. Then q - (t + gamma + p - p') in W holds if and only if (q - t - gamma) + v_{p'} - v_p in W, using the residues modulo n. The roster estimate of the tag clock bounds the number of ordered pairs satisfying this condition. For a fixed finite set of translates Gamma, the union over gamma in Gamma has at most |Gamma| c_cl log(2m) such pairs. Both q and every gamma are held fixed while the roster estimate is applied; choosing a usable offset afterwards does not alter the bound.
Local markers. The affine split requires each accepted suffix to stop at the actual first episode end. Agreement of tags alone cannot guarantee the endpoint. A local marking rule, constructed from the regularity of the word itself, supplies an intrinsic episode boundary that an independently chosen suffix can verify. The construction is a finite-window version of Krieger's separated-marker lemma; the finite merging argument is the one in Meyerovitch's recent work, specialized to a two-sided word over a finite alphabet.
A positive integer d is a period of a finite block if letters at positions d apart agree whenever both positions belong to the block. Equivalently the block extends to a two-sided d-periodic word. When the block has length at least d that extension is unique at that period.
Lemma (Local markers). For integers d >= 2 and K >= 1 there are an integer r >= K and a fixed translation-equivariant marking rule on two-sided words with three properties:
(i) distinct markers have distance at least d;
(ii) whether position x is marked depends only on the letters in [x - r, x + r);
(iii) if no marker lies in [z - d, z + d], the block [z, z + K) has a period strictly less than d.
Consequently a marker test whose inspection interval is present in a finite word is independent of the two-sided extension.
Proof. List as v_1, ..., v_N all length-K words having no period below d. Start with no markers. At stage j, mark every occurrence of v_j whose start lies at distance at least d from all markers installed at earlier stages. Two occurrences installed at the same stage cannot be at distance less than d: a word on the list has K >= d, since otherwise K itself would be a period below d, so starts at positive distance a < d <= K would overlap and give v_j period a, a contradiction. Separation is preserved at every stage.
For locality, take r_0 = K and r_j = K + j(d - 1). If earlier decisions have radius r_{j-1}, then deciding the stage-j rule at x requires its length-K block and the earlier decisions at positions x - (d - 1), ..., x + (d - 1); these are all determined in [x - r_j, x + r_j). The union with earlier markers is determined there too. So r = r_N suffices, and the construction commutes with every integer translation.
If the block at z is exactly v_j, at stage j its start is either marked or blocked by an earlier marker at distance less than d, and that marker remains installed. Absence of a marker in [z - d, z + d] therefore excludes every word on the list and proves the last assertion. Locality gives extension independence.
Lemma (Overlap of short-period blocks). Two two-sided words with periods a and b that agree on ab consecutive letter positions agree everywhere. In particular:
(i) if K - w > d^2, length-K blocks starting at a finite nonempty set of positions of diameter at most w, each having a period below d, share a common two-sided periodic extension, and the word agrees with this extension on the union of these blocks;
(ii) with the marker rule of the previous lemma and K > 3 d^2, if H >= d and [z - H, z + H] contains no marker, then all blocks starting at integer positions from z - H + d through z + H - d belong to one common two-sided periodic word of period below d, and the original word agrees with it throughout [z - H + d, z - H + d + K).
All statements apply to a finite word when the indicated blocks and marker inspection intervals are available.
Proof. The integer ab is a period of both two-sided words. For any position, translating it by a multiple of ab places it inside the interval of agreement, and both letters are preserved by the translation.
For (i), any two blocks overlap in at least K - w > d^2 letters, more than the product of their two short periods. Their periodic extensions agree. This also shows that choosing a different short period for a single block yields the same extension; fixing one block then gives a common extension for all. Their union is the interval from the least start to the greatest start plus K since w < K, and every letter there belongs to a block and has the asserted value.
For (ii), each indicated start x satisfies [x - d, x + d] contained in [z - H, z + H], so the marker lemma gives a period below d for its length-K block. Consecutive blocks overlap in K - 1 letters, at least the product of their periods; the first assertion applied successively identifies all their extensions. The common extension retains the period of the first block.
Lemma (Search crossings and right margins). Let I be an interval of integer centers of diameter D. For a set S subset of Z of marker positions and an integer L >= 0 write f_L(z) = min(S cap [z - L, z + L]), with value "bottom" when the intersection is empty. Equality of two search results means equality of their positions in the word, or that both are bottom.
(i) If points of S are at least d apart, h >= 0, and D + 2h < d, then at most 2(2h + 1) centers z in I satisfy f_L(z + e) != f_L(z) for some integer |e| <= h. This estimate is independent of L.
(ii) If h >= 1 and D < 2L + 2, at most h centers z in I satisfy S cap [z - L, z + L] = empty and S cap (z + L, z + L + h] nonempty. This estimate does not require separation.
If centers are indexed by ordered pairs (p, p') with p != p', as z = z_0 + p - p', and all their ordered nonzero differences are distinct, the same bounds count ordered pairs.
Proof. If a first-marker result changes, a marker belongs to the symmetric difference of the two search intervals. Such a marker lies within distance h of z - L or of z + L. As z ranges over I, each enlarged endpoint range has diameter D + 2h < d and hence contains at most one marker. For a fixed marker and endpoint, the condition of being within distance h permits at most 2h + 1 integer centers. Summing over the two endpoints gives (i). Only the implication from a changed result to a crossing is used; an entering marker need not change the minimum.
For (ii), assign to a center z its first marker m strictly after z + L; then z + L < m <= z + L + h. Suppose distinct serving markers m < m' are assigned to centers z, z'. Since m' is the first marker after z' + L, m <= z' + L. The marker-free interval about z' then forces m <= z' - L - 1. Combining with m >= z + L + 1 gives z' - z >= 2L + 2, contrary to the diameter hypothesis. So at most one marker serves the centers under consideration. For that fixed m, m - L - h <= z <= m - L - 1 allows at most h integer centers. Distinct ordered differences make the indexing map (p, p') -> z_0 + p - p' injective.
For local markers, the counting estimates apply to a finite word when all the shifted search inspection intervals are present: evaluate the rule on any common two-sided extension and use locality to identify the results being counted.
Episode rule. The sampling origin of an episode starting at s is t = s + L_0, for a fixed integer L_0 postponed to the parameter-choosing section. Between s and t lie five aligned subbuffers. After t lie the outer layers, one main and one periodic.
Apply the local-marker lemma to an inner marker system with parameters d_circ >= 2, K_circ > 3 d_circ^2, r_circ >= K_circ. For each label lambda in a finite set Z, let o_lambda be a nominal offset and set z_lambda(t) = t + o_lambda, u_lambda(t) = first inner marker in [z_lambda(t) - H, z_lambda(t) + H], with "bottom" for absence. The labels, offsets, trials, and full cut-offset sets H_1, H_2 are specified by the outer split. No trial roster is needed to define the end rule.
Independently apply the marker lemma to an end marker system with d_bullet >= 2, K_bullet > 3 d_bullet^2, r_bullet >= K_bullet. Its nominal position and search are z_bullet(t) = t + o_bullet and eta(t) = first end marker in [z_bullet(t) - d_bullet, z_bullet(t) + d_bullet], again "bottom" for absence. Its inspection interval is [z_bullet(t) - d_bullet - r_bullet, z_bullet(t) + d_bullet + r_bullet). When eta(t) = bottom, the marker lemma gives the seed block [z_bullet(t), z_bullet(t) + K_bullet) a period below d_bullet. The overlap lemma makes its two-sided periodic extension unique, even when several such periods are possible; call that extension pi_t.
Definition (complete episodes). Fix a positive integer B_tail. With all required bounded data present, the anchor at origin t is defined as follows:
(1) if eta(t) != bottom, the anchor is q = eta(t);
(2) if eta(t) = bottom, the anchor is the first letter position q >= z_bullet(t) + K_bullet whose letter differs from pi_t(q); if no such letter is present, no anchor has been found.
An episode beginning at s ends exactly at q + B_tail. The language E consists of the nonempty words that, with s = 0, contain the required search and seed data, have an anchor under this rule, and end exactly there. In the markerless case the tail includes the mismatch letter at q, since B_tail >= 1.
In the markerless case, "first" is part of the end test: every letter from the seed's end up to q must agree with the repetition, and the letter at q must disagree. Applying the rule at an origin that a suffix proposes uses the same convention.
Lemma (Prefix code). The language E is a prefix code. Its end decisions have the same values in an episode considered alone and in any word containing that episode at the same position.
Proof. Let e, f in E, with e a prefix of f. Their starts and sampling origins coincide. Every end-marker inspection used by e is internal to e, so the two words obtain the same value of eta(t). A present marker immediately fixes the same anchor. If it is absent, the same seed fixes the same repetition; the first mismatch seen in e is present in f and all earlier letters inspected for continuation coincide, so first mismatches coincide too. In either case |e| = q + B_tail = |f|. The same argument, together with locality of all bounded searches, proves the final claim.
Independent suffix choices have one end. Fix a stability radius with 0 <= w_E < d_bullet and K_bullet - w_E > d_bullet^2. The search eta is stable within w_E at t if eta(t + v) = eta(t) for every integer |v| <= w_E.
Lemma (Shared anchor and exact suffix consumption). Let a word begin with a complete episode e at s, with origin t, anchor q, and end b_0 = q + B_tail. Let s < k < b_0 be a cut and let [k, b) be any proposed suffix factor of the word (its endpoint b may be before or after b_0). Let T be a finite nonempty set of candidate origins with t in T and diam(T) <= w_E. Assume every candidate's end-search inspections and seed block lie inside both [s, b_0) and [k, b). Suppose the proposed suffix requires:
(r1) equality of eta(tau) for all tau in T;
(r2) the exact end rule of the definition of episodes at any one reference tau_0 in T, with anchor b - B_tail.
Then b = b_0, and the reference anchor is q. Moreover, if eta is stable within w_E at t and all the candidate data are visible in the actual suffix [k, b_0), both requirements hold for that suffix and every choice of reference.
Proof. All bounded tests in the two factors inspect the same ambient letters, so by locality they obtain the same results, including for false candidate origins. If the common value of eta is a marker position, it is also eta(t) = q, and the exact end requirement gives b = q + B_tail.
Suppose instead that every value is bottom. The seed starts x_tau = z_bullet(tau) have diameter at most w_E. By the inequality on w_E and the overlap lemma, all seeds share a common two-sided extension pi. The word agrees with pi throughout their union [x_min, x_max + K_bullet), where x_min and x_max are the extremal seed starts. Thus the true first mismatch q, which occurs after the true seed, cannot lie inside any later seed; it follows that q >= x_max + K_bullet. There is no mismatch between the end of any seed and q: before x_max + K_bullet this follows from the seed union, and afterwards from the true first-mismatch rule. Every candidate seed therefore has exactly the same first subsequent mismatch q.
Truncated or extended suffixes also fail. Put q' = b - B_tail. If q' < q the proposed mismatch letter at q' is present in both factors and contradicts the continuation just proved. If q' > q the proposed continuation reaches the visible mismatch at q and fails there. A suffix lacking a required inspection or its claimed mismatch letter cannot pass the requirements in the first place. Therefore q' = q and b = b_0.
Finally, stability and t in T imply equality of eta on T; the same seed-union argument shows that the actual suffix satisfies the exact end rule for every reference.
For an outer layer with full cut-offset set H_i, a suffix beginning at k uses T = {k - h : h in H_i}. If the prefix chooses an actual cut k = t + h_0 with h_0 in H_i, the true origin belongs to this set regardless of the suffix's independent tag. Its diameter is diam(H_i). So the end guard establishes exact consumption before any agreement of tags is used. An aligned stencil P_i similarly gives candidate origins k + L_0 - p'; at a true cut k = s + p these are t + p - p'. Their diameter is diam(P_i).
Lemma (End selection after bounded decoding). Let e, k, [k, b), t, q be as in the shared-anchor lemma, and let T be any finite candidate set containing t, with no diameter restriction. Suppose its candidates are tested by bounded predicates that do not use an anchor, all inspection intervals lie inside both the actual episode and the proposed suffix, and the true origin passes its predicate. If exactly one candidate passes, it is the true origin. Applying the exact end rule at that decoded origin, with its search and seed data also present in both factors, forces the proposed suffix to end at q + B_tail without any stability assumption.
Proof. The bounded predicates have the same values on their common letters, so the passing true candidate cannot disappear in the proposed suffix. Uniqueness therefore identifies it. Apply the shared-anchor lemma with the singleton reference set {t}; its equality condition is automatic.
The last aligned stage uses this lemma: its current witness is a bounded end-marker test independent of q, so decoding precedes the end rule. At the other stages one reference end rule is applied first. In either order, subsequent controls at translated origins keep that same q fixed and introduce no further first-mismatch scans.
Finite margin interface. The end guards require every bounded inspection to lie inside the true episode, even when the suffix proposes a wrong origin or a wrong end. Take the union of all bounded inspection intervals under every allowed cut, metadata choice, and candidate origin, adding the neighborhoods needed to decide markers and the intervals swept out in the search-crossings lemma. Let I_- <= 0 <= I_+ bound the inner-marker and trial data and all outer cuts relative to t; let E_- and E_+ bound the end-marker inspections and seed blocks relative to z_bullet(t). The continuation to the selected first mismatch is governed by the exact end rule; products ending there and residues involving q do not enlarge this inventory. Let A bound the offsets from s of the buffers before t. Then sufficient final margin inequalities are:
L_0 + I_- > A,
o_bullet + min{E_-, -d_bullet} > I_+,
B_tail > E_+ + d_bullet and B_tail >= 1.
The first inequality puts all inner data after the early buffers. The second puts every end control and every possible anchor after the inner data and the outer cuts. Since q >= z_bullet(t) - d_bullet, the third puts every end control strictly before even the earliest complete end z_bullet(t) - d_bullet + B_tail. Thus every bounded control lies strictly inside every true complete episode.
Internal visibility alone does not put data on the correct side of a cut. Each split also needs its prefix computations before its cut and its suffix computations after; any supplied left context has to be declared as finite metadata and verified by the prefix. Every test argument must contain every position it is required to inspect on its reading side. An unavailable candidate or translate causes rejection; it is never removed from a universal guard or from a uniqueness test. Requested product intervals must likewise have available, correctly ordered endpoints. This applies to a standalone suffix with false metadata and to a proposed endpoint different from the true episode end. The margins give availability for the true suffix; the rejection rule ensures that every accepted suffix sees the same bounded control values used in the shared-anchor and decoded-end lemmas.
Fixing this finite inventory independently of L_0, o_bullet, B_tail is deferred to the section on choosing parameters, which locates the three lengths in the order displayed above.