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.
https://doi.org/10.1007/3-540-45995-2_46
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.
https://doi.org/10.1307/mmj/1028998975
https://doi.org/10.1016/S0019-9958(66)90108-7
https://doi.org/10.1016/S0019-9958(65)90108-7
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 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.
Outer splits. Two outer splits convert graph languages on the full episode class E to graph languages on a residual domain D_0 on which two availability conditions fail in one of five explicit ways. The first outer split uses prediction trials whose boundaries are chosen by inner markers. The second uses a long markerless window whose periodicity supplies cuts with constant prefix product. Both constructions define total deterministic affine updates independent of split success; the split identity transports graph languages between them.
Use the earlier notation. The episode start is s, its origin t = s + L_0, its anchor q, and its end b_0 = q + B_tail. Five aligned subbuffers lie between s and t. The outer layers use cuts after t; every bounded inspection of either layer sits at a fixed offset from t. Write T_e for the interval product T[s, q + B_tail].
Main schedule. Fix the initial representation on V and put J = |V|^2. Fix a finite collection of main trials, indexed by nu, each with a prediction Theta_nu in M^{J+1}. The label set Z = {(nu, j) : 0 <= j <= J + 1} indexes endpoints and checkpoints. For lambda in Z let o_lambda be its nominal offset from t. Take an inner marker system with separation d_circle, block length K_circle > 3 d_circle^2, inspection radius r_circle >= K_circle, and search halfwidth H supplied by the parameter choices.
Set z_lambda(t) = t + o_lambda and u_lambda(t) = first inner marker in [z_lambda(t) - H, z_lambda(t) + H], with "bottom" for absence. Let A(t) mean every u_lambda(t) is present. When A(t) holds, these are the actual trial boundaries; trial nu has endpoints B_nu = u_{nu,0}(t) and C_nu = u_{nu,J+1}(t). Its block j consists of cuts k = t + c_{nu,j} + a for 0 <= a < R_1, where R_1 is the modulus determined by the parameter choices. The offsets place the whole block strictly between boundaries j-1 and j.
Second-layer cuts lie at k = z_lambda(t) + a for 0 <= a < R_2. Let H_1, H_2 be the finite sets of all cut offsets from t. Choose the end-stability radius so that diam(H_1), diam(H_2) < w_E < d_bullet and K_bullet - w_E > d_bullet^2; the parameter choices realise this.
Every suffix test at an outer cut k uses the following guard, independently of its tag. Form all origins k - h for h in H_r with r in {1, 2}. Require their values of eta to be equal, and require exact consumption of the episode end obtained from one reference origin. Let q be that reference anchor. If the prefix used an actual cut k = t + h_0 with h_0 in H_r, the shared-anchor lemma forces q to coincide with the true anchor, even if the suffix initially extends beyond the first episode or ends prematurely. Every accepted cut therefore consumes exactly one episode, and the clock integers i = k - t and j = q - k satisfy i + j = q - t.
Main affine update. Apply the tag clock to tags alpha = (nu, j, X, Y) with X, Y in V. Write n_1, I^(1)_alpha, J^(1)_alpha, W_1 for the resulting modulus, prefix set, suffix set, and bad set. Define F_{1,e}: V -> V for every episode, independently of any split, as follows:
(a) if the clock graph G_1(ell) of possible tag pairs at ell = q - t is contained in the diagonal and A(t) holds, process letters by v -> v d_e for the letter d_e, insert the ideal shift of the prediction-trial lemma at each main-trial end, and evaluate the affine action so produced on v;
(b) if G_1(ell) is diagonal and A(t) fails, set F_{1,e}(v) = v T_e;
(c) if G_1(ell) has its unique off-diagonal edge alpha -> beta, set F_{1,e}(v) = v T_e + Y(beta) - X(alpha) T_e.
These cases exhaust all possibilities, including the empty graph, which belongs to the diagonal case. Every F_{1,e} is deterministic affine with linear part T_e.
A language with metadata is the union over its own metadata choices; the prefix's union over labels is independent of the suffix's. Define P_x^(1) as the union over alpha = (nu, j, X, Y) of languages of words u such that:
(i) |u| equals one of the prescribed cuts of block j; |u| - t lies in I^(1)_alpha; and x = X;
(ii) every boundary preceding the cut is present, including the boundaries of all earlier trials and through boundary j-1 of the current trial;
(iii) processing from x to B_nu, with ideal shifts on earlier trials, arrives at the enumerated input x_j of this block;
(iv) the block's predicted transfer, together with all its preceding individual eligibility conditions, holds.
All data used lie before the cut, by placement.
Define Q_y^(1) as the union over the same alpha of languages of suffixes v such that:
(a) v satisfies the independent end guard;
(b) q - k lies in J^(1)_alpha and y = Y;
(c) for each candidate origin k - c_{nu,j} - a with 0 <= a < R_1, the future boundary searches for that role are performed, with every boundary from j onward in the current trial, and every boundary in later trials, present at the same word position across all those candidates;
(d) at those common positions, the suffix-product condition from boundary j to C_nu is verified;
(e) starting from the enumerated output y_j at C_nu, iterating through later trials with ideal shifts, arrives at y.
All required searches are after k. The candidate-origin role may be false; it remains a finite datum.
Set S_1 subset of E to consist of those episodes satisfying: eta(t) stable within w_E; ell = q - t not in W_1; A(t) holds; u_lambda(t) stable within R_1 for every lambda; and at least one main trial perfectly predicted.
Lemma (Main split). The languages P_x^(1) and Q_y^(1) satisfy the split identity with D = E, updates F_{1,e}, and skipped class S_1.
Proof. Take an accepted pair (u, v) at a genuine episode boundary, so the whole word lies in E*. The end guard gives exact consumption and d = q - t equal on the two sides. If G_1(ell) is contained in the diagonal, the two tag pairs coincide, so the prefix and suffix use the same (nu, j, X, Y). The actual t then appears among the role-origin candidates. The prefix establishes all earlier boundaries, the suffix establishes all later boundaries, and together they verify A(t). Jointly they verify, for the actual trial nu and block j, ideal eligibility of the (x_j, y_j) pair and of all surrounding intervals. The prediction-trial lemma together with the ideal computations before and after that trial give F_{1,e}(x) = y.
If the tag pair is off-diagonal, the tag clock identifies it as the unique edge alpha -> beta. The prefix's input check fixes x = X(alpha) and the suffix's output check fixes y = Y(beta), so F_{1,e}(x) = x T_e + Y(beta) - X(alpha) T_e = y. Data gathered under potentially false role origins introduces no competing input or output.
For availability, take e in S_1 and any x in V. The perfect trial nu supplies a block j such that, for the actually arriving vector at block j and its trial output, the (x_j, y_j) pair is eligible. Set X = x and Y = F_{1,e}(x). Because ell = q - t lies outside W_1, the tag clock gives a decomposition ell = i_p + j_s with i_p in I^(1)_alpha and j_s in J^(1)_alpha for alpha = (nu, j, X, Y). The R_1 consecutive cut offsets enumerate every residue modulo n_1 = R_1, so one cut realises the required residue. Every role origin differs from the true one by less than R_1, so future-boundary stability makes every suffix comparison pass. End stability makes the independent guard pass. Every required datum is present, giving the desired split.
Periodic-window update. For episodes in E minus S_1, the main family
of boundaries is missing, or the trial prediction fails. The second
layer handles these using a long marker-free window and short-period
cuts.
Apply Lemma (tag clock) to the second tag alphabet whose fields have
sizes |Z|, |V|, |V|, |M|, n_1, and |S|^(2 r_circ), where Z is the trial
label set and r_circ the inner-marker search radius. The clock gives a
second modulus n_2, sets I^(2)_alpha, J^(2)_alpha in Z/n_2, and a bad
set W_2.
The prefix P^(2)_x requires: k - t in I^(2)_alpha; x = X; the proposed
prefix product m equals T_(s,k); the proposed first-clock residue r
equals k - t modulo n_1; the proposed left context xi equals the
2 r_circ letters immediately before k; no inner marker lies in
[z_lambda(t) - H, k - r_circ].
The suffix Q^(2)_y uses the outer guard at layer 2, then requires
q - k in J^(2)_alpha and y = Y. Adjoin xi immediately before the
argument and require no inner marker in [k - r_circ, k + H + R_2].
Combine m with the suffix product T_(k, q + B_tail) to obtain a
proposed product for the whole episode. Combine r with (q - k) mod n_1
to obtain a proposed first-clock residue. Use G_1(ell) at this residue
and the tag (X, Y) to compute F_1,e(x) under that combined graph case.
Require y = F_1,e(x).
For the linear extension, on U_0 = V + F_2 define F_2,e as the
homogeneous lift of F_1,e:
F_2,e(v, c) = (v T_e + c b_e, c),
where F_1,e(v) = v T_e + b_e. The lift is linear on U_0 and recovers
F_1,e on c = 1.
Set the second availability class
S_2 = { e in E minus S_1 :
eta stable within w_E,
ell not in W_2,
for some lambda,
[z_lambda(t) - H, z_lambda(t) + H + 2 R_2] has no inner
marker }.
Lemma (periodic-window split). The pair (P^(2)_x, Q^(2)_y) satisfies
the split identity on D = E minus S_1, with updates F_2,e and skipped
class D_0 = E minus S_1 minus S_2.
Proof. Soundness. The guard gives ell = q - t. If G_1(ell) is diagonal,
the tags agree on (X, Y). The residue combination r + (q - k) mod n_1
recovers ell mod n_1, so the suffix evaluates F_1,e correctly. If
G_1(ell) is off-diagonal, the constrained (x, y) fits the affine
correction absorbed by F_2,e, and the same check y = F_1,e(x) holds.
Both cases give F_2,e(x, 1) = (y, 1) by the homogeneous lift, which is
the pair's own graph-test requirement.
Availability. Take e in S_2 with the indicated lambda. The extended
window is markerless. By Lemma (markers), a short-period K_circ-block
begins at every start from z_lambda(t) - H + d_circ through
z_lambda(t) + H - d_circ, and Lemma (periodic overlap) makes these into
one short-period run with period d < d_circ. The parameter inequality
places at least |M| whole periods, and the required 2 r_circ context,
immediately before z_lambda(t) inside the run. Walking through n_1 n_2
consecutive cuts in the run visits every pair (r, s) of first-clock and
second-clock residues. Some cut therefore carries the tag
(X, Y) = (x, F_1,e(x)). All checks pass by stability of eta and the
marker-free window. So a split exists.
Five witnesses for the remainder
An episode of D_0 witnesses failure of both outer availability
conditions. A finite number of local, bounded predicates classifies the
failure.
A_0 (t, q) = (q - t in W_1) or (A(t) holds and no trial is
perfectly predicted).
A_1 (t, q) = some u_lambda(t) changes under a shift of magnitude
at most R_1.
A_2 (t, q) = q - t in W_2.
A_3 (t, q) = some lambda has [z_lambda(t) - H, z_lambda(t) + H]
markerless, and an inner marker lies in the next
2 R_2 positions to the right of z_lambda(t) + H.
A_4 (t, q) = eta(t) changes under a shift of magnitude at most
w_E.
A_4 does not use q. Membership in a bad set always uses the
corresponding modulus.
At a formally translated origin t + delta, these predicates act on
t + delta, q with q fixed. They do not run a new first-break scan and
do not assert that t + delta starts an episode.
Lemma (residual coverage). Every episode of D_0 satisfies at least one
of A_0, A_1, A_2, A_3, A_4.
Proof. Suppose A_4 fails, so eta is stable within w_E.
Case A(t) holds. If A_0 and A_1 both fail, every condition of S_1
holds, so e lies in S_1 and not in D_0. Therefore, in this case,
either A_0 or A_1 holds.
Case A(t) fails. Some lambda_0 in Z has u_(lambda_0)(t) absent, so
[z_(lambda_0)(t) - H, z_(lambda_0)(t) + H] is markerless. If A_2 and
A_3 also fail, then q - t not in W_1 and q - t not in W_2 and, at
lambda = lambda_0, the failure of A_3 gives no inner marker in
(z_(lambda_0)(t) + H, z_(lambda_0)(t) + H + 2 R_2], so the extended
window is markerless. That puts e in S_2, contradicting membership in
D_0. Therefore in this case A_0, A_2, or A_3 holds.
Since A_4 itself is a witness when it holds, every episode of D_0 lies
in at least one of the five classes.
The five aligned stages
The two outer splits reduce the task of computing F_2 graph tests on
D_0^* to the same task on D_0^* itself, at one level of star height
higher. The five predicates A_0 through A_4 exhaust D_0. Five aligned
stages eliminate them in order, one stage per predicate, starting with
stage i = 0 and ending with stage i = 4.
Setup. Fix i in {0, 1, 2, 3, 4}. Let g_0,e = F_2,e on U_0 = V + F_2.
Each later g_i,e is affine on a larger finite vector space U_i, and the
aligned stage defines g_(i+1),e: U_(i+1) -> U_(i+1) on
U_(i+1) = U_i x V_M, where V_M is the finite vector space over F_2
with basis indexed by M, so that the linear part L_(i+1),e acts by
[v, 1_M] L_(i+1),e = [ g_i,e(v), 1_M ] for every v in U_i.
Composing this identity across an episode sequence shows that the
linear part of g_(i+1),e composed over any word w in D_(i+1)^* maps
[v, 1_M] to [g_i,w(v), 1_M]. The auxiliary register stays at 1_M in
every episode, so it resets and carries no state across splits; what
survives is exactly the value the stage must transmit. Recovering
g_i,w from g_(i+1,w) is therefore a finite Boolean query on the linear
part applied to the basis [v, 1_M].
Each stage i uses a finite stencil P_i of integer cut offsets from the
episode start s. The stencil is repeated many times inside a subbuffer
that is placed before s + L_0. The set
Delta_i = P_i minus P_i,
Gamma_i = sum_(j < i) (Delta_j + Delta_j), Gamma_0 = {0},
captures all the offsets at which A_i or its predecessors are checked.
For any finite Gamma, write A_h^Gamma (t, q) for the assertion that
A_h(t + gamma, q) holds for some gamma in Gamma.
The entry promise. Let D_i be the subclass of episodes with the promise
A_i^(Gamma_i) (t, q) or A_(i+1)^(Gamma_i) (t, q) or ... or
A_4^(Gamma_i) (t, q).
For i = 0 this is Lemma (residual coverage). Each stage preserves the
promise for the next stage.
Total suffix tables. The suffix beginning at a_i does not know the
prefix product T_(s, a_i). Each table Phi_i(m): U_i -> U_i (with
m in M) satisfies Phi_i(T_(s, a_i)) = g_i,e. Table evaluation is a
finite calculation on the episode's own letters, marker data, and M-
products; it runs no graph test on a word sequence and does not query
split success.
The proof is inductive. For i = 0, the outer rules reconstruct F_2 in a
form parametrized by the hidden prefix product m; the two clocks use
the common ell. For i < 4, suppose Phi_j exists for j <= i. Set
a = a_(i+1) and b = a_i. A hypothetical product m assigns m T_(a, u)
to the stage-i measurement at u, selecting a leaf h(m) in the stage-i
full decision tree. Let C_nu be the ends of the stage-i trials, and let
beta_nu(h(m)) be the ideal trial shift determined by that leaf's
predictions and the actual products. For every x in U_(i+1), define
Phi_(i+1)(m)(x)
= ( x rho(m T_(a,b))
+ sum_nu beta_nu(h(m)) rho(T_(C_nu, b)) ) H_i,
where rho is the reset action taking the auxiliary register back to
1_M, and H_i is the terminal map. Each trial shift is transported once
to b; the terminal map is applied linearly. The result is affine in x.
Setting m = T_(s, a_(i+1)) gives Phi_(i+1)(T_(s, a_(i+1))) = g_(i+1),e,
and its linear part on the auxiliary M-coordinate equals
[v, 1_M] L_(i+1),e = [g_i,e(v), 1_M] because the reset per episode
posts g_i,e (v) in the M-coordinate. That closes the induction.
Full sets, primary and secondary. Within D_i define
F_i = { e in D_i : the true history has a perfect aligned trial,
and no later witness: neg A_h^(Gamma_i
+ Delta_i) (t, q) for every h > i }.
Put D_i' = D_i minus F_i. Within D_i' define
O_i = { e in D_i' : neg A_h^(Gamma_i
+ Delta_i + Delta_i) (t, q) for every h > i }.
Put D_(i+1) = D_i' minus O_i. Every episode left in D_(i+1) fails the
later-witness bounds of both sets, so it has a later witness expanded
by Gamma_(i+1) = Gamma_i + Delta_i + Delta_i. That proves the next
entry promise. At i = 4 the secondary set O_4 is empty and D_5 is
empty.
Both splits at stage i transmit the same g_(i+1),e. The full sets and
the residual restrictions reclassify episodes; they do not redefine the
update.
Exact decoder. At a cut k = s + p with p in P_i, the suffix examines
the candidate origins
tau_(p') = k + L_0 - p', p' in P_i.
For i < 4 it does the q-free last-type checks first, requires eta equal
across all candidates, applies the exact end rule at one reference
candidate (fixing q), and only then does the remaining later-type
checks. For i = 4 there is no later guard; the suffix uses the
q-free uniqueness test for A_4^(Gamma_4) directly, decodes the origin,
and only after decoding applies the exact end rule. Both uniqueness
tests range over all of P_i. Every bounded control is mandatory: a
suffix missing any required inspection rejects.
The prefix family P_x^(i+1) carries a measurement copy: it validates
the node's length and verifies its ancestor measurements, together
with the payload x. The suffix family Q_y^(i+1) applies the
strengthened time decoder to obtain the node, its ancestor-path
metadata, and the payload. At the node's measurement position u it
tries every d in M, follows branches using d T_(u, u'), and retains
exactly those values whose resulting history has no perfectly
predicted trial. It requires a unique retained value.
Bad histories. Fix one episode and its actual tuple of natural products on all aligned trial intervals. Fewer than R leaf histories have no perfectly predicted trial, including infeasible histories. Along the true path, fewer than R nodes have a wrong proposed measurement value whose suffix continuation yields such a history.
Proof. Let B be the set of all leaf histories whose prediction differs from the actual tuple on every trial. If R distinct leaves lay in B, their allocated common trial would assign all R possible tuples across them. One assignment equals that trial's actual tuple, contradiction. So |B| < R.
At a true-path node with measurement u, a wrong proposed value d chooses a different branch. Continue at any later measurement u' using d T_(u, u'). This selects a well-defined leaf in the off-path subtree, whether or not the whole history is feasible. Departures at two different nodes of the true path lie in disjoint subtrees, so their leaves differ. Selecting one wrong surviving value at each ambiguous node injects those nodes into B, proving the bound.
Aligned stage lemma. Assume the entry promise, the total-table property, the placement conditions, and the ambiguity bound with more than C_i copies per kind. Exact graph tests for g_(i+1) on D_(i+1)^* yield graph tests for g_i on D_i^* by two uses of the split identity and finite Boolean operations. At the next stage every hypothesis still holds, and D_5 is empty.
Proof. The secondary split first gives graph tests for g_(i+1) on (D_i')^*. It uses the entry promise for D_i' and the exact time decoder to recover each episode's update. The primary split uses these as skips and gives its graph tests on D_i^*. Both splits transmit the same deterministic affine update g_(i+1).
By the affine-recovery lemma these tests determine the product of the episodewise linear parts of g_(i+1). By construction L_(i+1,e) sends [v, 1_M] to [g_i,e(v), 1_M], so the composed product on a word w in D_i^* sends [v, 1_M] to [g_i,w(v), 1_M]. Querying basis vectors e_v tensor e_(1_M) therefore recovers g_i,w as a finite Boolean combination. This gives graph tests for g_i on D_i^*.
The domain restrictions D_(i+1) were recorded above and D_5 is empty. Starting with identity graph tests on the empty D_5 domain (height 0), the five stages produce graph tests for g_0 = F_2 on D_0^*.
Consistency of the two splits. Both the primary and secondary split at stage i test the same g_(i+1,e), fixed by the total-table construction from the suffix data at a_i. That construction uses no split-success oracle; it uses only letters, marker data, and M-products on the reading side. Every successful pair at a genuine boundary therefore has x = X and y = g_(i+1,e)(x), regardless of the variant used. Lemma (split identity) applied twice therefore assembles F_2 graph tests on D_i^*.
Parameters
All finite choices are made in a consistent order, so that no choice depends on a later one.
Separated differences. Suppose x_1 < ... < x_a are integers with all positive differences separated by more than S, each larger than S. Put D = x_a - x_1. Choose x_(a+1) in its prescribed residue class so that x_(a+1) - x_a > D + S. Every new positive difference exceeds D + S; the difference of two new positive differences is an old positive gap, larger than S. Separation and distinctness are preserved. Representatives in any residue class may be chosen arbitrarily large, so any nonempty residue prescription is met. This constructs a stencil with preset residues and separated differences. Interposed bounded events fit in the reserved gaps by enlarging them by a finite amount.
Stage 0. Put J = |V|^2 and K = m^(J+1). Choose mu_0 to exceed both 2A and 4 B^2 where A = K + c_cl log(2 J^2 (1 + K kappa_0^(2K))) and B = 2 c_cl K. Let roster P_0 have N_0 = mu_0 kappa_0 slots. For every ordered list of K distinct ordered pairs of slots, reserve a group of K main trials and one spare. The total trial count is T_1 = 1 + K (Q)_K, where Q = N_0 (N_0 - 1). The first tag alphabet has size m_1 = J^2 T_1 and the trial/checkpoint set Z has size (J + 2) T_1. Apply Lemma (tag clock) with threshold 1; obtain n_1, W_1, and roster residues. Set R_1 = n_1. Place the stage-0 stencil with separated differences longer than T.
Stage 1. Choose mu_1 = floor(C_1) + 1. Construct the stage-1 stencil and record h_1. Choose d_circ > 10(2 h_1 + 2 R_1 + 5) and K_circ > 3 d_circ^2. Lemma (markers) gives the inner-marker rule and the search radius r_circ >= K_circ.
Stage 2. Set m_2 = |Z| |V|^2 m n_1 |S|^(2 r_circ). Choose mu_2 = floor(C_2) + 1. Apply Lemma (tag clock) with threshold max{n_1, N_M, d_circ}, N_M = m!. Receive n_2, W_2, and roster residues. Construct the stage-2 stencil and record h_2. Set R_2 = n_2 n_1 N_M d_circ.
Stage 3. Choose mu_3 = floor(C_3) + 1. Construct the stage-3 stencil and record h_3. Choose H > r_circ and a common main-trial template length T exceeding all scheduled inspections. Place the main trials: templates are ordered and separated by more than 2 h_0 + 2 T + h_0.
Stage 4. Choose w_E > 1 + max{diam H_1, diam H_2, 2(h_0 + h_1 + h_2 + h_3)}. Choose mu_4 = floor(C_4) + 1, construct the stage-4 stencil, record h_4. Choose d_bullet > 10(2 h_4 + 2 w_E + 5) and K_bullet > 3 d_bullet^2. Lemma (markers) gives the end-marker rule and radius r_bullet >= K_bullet.
Final placement. Translate the five aligned arrangements into disjoint intervals after s, in reverse order 4, 3, 2, 1, 0, ending at a_4 < a_3 < a_2 < a_1 < a_0. Let A_buf be a bound on their offsets from s. Choose L_0 > A_buf + B_circ + 2 for B_circ a finite envelope bound. Then choose o_bullet and B_tail to satisfy the margins:
L_0 + I_- > A_buf,
o_bullet + min{E_-, -d_bullet} > I_+,
B_tail > E_+ + d_bullet, B_tail >= 1.
Existence. Each C_i depends only on strictly earlier choices. Every margin inequality is satisfied by choosing L_0, o_bullet, B_tail large enough after all earlier parameters. Hence a consistent finite parameter set exists, with h_i < w_E for i < 4 and more than C_i copies per stencil kind.
Compilation and the uniform bound. Three steps assemble the pieces into a height-13 expression for every regular language.
Reduction to E. From the aligned stages, graph tests on D_0^* for F_2 have height at most 11. The periodic-window split, whose domain D_1 = E minus S_1, raises them to graph tests on D_1^* for F_2, at height at most 12. The main split raises them to graph tests on E^* for F_1, at height at most 13. By the affine recovery lemma applied to the linear part of F_1, exact graph tests for F_1 on E^* determine graph tests for the composed interval products T_e on E^*.
Episodes and the tail. Every word of Sigma^* factors uniquely as uv with u in E^* and v in F = complement of (E · top), where top = Sigma^*. The E-part is the concatenation of the maximal initial sequence of whole episodes; the F-part is the trailing remainder, either empty or lacking any nonempty E-prefix. Because E is a prefix code, the factorization is unique.
Lemma (templates). Call a word a template if it has the shape a b^j c with b nonempty and j a nonnegative integer, and a periodic-template family any set of such templates. On any periodic-template family, every finite-data quantity that the construction evaluates is eventually periodic in the exponent j: interval products have the form A T_b^(j-j_0) C for fixed A, C in M, length residues are periodic in j, and any finite function of ultimately periodic data is ultimately periodic.
Proof. Prefixes and suffixes of a b^j c stabilise letterwise past a finite threshold. An interval touching the boundary between a and the j-indexed middle multiplies by T_b each time j increases by one; powers of a fixed element of a finite monoid are ultimately periodic, and length residues are periodic with modulus n. A common threshold and common multiple of the periods put every queried finite-data quantity on one ultimately periodic grid. Finite branching inside the table recursions composes finitely many such functions.
Lemma (component languages). Every component language that occurs in the outer and aligned splits -- a fixed inspection window at a bounded offset from t or t + delta, an equality between two M-products on a bounded interval, a membership test on a fixed clock residue, an exact end rule with bounded lag -- reduces to a finite Boolean combination of periodic-template family languages once the input is restricted to a template. Each such decision therefore has height at most one; the same holds for every metadata choice, which is a finite union on the same alphabet.
Reduction of E^* to bounded instances. For a fixed graph-state pair (x, y), the graph test on E^* now reduces to a union over bounded-length initial episodes of a finite language times a periodic continuation, plus one long-scan case. Both the finite language and the periodic continuation have height at most one. The residual F-language reduces by the final-suffix lemma.
Lemma (Final suffix). For every m in M, the language {f in F : T_f = m} has height at most one. Every word of Sigma^* lies in E^* F.
Proof. The set F = complement of (E · top). Since E is a prefix code and its members end at q + B_tail, a word of F avoids any complete episode as a prefix. Its seed fix, when present, forces a unique continuation by the marker rule. When no marker is visible, the same periodic run extends; when a marker is visible, the first mismatch sits at a fixed distance from the marker. Either way the monoid value of every sufficiently long initial segment is determined by a fixed finite template and a bounded word. By the templates lemma, F_m has height at most one. Completeness of the factorization E^* F is definitional.
Assembly. Let A subset M be the set of monoid elements that send the initial state of the DFA to an accepting state. For each mn in A the language L_m F_n consists of words whose DFA run is accepted along the pairing (m at the E^* prefix, n at the F-suffix). The DFA language equals the union over mn in A of L_m F_n. Concatenation and finite union do not increase the height beyond the maximum, so the DFA language has generalized height at most 13.
Height accounting. Starting at height 0 on the empty D_5 domain, stage 4's two splits travel 0 -> 2 -> 3, stage 3 travels 3 -> 4 -> 5, stage 2 travels 5 -> 6 -> 7, stage 1 travels 7 -> 8 -> 9, stage 0 travels 9 -> 10 -> 11. The periodic-window split then travels 11 -> 12, and the main split travels 12 -> 13. Concatenation with the height-1 suffix F_n preserves 13. Each split's contribution is bounded by max(2, H+1), so no stage adds more than one to the running bound once it exceeds 1.
Historical context. The star-height problem originates with Eggan's 1963 Michigan Mathematical Journal paper; Dejean and Schutzenberger's Information and Control note supplied the binary unbounded example. The star-free case was characterized by Schutzenberger in 1965 via aperiodic monoids. Height one is known for languages recognized by finite abelian groups (Henneman, recorded as Theorem 3.4 in Pin, Straubing, Therien, Information and Computation 1992) and, more generally, by finite nilpotent groups of class two (PST 1992, Theorem 7.3). Bourne and Ruskuc extended height one to languages recognized by finite Rees zero-matrix semigroups over abelian groups in their 2016 Theoretical Computer Science paper. Place and Zeitoun's 2017 CSR lecture framed the concatenation-hierarchy context and distinguished the ordinary from the generalized problem; Cotumaccio's 2025 Bulletin of the European Association for Theoretical Computer Science column records uniform boundedness as an open problem linking automata theory and data compression. Rabin and Scott's 1959 IBM Journal paper established the finite-automaton equivalence for regular languages that underlies the reduction to a monoid. Krieger's 1982 Ergodic Theory and Dynamical Systems paper contains the separated-marker lemma underlying the finite-window form, and Meyerovitch's 2025 paper gives a clopen-marker embedding form of it with a finite merging argument.
./pst-1992.pdf
./bourne-ruskuc-2016.pdf
https://doi.org/10.1007/978-3-319-60134-2_3
./cotumaccio-2025.pdf
https://doi.org/10.1147/rd.32.0114
https://doi.org/10.1017/S0143385700001516
./meyerovitch-2025.pdf
None of these papers contains a uniform bound. The constant 13 constructed above is not optimized: it reflects the number of split applications in the prediction/history chain, not the actual minimum. Whether every regular language has generalized height at most one, two, or some other fixed integer remains open at the time of writing.