diff 6590661..2167f8f generalized_star_height_four_v2.txt
diff --git a/generalized_star_height_four_v2.txt b/generalized_star_height_four_v2.txt
index e69de29..81e4cb5 100644
--- a/generalized_star_height_four_v2.txt
+++ b/generalized_star_height_four_v2.txt
@@ -0,0 +1,1472 @@
+GENERALIZED STAR HEIGHT AT MOST FOUR
+
+A COMPLETE WALKTHROUGH
+
+
+HOW TO READ THIS DOCUMENT
+
+This is a plain-language but mathematically complete account of the
+paper "Generalized star height at most four." The technical original
+is a journal-length research paper. This walkthrough states every
+main theorem exactly, defines every term, and explains every major
+step at a level suitable for a motivated high-school student who
+knows sets, functions, and basic algebra. If you follow the whole
+thing you will know precisely what the paper proves and why each
+piece of the proof is needed.
+
+If you want only the headline, read Part 1 (the question) and Part
+11 (the answer). If you want the full construction, work through
+Parts 2 through 10 in order. Parts 3-10 are the technical
+construction; if you get lost there, you can read Part 11 and Part
+12 to see what was proved and what is still open. A short glossary
+is at the end.
+
+
+PART 1. THE QUESTION
+
+
+1.1 Regular languages and star height
+
+Fix a finite alphabet Sigma, a finite set of "letters" (for example
+Sigma = {a,b}, or Sigma = {a,b,c}, or any other finite set). A word
+is a finite sequence of letters, like "abba" or "aabcb" or the
+empty word epsilon of length zero. A language is any set of words.
+The set of all words of every length, including epsilon, is
+Sigma*.
+
+A regular expression is a formula that describes a language. Its
+basic constructs are
+
+ 0 the empty language
+ 1 the language {epsilon}
+ a the language {a}, for each letter a
+ P + Q the union of P and Q
+ P Q the concatenation: all pq with p in P, q in Q
+ ~P the complement of P in Sigma*
+ P* the Kleene star of P: all finite concatenations of
+ words of P, including the empty concatenation
+
+Every regular language can be described by some regular expression:
+this is Kleene's theorem from 1951.
+
+The star height of an expression is the deepest nesting of stars
+inside it:
+
+ ht(0) = ht(1) = ht(a) = 0
+ ht(P+Q) = ht(PQ) = max(ht(P), ht(Q))
+ ht(~P) = ht(P)
+ ht(P*) = 1 + ht(P)
+
+The generalized star height of a regular language L is
+
+ h(L) = min over expressions E with L(E) = L of ht(E).
+
+It measures how deeply the star operator must be nested if we try
+to describe L exactly, with no limit on how many times we use the
+other operations.
+
+
+1.2 The ordinary (non-complemented) problem is unbounded
+
+If you take regular expressions and forbid the complement, you
+get the "ordinary" star height problem. In 1963 Eggan introduced
+this notion and observed that different regular languages need
+different depths. In 1966 Dejean and Schutzenberger proved that
+ordinary star height is unbounded: over the binary alphabet there
+are regular languages of ordinary star height 1, 2, 3, and so on
+without bound.
+
+Adding complement changes everything. A famous theorem of
+Schutzenberger (1965) classifies the star-free languages, meaning
+the languages of ordinary star height 0: they are exactly the
+languages whose syntactic monoid is aperiodic (contains no
+nontrivial group). The same criterion controls generalized star
+height 0, because adding complement does not remove the need for
+stars: a language has generalized height 0 if and only if it is
+recognized by an aperiodic finite monoid.
+
+
+1.3 The open question of height one
+
+What about height one? Several beautiful theorems are known.
+
+ Henneman (as recalled in Pin-Straubing-Therien 1992, Theorem
+ 3.4): every language recognized by a finite commutative group
+ has generalized height at most one.
+
+ Pin-Straubing-Therien (1992, Theorem 7.3): the same conclusion
+ holds for every finite nilpotent group of class two.
+
+These results are algebraic. They fall far short of a general
+theorem. The fact is that nobody knows whether every regular
+language has generalized star height at most one. That is a
+different, still-open question. The question addressed here is the
+weaker question: is there any fixed absolute bound?
+
+
+1.4 The main theorem
+
+This paper proves:
+
+ Theorem. For every finite alphabet Sigma and every regular
+ language L contained in Sigma*, one has
+
+ h(L) <= 4.
+
+The bound 4 is absolute. It does not depend on Sigma, on L, or on
+the number of states of any automaton recognizing L. It does not
+assert that 4 is necessary: some languages may have smaller height,
+possibly height 1. What the theorem says is that 4 is always
+enough.
+
+The number 4 comes from a chain of three star-producing splits
+plus one star-free compilation step. This paper also has two
+companion papers:
+
+ Uniform13 (companion, "Finite monoid computations and a uniform
+ generalized star-height bound"): proves height 13.
+
+ Height3 (companion, "Generalized star height at most three"):
+ proves height 3.
+
+Each paper proves its own required algebra, timing statements,
+and original-alphabet compilation. The bound 3 is the strongest
+known; the present paper's split and multiscale method is
+independent of that and does not rely on the companion theorem.
+
+
+PART 2. TOUR OF THE PROOF
+
+
+2.1 The reduction to a finite monoid
+
+The expression we want to construct is over the original alphabet
+Sigma. But every regular language is recognized by a finite
+deterministic automaton, and every such automaton yields a finite
+monoid M together with a morphism
+
+ T : Sigma* -> M
+
+that assigns to each word the "type" of its action on the
+automaton's states. If q_0 is the start state and F the set of
+accepting states, then L is a finite union of fibers T^{-1}(m),
+one for each m in M with q_0 . m in F.
+
+So it suffices to build a generalized expression of height at most
+4 for T^{-1}(m) for each m in M, and then take the finite union.
+The construction below does exactly this.
+
+The finite monoid M has an "affine lift" trick that turns the
+question into a statement about linear maps on a finite-dimensional
+vector space V over F_2. Instead of tracking just the monoid value
+of the whole word, we track a linear map on V whose "basis
+survivor" encodes the monoid value. This makes the math linear and
+allows the affine-line lemma (Part 5) to apply.
+
+
+2.2 Three essential tricks
+
+The proof uses three genuinely different tricks.
+
+ Trick 1. Split a sequence into a prefix and a suffix.
+ Given a word that is a sequence of small "episodes," we can cut
+ it at a specific place. The prefix announces its own state, the
+ suffix announces its output, and the two sides agree on enough
+ finite data to determine the total. This builds a graph test on
+ a larger class of episodes from a graph test on a smaller
+ class. Each split application introduces one new star.
+
+ Trick 2. Hide one interval product by an affine correction.
+ Suppose a word splits into l equal-length intervals, and neither
+ side can read the product across the cut. We precompute a
+ correction function beta that, for every possible tuple of
+ interval products, hides one of them: for every tuple some
+ coordinate is "evadable." The prefix goes up to the cut and
+ announces everything weak; the suffix reads the rest and checks
+ "constancy along a line." The existence of beta is
+ probabilistic: the Erdos-Lovasz local lemma guarantees that a
+ random beta works.
+
+ Trick 3. A finite clock and multiple scales.
+ When a prefix chooses one of finitely many "tags" and a suffix
+ chooses another, we need to decide whether they are compatible
+ using only finitely many residue tests. The clock provides such
+ tests. The scales let us "slide" a boundary through a periodic
+ region without changing any interval product, so we can always
+ find a cut position that avoids finitely many bad shifts.
+
+2.3 The height ladder
+
+The central construction is a sequence of five steps that raise
+the height from 0 up to 4:
+
+ height 0 -> height 2 stage 1 aligned split
+ height 2 -> height 2 recover g_1 from g_2 (Boolean)
+ height 2 -> height 3 stage 0 aligned split
+ height 3 -> height 3 recover g_0 from g_1 (Boolean)
+ height 3 -> height 4 main split
+
+Each split adds exactly one. Each recovery is Boolean and adds
+nothing. The Boolean recoveries are what let us interleave lifts
+of the update without paying extra height for them.
+
+2.4 What is not claimed
+
+The proof gives no runtime bound. The finite choices of
+parameters are made by exhaustive search, but the sizes of the
+objects obtained are not controlled. The expressions produced
+are finite objects with bounded height; their lengths and the
+running times to find them are arbitrary.
+
+The proof does not exhibit any specific regular language that
+needs height more than 1. It is completely compatible with the
+conjecture that height 1 always suffices.
+
+
+PART 3. ALGEBRA: EPISODES, INTERVALS, AND GRAPH LANGUAGES
+
+
+3.1 Episode prefix codes
+
+Let E be a set of nonempty words over Sigma such that no member of
+E is a proper prefix of another member of E. Such a set is called
+a prefix code, and its elements are called episodes.
+
+The defining property of a prefix code is: every word in E* (every
+concatenation of episodes) has a unique factorization into
+episodes. Proof: compare the first factors of two factorizations of
+the same word. Both are prefixes of the word, so one is a prefix
+of the other; the prefix-code property forces them to be equal.
+Cancel and continue by induction.
+
+We build E from "small complete words" that a deterministic
+end-marker rule selects: an episode starts at s and ends exactly at
+its anchor position plus a fixed tail. Because the endpoint is
+uniquely determined by the word's own letters up to and including
+that point, prefix relations are impossible (an episode would have
+to be a proper prefix of another episode, contradicting the
+deterministic rule). Section 8 proves this elementary fact.
+
+
+3.2 Interval products
+
+Fix a finite monoid M and a morphism T : Sigma* -> M (Section
+2.1). For a word w_1 w_2 ... w_k, let T(w) in M be the product of
+letters in reading order. Write T_{a,b} for the product of letters
+at positions a, a+1, ..., b-1, the "interval product" from cut a to
+cut b. Because T is a morphism, T_{a,c} = T_{a,b} * T_{b,c} for
+a <= b <= c. Each letter occupies a unit interval [i, i+1), and the
+endpoint i is the cut before the i-th letter.
+
+
+3.3 A vector space that distinguishes monoid elements
+
+Let V = F_2^M be the vector space with basis indexed by M. Right
+multiplication in M gives a linear right action of M on V:
+
+ e_c . d = e_{cd}, extended to V by F_2-linearity.
+
+The key property: e_{1_M} . d = e_d tells us which monoid value
+produced it, so a linear map on V that survives to e_m identifies
+m. In the construction we will track affine maps on V whose linear
+part is x -> x T(w) for the total monoid value of the word. Then
+e_{1_M} is transported to e_{T(w)}; reading the surviving basis
+index gives T(w). Fibers T^{-1}(m) are then distinguished by the
+surviving basis index.
+
+
+3.4 Graph languages
+
+Suppose each episode e carries a deterministic update G_e of a
+fixed finite state set S. For x, y in S, the graph language from x
+to y on D* (where D is a subset of E) is
+
+ W_{x,y}(D) = { w in D* : the composite update of w sends x to y }.
+
+The domain condition is part of the language: it accepts no word
+outside D*. The empty word carries the identity update and lies in
+W_{x,x}.
+
+
+3.5 Buffers and kinds (preview)
+
+Each episode will have two "buffer" regions preceding its main
+cut, physically laid out in the order 1 then 0 along the word
+(this reversed order is explained in Section 8.7). Buffer i has
+checkpoints B_{i,0} < ... < B_{i,l_i} < a_i, giving l_i "interval
+products" d_{i,1},...,d_{i,l_i} with d_{i,f} = T_{B_{i,f-1},
+B_{i,f}}. The "kind" of a buffer hypothesis is the tuple
+
+ (j, v, d_1, ..., d_{j-1}) with 1 <= j <= l_i, v in U_{i+1},
+ d_f in M.
+
+It records the hidden interval index, the input vector at the start
+of the buffer, and the preceding interval products.
+
+
+PART 4. THE SPLIT LEMMA
+
+
+4.1 The split identity
+
+The split lemma converts a graph test on D'* (a smaller class) into
+one on D* (a larger class), via two auxiliary languages P_x and Q_y.
+
+ Lemma. Let D' be a subset of D, where D is a subset of the
+ prefix code E. Let (G_e) be deterministic updates of a finite
+ state set S. Suppose languages P_x, Q_y (x, y in S) satisfy:
+
+ (i) If a word in D* has a prefix u v with u in P_x and
+ v in Q_y, then its first episode e exists, u v = e, and
+ G_e(x) = y.
+
+ (ii) For every e in D \ D' and every x in S, the episode e
+ lies in P_x Q_{G_e(x)}.
+
+ Then the graph language from x to y on D* equals
+
+ D* intersect ( W_{x,y}
+ + (union_a W_{x,a} P_a)
+ ( union_{b,c} Q_b W_{b,c} P_c )*
+ ( union_f Q_f W_{f,y} ) ),
+
+ where W_{x,y} is the graph language from x to y on D'*.
+
+ If D, all P_x, and all Q_y have height at most one, and every
+ W_{x,y} has height at most b, then the graph language from x
+ to y on D* has height at most max(2, b+1).
+
+
+4.2 Idea in words
+
+Episodes in D' are "easy": the W-languages handle them directly,
+without any splitting. Episodes in D \ D' are "hard": each is in
+P_x Q_{G_e(x)} for the true current state x (condition ii), so we
+split it into a prefix announcing "we are in x" and a suffix
+announcing "we came out at y". Between splits the word runs through
+D'-episodes, which W absorbs. The central star lets us repeat the
+alternation as many times as needed.
+
+Condition (i) is the soundness condition: it prevents P and Q from
+cheating by producing a fake episode. Condition (ii) is the
+completeness condition: every D \ D'-episode can be split honestly
+at least one way.
+
+
+4.3 Soundness in detail
+
+Suppose a word is accepted by the right side of the split identity.
+It is in D* by the outer intersection, so it really is a
+concatenation of D-episodes. The W-factors, by the prefix-code
+property, respect that factorization: each W-factor consumes whole
+episodes. The explicit P Q pairs, by condition (i), consume the
+next episode and send the current state to the announced target.
+Alternating through the central star's rounds, we induct on the
+rounds and conclude that the composite update sends x to y.
+
+The first term W_{x,y} is handled by induction on D'*: those
+episodes never needed splitting.
+
+
+4.4 Completeness in detail
+
+Take any word in D* with update from x to y. Split each D \ D'-
+episode using condition (ii): the current state is the true one,
+and the episode lands at its honest G_e. Chop the word at every
+D \ D'-episode; each D'-run is handled by its W; each explicit
+split is a P Q pair. This gives a factorization accepted by the
+right side. If there are no D \ D'-episodes, W_{x,y} captures the
+whole word.
+
+
+4.5 Height
+
+The outer D* has height at most 2, because D is contained in the
+prefix code E: a word is in D* if it is a concatenation of
+episodes AND every episode is in D; both are height-1 languages,
+and their intersection has height 2.
+
+The central star has operand of height max(1, b), so it contributes
+height max(2, b+1). All other operations (finite unions,
+concatenations, intersections) don't raise the height. This is the
+one place in the whole construction where height increases.
+
+
+PART 5. AFFINE CORRECTION AND THE AFFINE-LINE LEMMA
+
+
+5.1 Why affine correction is needed
+
+At an interior cut, neither side can read the interval product d_j
+that straddles the cut. We precompute a correction beta such that
+even without d_j the total output can be recovered. The trick is
+to work with affine updates
+
+ G_e(v) = v L_e + sigma_e (v in U, L_e linear, sigma_e in U)
+
+on a finite-dimensional F_2-vector space U with a linear right
+action of M. Affine updates compose to affine updates: v |-> v L +
+c, where L = L_1 L_2 ... L_k (product in reading order) and c is a
+constant. If c is readable by the suffix, and v L is what we want,
+we can use a Boolean "recovery" step at the end to extract the
+linear part.
+
+
+5.2 Affine recovery lemma
+
+ Lemma. Let U be a finite-dimensional F_2-vector space, D a
+ subset of the prefix code E, and the update for e in D affine:
+
+ G_e(v) = v L_e + sigma_e.
+
+ If R_{v,y} are graph languages for the affine composite on D*
+ (from v to y), then the graph language of the product of the
+ linear parts (from v to y) is
+
+ union over f in U of ( R_{v, y+f} intersect R_{0, f} ).
+
+ This recovery uses only finite Boolean operations.
+
+ Proof. On any word of D*, the affine composite has form v |-> v
+ L + c. Its output at v is v L + c; at 0 it is c. The difference
+ is v L. The displayed intersection says "the first output is
+ y + f and the second is f," which is exactly "v L = y." QED.
+
+
+5.3 Affine-line lemma
+
+ Lemma. Let U be a finite-dimensional F_2-vector space with a
+ linear right action rho of M. There exist an integer l >= 1 and
+ a function beta : M^l -> U such that for every v in U and every
+ tuple d = (d_1, ..., d_l) in M^l, some index j in {1,...,l}
+ makes the function
+
+ a |-> v . rho(d_1 ... d_{j-1} a d_{j+1} ... d_l)
+ + beta(d_1,...,d_{j-1},a,d_{j+1},...,d_l)
+
+ constant on M.
+
+
+5.4 Intuition
+
+Think of d as a center point in the l-dimensional grid M^l. Through
+it run l coordinate lines (one per coordinate direction). On each
+line, only one coordinate varies; the other l-1 are fixed.
+
+For a given v and d, we want SOME coordinate line to make the
+function of a_j constant. If beta is chosen uniformly at random in
+U^(M^l), then the chance that a specified line is constant is
+q_U^{1-m}, because beta must take one specified value at each of
+the m-1 off-center points on that line (each with probability 1/q_U).
+Different lines through the same center touch disjoint sets of
+off-center points, so their constancy events are independent.
+
+So the probability that a specific (v, d) is BAD (no line constant)
+is p_l = (1 - q_U^{1-m})^l, which decays exponentially in l. For
+large l, most centers are good.
+
+The uniformity is essential: a single beta must work for all v and
+all d simultaneously. So we need to rule out ALL bad centers.
+
+
+5.5 Erdos-Lovasz local lemma
+
+The naive union bound fails: q_U * m^l pairs, each failing with
+probability p_l, gives q_U * m^l * p_l, which is huge.
+
+The Erdos-Lovasz local lemma does better. If the failure events
+have bounded maximum dependency degree Delta (each is independent
+of all but at most Delta others) and each has probability at most
+u (1-u)^Delta for some u in (0,1), then all events can be avoided
+simultaneously. Here, the dependency degree is bounded by
+
+ Delta_l = q_U (1 + l m + l^2 m^2),
+
+the number of centers within Hamming distance 2 of a given one.
+Choose u = 1/(2 Delta_l); Bernoulli's inequality gives
+u (1-u)^Delta_l >= 1/(4 Delta_l). Since p_l decays exponentially,
+choose l large enough that p_l <= 1/(4 Delta_l). The local lemma
+then gives a choice of beta with no bad centers. Fix such a beta.
+
+
+5.6 Uniformity
+
+The choices of l and beta depend only on U, M, rho. They are fixed
+before any v or d is given. The successful coordinate j is allowed
+to depend on v and d. So the whole procedure is uniform in the cut
+and in the input.
+
+The proof is effective in principle: enumerate l = 1, 2, ...; for
+each, check p_l <= 1/(4 Delta_l); the first l that works stops the
+search. Enumerate the finitely many candidate beta and test. At
+least one passes. This gives a finite existence proof, but no
+useful running-time bound.
+
+
+5.7 Applying the lemma to a word segment
+
+To apply the affine-line lemma to a word segment, choose l ordered
+checkpoints B_0 < ... < B_l and set d_j = T_{B_{j-1}, B_j}.
+Process the segment by rho, then add beta(d) at B_l. If a cut lies
+in interval j, the prefix can transmit the vector v at B_0 and the
+preceding products d_1, ..., d_{j-1}. The suffix supplies
+d_{j+1}, ..., d_l and checks constancy on the missing-coordinate
+line. When that check holds, it obtains the correct vector at B_l
+without knowing d_j. For every actual tuple and input at least one
+interval permits this procedure. Because the added vector depends
+only on the actual tuple, the composite of the whole segment is
+still affine and remains eligible for the recovery lemma.
+
+
+PART 6. THE FINITE TAG CLOCK
+
+
+6.1 The problem the clock solves
+
+At a main split, the prefix chooses a finite "tag" alpha and the
+suffix independently chooses a finite "tag" lambda. We need a
+finite test that says "alpha and lambda are compatible at this cut."
+The clock converts this into a residue test "s in I_alpha +
+J_lambda" modulo a modulus n. It also supplies a "bad set" of
+residues W and gives each roster item p a residue v_p, so that at
+most boundedly many translate-rosters produce collisions in W.
+Everything is finite and enumerable.
+
+
+6.2 Clock lemma
+
+ Lemma. For every finite monoid M, there exist a modulus n, a
+ prime q dividing n, a finite tag set Lambda with maps X, Y :
+ Lambda -> M, and finite sets I_alpha, J_lambda in Z/nZ (alpha,
+ lambda in Lambda) satisfying:
+
+ (i) For every s in Z/nZ, the relation
+
+ E(s) = {(alpha, lambda) in Lambda^2 : s in I_alpha +
+ J_lambda}
+
+ either is contained in the diagonal { (a,a) : a in Lambda }
+ or is a singleton consisting of an off-diagonal pair.
+
+ (ii) There is a set W in Z/nZ such that, for every ordered
+ list ((p_a, p'_a))_{a=0}^{F-1} of F distinct roster items
+ with underlying undirected edges forming a forest, the
+ number of ordered pairs (p, p') with p != p' whose
+ difference residue v_p - v_{p'} lands in W is at most
+
+ C_cl = 2^{|Lambda|} (1 + 4 F^2),
+
+ where F = 400.
+
+ The construction is explicit and finite. Here are the key ideas.
+
+
+6.3 Coordinate blocks per left/right assignment
+
+For every map chi : Lambda -> {L, R} we build one "first coordinate"
+of prime order q (large) and a "batch" of redundant coordinates. A
+tag alpha is "left" at chi if chi(alpha) = L, else "right."
+
+First coordinate:
+ - Left tag alpha: the first coordinate of I_alpha is exactly 0.
+ - Right tag alpha: the first coordinate of I_alpha is nonzero.
+ - Left tag alpha: the first coordinate of any element of J_alpha
+ is nonzero.
+ - Right tag alpha: the first coordinate of J_alpha is exactly 0.
+
+Batch coords (all left tags alpha):
+ - I_alpha sits within 1/16 of a center from C_I = {0, 1, 3}/6.
+ - J_alpha sits within 1/16 of a center from C_J = {2, 4, 5}/6.
+Right tags: both I_alpha and J_alpha are "small" in a strict
+majority of batch coordinates (within 1/100 of 0).
+
+
+6.4 Two key inequalities
+
+ Sums cover everything. For a left tag, any target t is a sum:
+ C_I + C_J contains all six multiples of 1/6, and 1/16 slack in
+ each batch absorbs any rounding error. For a right tag, any
+ target with a small coordinate in each batch is a sum. Hence an
+ s notin W (which has a small coordinate in every batch) is a
+ sum for every tag.
+
+ Differences are separated. Across EVERY batch coordinate, any
+ left-tag diagonal difference i - j (i, j from I_alpha, J_alpha
+ for the same left tag alpha) has |i - j| >= 1/6 - 2/16 = 1/24.
+ Across SOME batch coordinate, any right-tag diagonal difference
+ i' - j' (same right tag alpha') has |i' - j'| <= 2/100 < 1/24.
+ So a left-diagonal difference and a right-diagonal difference
+ can never be equal as full vectors.
+
+
+6.5 Why relation (i) holds
+
+Take any fixed chi. In the first coordinate:
+
+ - Left tag alpha: I_alpha first = 0, J_alpha first nonzero.
+ - Right tag alpha: I_alpha first nonzero, J_alpha first = 0.
+
+Excluding off-diagonal pairs when s notin W. Suppose s notin W, so
+every first coordinate of s is nonzero. If (alpha, alpha') were an
+off-diagonal pair in E(s), choose a chi with alpha left and alpha'
+right. In this block, s[first] = I_alpha[first] + J_alpha'[first]
+= 0 + 0 = 0. Contradiction. So no off-diagonal pair is in E(s).
+
+The full diagonal is present for s notin W by the sum
+constructions (left tags: any target; right tags: any target with
+a small coordinate). So E(s) is exactly the full diagonal.
+
+At most one off-diagonal pair, at any s. Suppose (alpha, alpha')
+is an off-diagonal pair in E(s). Any other pair (lambda, mu) with
+different unordered pair may be excluded: choose a chi with alpha
+left, alpha' right, and lambda, mu on the same side. In this block,
+(alpha, alpha') forces s[first] = 0, while (lambda, mu) forces
+s[first] != 0. Contradiction, so (lambda, mu) is not in E(s).
+
+The remaining competitor is the reverse pair (alpha', alpha). If
+both are in E(s), there would be elements satisfying
+
+ i_alpha + j_alpha' = s = i_alpha' + j_alpha,
+ so i_alpha - j_alpha = i_alpha' - j_alpha'.
+
+LHS is a left-diagonal difference (for left tag alpha); RHS is a
+right-diagonal difference (for right tag alpha'). By the two key
+inequalities, these can never be equal as full vectors.
+Contradiction. So only one off-diagonal pair survives at s.
+
+
+6.6 Roster residues v_p
+
+In every first coordinate of every chi, place roster items p_0,
+p_1, ... with v_{p_j} = 2^j modulo q. For two distinct a < b,
+
+ v_{p_b} - v_{p_a} = 2^b - 2^a = 2^a (2^{b-a} - 1).
+
+The exact power of 2 identifies a, and after removing it, the odd
+factor 2^{b-a} - 1 identifies b - a. So distinct ordered pairs give
+distinct nonzero integers, and choosing q > 2^r preserves this in
+Z/qZ. The v_p are then distinct on every first coordinate.
+
+
+6.7 Dedicated batch coordinates
+
+For every ordered list ((p_a, p'_a))_{a=0}^{F-1} of F distinct
+roster items with underlying undirected edges forming a forest,
+give one dedicated batch coordinate. Set z_a = grid point within
+1/(2q) of a/F, and prescribe v_{p'_a} - v_{p_a} = z_a in this
+coordinate. This is satisfiable (forest has no cycle constraint).
+
+Then for any translate u, some a has |u + z_a| <= 1/(2F) + 1/(2q)
+< 1/400 < 1/100. So every dedicated forest has a NEGATIVE witness:
+some pair with SMALL translated difference in that coordinate.
+
+Counting bad ordered pairs for a batch. Fix u and a batch. Call a
+pair (p, p') "bad" if u + v_{p'} - v_p has no small coordinate.
+Form the undirected graph of bad pairs (drop isolated vertices). If
+a spanning forest had fewer than F edges, its vertices would be at
+most 2F - 2, so the number of unordered pairs would be at most
+(2F-2)(2F-3) < 4F^2. But we could pick F edges of the forest and
+they would form one of the dedicated lists, forcing a violation.
+So a spanning forest has >= F edges; hence the number of bad
+ordered pairs is at most 4F^2. Take the union over all 2^{|Lambda|}
+blocks and add 1 from the first-coordinate obstructions: total
+at most C_cl = 2^{|Lambda|} (1 + 4 F^2).
+
+
+PART 7. LOCAL MARKERS AND MOVING BOUNDARIES
+
+
+7.1 Why markers and scales
+
+The suffix does not know where the first episode that produced its
+argument truly began. It has a bounded candidate list, but the
+interval products it must check depend on the true start position.
+If the true start is far from every candidate, nothing works.
+
+The remedy is a pair of tools. "Markers" are well-spaced integer
+positions; "scales" are scales of sliding the boundary. Boundaries
+are locally determined: near a marker, the boundary IS the marker;
+away from any marker, the boundary follows a periodic extension of
+the local word. This gives a finite set of possible boundary
+positions and a uniform bound on how often ambiguity fails.
+
+
+7.2 Local markers
+
+ Lemma. Let d >= 2 and K > 3d^2. There is a translation-
+ equivariant rule marking integer positions of any two-sided word
+ such that:
+ - distinct markers are at distance at least d;
+ - the decision at z uses only [z-r, z+r) for a fixed finite
+ integer r >= K;
+ - if there is no marker in [z-d, z+d], then the block
+ [z, z+K) has a positive period less than d.
+
+ Proof sketch. List the finitely many length-K words with no
+ positive period below d. Process them in a fixed order, marking
+ all starts not within distance < d of an earlier marker. Two
+ starts added at the same step cannot be at distance a < d:
+ their overlap would make a a period of the listed word.
+ Contradiction. The finite list gives a finite inspection
+ radius; enlarge it to at least K. The absent-marker conclusion
+ follows: any "would-be-marked" start either was marked at its
+ step, or has a marker within distance < d. QED.
+
+The marker-vs-periodicity principle is due to Krieger (1982).
+We use only the elementary finite-window version above.
+
+
+7.3 Common periodic extensions
+
+ Lemma. A block of length K > 3d^2 with positive period below d
+ determines a unique two-sided periodic extension of period below
+ d. Two such blocks whose starts differ by less than K - d^2
+ determine the same extension. If no marker is in [z-H, z+H],
+ H >= d, then the actual letters on [z-H+d, z+H-d+K) belong to
+ one such extension.
+
+ Sketch. A block of period a extends by repeating its first a
+ letters. Two two-sided periodic words of periods a, b that
+ agree on ab consecutive positions agree everywhere (standard
+ fact). Here a, b < d, so ab < d^2. QED.
+
+
+7.4 The vector spaces U_0, U_1, U_2
+
+The construction lifts V = F_2^M to two larger spaces. For any M
+and any F_2-vector space U with a linear right action of M, let
+U x M be the space with basis e_{[v,c]} for v in U, c in M. The
+right action is
+
+ [v, c] . d = [v . d, cd].
+
+Then choose U_0 = V, U_1 = U_0 x M, U_2 = U_1 x M. The "work
+actions" rho_i : M -> End(U_{i+1}) on U_{i+1} are defined by
+rho_i(d)([v, c]) = [v, cd]. Note that rho_i has nothing to do with
+the episode structure; it is a generic linear action that only
+multiplies the M-coordinate.
+
+The key property: the basis vector [v, 1_M] is "distinguished", and
+after multiplying by a product of M-elements, the M-coordinate
+stays 1_M. So the distinguished basis is closed under the
+computation, letting us transport vectors of V up through the lifts
+without ambiguity.
+
+
+7.5 Buffer kinds and stencils
+
+Each episode has two buffers preceding its main cut, physically in
+the order 1 then 0 along the word. Buffer i has checkpoints B_{i,0}
+< ... < B_{i,l_i} < a_i. The kind of a buffer-i hypothesis is
+
+ (j, v, d_1, ..., d_{j-1}) with 1 <= j <= l_i, v in U_{i+1},
+ d_f in M.
+
+It says "the hidden interval index is j, the input vector at B_{i,0}
+is v, and the interval products before j are d_1, ..., d_{j-1}."
+
+A stencil P_i is a finite set of integer offsets from s together
+with a kind assigned to each offset. We need more offsets of each
+kind than the total bad-origin count C_0 = C_cl + 2^{l} (something),
+so that a good offset always exists.
+
+
+7.6 Polynomial roster
+
+Roster items are polynomials p of degree < k_0 over a prime field
+F_P. Fix R distinct evaluation points xi_1, ..., xi_R in F_P. The
+"digit" at scale r is x_r(p) = p(xi_r).
+
+Two distinct polynomials of degree < k_0 have at most k_0 - 1 roots,
+so distinct polynomials differ in at least R - k_0 + 1 = k_0 digits.
+This is the Reed-Solomon distance property.
+
+Choose positions f_r(0) < ... < f_r(P-1) at each scale r so that
+all nonzero digit differences are distinct and well-separated.
+Give slot p the numerical offset
+
+ sum_{r=1}^{R} f_r(x_r(p)) + epsilon_p,
+
+where 0 <= epsilon_p < n is a small correction to land on residue
+v_p mod n. Then distinct slots get distinct offsets, any two
+offsets are separated by more than 2, and the residues match v_p.
+Choose P large enough that P^{k_0} / kappa_0 > C_0.
+
+
+7.7 Scales and usability
+
+For each scale r in 1..R, choose integers
+
+ S_r < S'_r thresholds
+ delta_r smooth (coprime to n)
+ R_r = n delta_r movement bound
+ f_r as above
+
+with S'_r dominating all smaller scales' diameters and movements.
+The inequalities ensure that a nonzero digit at scale r dominates
+all smaller digits plus the epsilon correction.
+
+A scale r is usable at origin t if, at every center z_j = t + o_j,
+
+ - the first-marker search is stable under all shifts of size
+ <= R_r (same answer), or
+ - the search is absent and the periodic-extension lattice is
+ too coarse to be affected by any such shift.
+
+If r is usable, then shifted boundaries B_j^{(h)} := B(z_j + h)
+for h = delta_r a (0 <= a < n) give identical interval products:
+
+ T_{B_{j-1}^{(h)}, B_j^{(h)}} = T_{B_{j-1}, B_j} for all j.
+
+
+7.8 Transport lemma
+
+ Lemma. Suppose scale r is usable at t, and h is a multiple of
+ delta_r with |h| <= R_r. Then T_{B_{j-1}, B_j} = T_{B_{j-1}^{(h)},
+ B_j^{(h)}} for all j. And for any fixed end b >= z_l + H,
+ T_{B_l, b} = T_{B_l^{(h)}, b}.
+
+ Sketch. The two boundaries at each center stay in the same
+ class modulo d * N (d = period, N = |M|, since the shift is
+ delta_r * n * something). Actual word has a full periodic run
+ around each boundary (by the marker lemma). Monoid-power
+ periodicity c^{h+N} = c^h for h >= m then gives the interval
+ product equality, one endpoint at a time. QED.
+
+
+7.9 Inner ambiguity bound
+
+For an origin t and an anchor q, define the "bad" predicate
+
+ A_0(t, q): q - t (mod n) in W, OR no scale usable at t.
+
+ Proposition. On any two-sided word, for any integers t, q,
+
+ #{(p, p') in P_0^2 : p != p', A_0(t + p - p', q)} <= C_0,
+
+ where C_0 = C_cl + 2^R (3Z+1)^R P^{2Z}, with Z = l + 1.
+
+ Sketch. Two cases.
+
+ (a) Clock failure: q - t - (p - p') mod n in W. By the clock
+ property, at most C_cl ordered pairs survive.
+
+ (b) No usable scale: examine digit differences D_r = f_r(x_r(p))
+ - f_r(x_r(p')). Distinct slots differ in at least k_0 = 2Z
+ + 1 digits. At each nonexceptional scale r, the marker
+ search range under all shifts bounded by R_r contains at
+ most one marker (or one lattice point); this pins D_r to at
+ most 3Z+1 possible values. Exceptional scales (at most Z in
+ number) contribute at most P^{2Z}. Multiplying over scales
+ gives the bound.
+
+ Sum the two contributions. QED.
+
+
+PART 8. EPISODES AND EXACT END DETECTION
+
+
+8.1 Second stencil and end-marker rule
+
+The main split cuts an episode at one of many buffer positions. To
+enforce exact ends (so P_x Q_y consumes exactly one episode), we
+need a separate end-marker system. Choose integers d_e, K_e with
+d_e > 10(1 + w + h_1) and K_e > 3d_e^2. Apply the marker lemma with
+these parameters to obtain an end-marker rule of radius r_e >= K_e.
+
+Each episode has an "end-search center" z_e(t) = t + o_e. The end
+marker function eta(t) is the first end marker in the inclusive
+interval [z_e(t) - d_e, z_e(t) + d_e], or "absent" if none.
+
+Predicate A_1(t) is "eta changes somewhere within a shift of size w":
+
+ A_1(t): exists u, |u| <= w, with eta(t+u) != eta(t).
+
+
+8.2 End ambiguity lemma
+
+ Lemma. On any two-sided word, uniformly in t,
+
+ #{(p, p') in P_1^2 : p != p', there exists gamma in Delta_0
+ with A_1(t + p - p' + gamma)}
+ <= C_1,
+
+ where Delta_0 is a fixed finite set of integer offsets and
+ C_1 = 2 |Delta_0|.
+
+ Sketch. If the first marker in a moving search interval changes
+ under a shift of size <= w, a marker crosses an endpoint. Fix
+ gamma and an endpoint. As p - p' ranges over the roster of
+ ordered differences, the possible marker positions lie in a
+ bounded interval of diameter at most 2h_1 + 2w < d_e, which
+ contains at most one end marker. That marker pins p - p' to an
+ interval of length 2w, so at most one nonzero ordered pair. Two
+ endpoints, |Delta_0| choices of gamma: 2 |Delta_0| in total. QED.
+
+
+8.3 The anchor rule
+
+For an episode beginning at s and true origin t = s + L:
+
+ - If eta(t) is present (a marker exists): set q = eta(t).
+ - Otherwise, the seed [z_e(t), z_e(t) + K_e) has a period < d_e
+ by the marker lemma, hence determines a unique two-sided
+ periodic extension. Set q = the position of the first mismatch
+ (first position where the actual word differs from the
+ extension), if any such position exists.
+
+The episode ends at q + b_tail, for a fixed positive integer b_tail.
+Episodes for which eta is absent and no mismatch appears are
+incomplete: they are not episodes.
+
+
+8.4 The episode language E
+
+Let E be the set of nonempty words starting at s such that:
+ - all required windows are available (they lie inside the word
+ with sufficient margins on each side);
+ - the anchor rule gives a well-defined q;
+ - the word ends exactly at q + b_tail.
+
+E is a prefix code: no member of E is a proper prefix of another
+member. Proof: every marker and bounded-control decision is
+unaffected by appending letters, because each decision window lies
+strictly inside the current word. So any extension of an episode
+has the same anchor and the same endpoint, and can be a complete
+episode only if it ends at that endpoint. QED.
+
+
+8.5 Placement
+
+The main construction slips finite "windows" around each episode
+to ensure every required datum is available on the correct side of
+any cut.
+
+ Lemma. The translations of the two buffers and the integers L,
+ o_e, b_tail can be chosen so that:
+ (i) After s, the buffers occur in order 1, 0, then all
+ relevant inner-system windows and cuts, then all
+ relevant end-system windows and seeds.
+ (ii) All bounded windows required at main hypotheses or at
+ aligned buffer hypotheses are internal to every
+ complete episode at a true cut.
+ (iii) A prefix or suffix computation has its required data
+ on its own side of a true cut.
+ (iv) Every possible true first-episode end is after all cuts
+ and bounded control windows.
+
+ Sketch. Three finite envelopes chosen in acyclic order:
+ 1. Fix buffer offsets from s; put buffer 1 before buffer 0.
+ 2. Choose L large enough that the inner envelope (inner
+ windows, buffer-related data, all usability shifts) sits
+ after all buffer data.
+ 3. Choose o_e large enough that the end envelope (end windows,
+ seeds) sits after the inner envelope.
+ 4. Choose b_tail large enough that the fixed tail sits after
+ the end envelope.
+ Each step only enlarges a translation. QED.
+
+
+8.6 End guard
+
+A suffix with a finite candidate list {k - h : h in H} forms its
+"end guard" by:
+
+ - requiring eta to agree across all candidates,
+ - requiring the exact-end test (anchor rule plus endpoint
+ q + b_tail) at one fixed reference candidate in the list.
+
+ Lemma (end guard). Suppose a finite word begins with a complete
+ episode e of true origin t and anchor q. A prefix cut k lies
+ inside e. Let a suffix argument at k use an end guard whose
+ candidate list contains t and has diameter at most w. If the
+ guard accepts, the suffix ends exactly at the end of e, and its
+ reported anchor is q. This conclusion holds even if the
+ proposed suffix initially ends before e or extends past e.
+
+ Sketch. On the true episode all candidate windows are present.
+ A premature suffix would miss a mandatory window; an excessive
+ suffix would still attempt to end at q + b_tail. Both excluded
+ by the availability requirement. QED.
+
+
+8.7 Why buffers are in reverse order
+
+The construction uses buffer 1 then buffer 0 along the word, even
+though the update-order is g_0 then g_1 then g_2. This reversed
+physical order is what lets the suffix compute the "lift" data that
+the main split needs: the buffer-1 suffix is physically positioned
+to observe the later buffer-0 segment data, so it can build the
+total table Phi_1 that encodes g_1 into g_2's lifted linear part.
+Without this reversal, the second lift could not be built from the
+suffix data alone.
+
+
+PART 9. THE THREE SPLIT CONSTRUCTIONS
+
+
+9.1 The main update g_0
+
+Fix an episode e with start s, true origin t = s + L, anchor q,
+end b = q + b_tail. Set:
+
+ T_e = T_{s, b} total monoid value of e
+ d_j = T_{B_{j-1}, B_j} interval products, 1 <= j <= l
+ d = (d_1, ..., d_l) tuple of interval products
+ res = q - t (mod n) anchor-cut residue
+ E(res) = {(alpha, lambda) in Lambda^2 : res in I_alpha + J_lambda}
+
+Define the main update g_{0,e} : V -> V by
+
+ Diagonal case (E(res) subset of diagonal):
+ g_{0,e}(x) = x T_e + beta(d) T_{B_l, b}
+
+ Off-diagonal case (E(res) = {(alpha, lambda)}, alpha != lambda):
+ g_{0,e}(x) = x T_e + Y(lambda) - X(alpha) T_e
+
+In both cases this is affine on V with linear part x -> x T_e. The
+correction term is built from e's own data, so g_{0,e} is determined
+by e alone, independent of any prefix or suffix choices.
+
+
+9.2 Main prefix and suffix tests
+
+ Prefix P_x^main (x in V). Choose a buffer kind (j, v, d_1, ...,
+ d_{j-1}) and a residue representative a in I_alpha, and check:
+ - x = v at the start (which is s for the prefix).
+ - the preceding products d_1, ..., d_{j-1} match their true
+ values on the episode prefix.
+ - the prefix ends at the buffer position corresponding to j.
+ P_x^main has height 0 (finite languages of fixed-length words).
+
+ Suffix Q_y^main (y in V). The suffix sees the letters from its
+ cut position k to the end of the whole word (which extends past
+ the first episode). It does:
+ 1. Enumerate candidate origins tau_{p'} = k + L - p' for
+ roster items p'.
+ 2. Apply the end guard: eta must agree across all candidates;
+ require the exact-end test at one reference candidate.
+ 3. Enumerate surviving (alpha, lambda) pairs via the clock:
+ for each, check residue membership.
+ 4. For each surviving (alpha, lambda) pair in E(res), compute the
+ corrected vector: if diagonal, add beta(d) T_{B_l, b}; if
+ off-diagonal, add Y(lambda) - X(alpha) T_e.
+ 5. Apply H_0 and compare to y.
+
+ Q_y^main has height at most 1 (single exact-end rule).
+
+
+9.3 Main split proposition
+
+ Proposition. The languages P_x^main and Q_y^main satisfy the two
+ split hypotheses of Part 4 for the episode update g_0, with
+ D = E and D' = {e in E : A_0(t, q) or A_1(t)}.
+
+ Sketch.
+ Soundness: any accepted concatenation has cut inside the first
+ episode, and the end guard forces exact consumption. The clock
+ gives either alpha = lambda or one specific off-diagonal pair.
+ In the diagonal case, at true origin tau = t, clock properties
+ give the exact sandwiching, and line constancy (via the Erdos-
+ Lovasz lemma) gives the correct lift to B_l. In the off-diagonal
+ case, the constant Y - X exactly compensates the tag mismatch.
+
+ Completeness: for e in E \ D', some scale is usable, so the
+ transport lemma gives equal later products for all candidates;
+ affine-line lemma gives an interval j; clock gives a residue;
+ since gcd(delta_r, n) = 1, some a gives k - t in I_alpha, so
+ prefix and suffix clock tests both succeed. End guard succeeds
+ because A_1(t) is false. The split gives exactly g_0(x) = y.
+ QED.
+
+
+9.4 The two exceptional classes D_0, D_1
+
+Define:
+
+ D_2 = empty.
+ D_1 = {e in D_0 : exists gamma in Delta_0 with A_1(t+gamma)}.
+ D_0 = {e in E : A_0(t, q) or A_1(t)}.
+
+Since 0 is in Delta_0, "e in D_0 \ D_1" implies A_0(t, q) and no
+A_1 hits for any gamma in Delta_0.
+
+The construction goes from bottom (D_2, easy) to top (E, hard):
+
+ 0 -> 2 (on D_1*): stage-1 aligned split, skip D_2 = empty.
+ 2 -> 2 (on D_1*): Boolean recover g_1 from g_2.
+ 2 -> 3 (on D_0*): stage-0 aligned split, skip D_1.
+ 3 -> 3 (on D_0*): Boolean recover g_0 from g_1.
+ 3 -> 4 (on E*): main split, skip D_0.
+ 4 -> 4 (on E*): final recovery of the monoid value.
+
+
+9.5 Total tables and lifts
+
+To handle the D_0 class (where A_0 or A_1 fails), we encode g_0 in a
+linear map on a larger space and recover it later. This uses a
+"total prefix table" Phi_i : M -> End(U_i) for each buffer i. The
+table is determined by the suffix's data after a_i and is defined
+for all hypothetical monoid values.
+
+The initial table (i = 0). Let A = T_{a_0, b} and C = T_{B_l, b}.
+For every c in M and v in U_0 = V:
+
+ Phi_0(c)(v) =
+ v(cA) + beta(d) C (diagonal clock)
+ v(cA) + Y(lambda) - X(alpha)(cA) (off-diagonal clock)
+
+Substituting the true c = T_{s, a_0} recovers g_0. The formula only
+uses c hypothetically, so it can be used even when c is not the
+true prefix product.
+
+The lift to U_{i+1}. Define the linear map H_i : U_{i+1} -> U_{i+1}
+on basis vectors by
+
+ H_i([v, c]) = [Phi_i(c)(v), 1_M].
+
+The next-level update is
+
+ g_{i+1, e}(z) =
+ ( z rho_i(T_{s, a_i})
+ + beta_i(d_i) rho_i(T_{B_{i, l_i}, a_i}) ) H_i,
+
+where d_i is the tuple of interval products in buffer i. Its linear
+part is L_{i+1, e} = rho_i(T_{s, a_i}) H_i. The crucial identity,
+on distinguished basis vectors [v, 1_M]:
+
+ [v, 1_M] L_{i+1, e} = [g_{i, e}(v), 1_M].
+
+So the lift linearly encodes the smaller update on distinguished
+basis. This is the first lift (i = 0, giving g_1 from g_0) and the
+second lift (i = 1, giving g_2 from g_1).
+
+
+9.6 Aligned decoders
+
+For i = 0, 1, we define P_x^{(i)}, Q_y^{(i)} for x, y in U_{i+1}.
+These implement g_{i+1} on D_i with skipped class D_{i+1}.
+
+ Prefix P_x^{(i)}: choose offset p in P_i (stencil of buffer's
+ checkpoints). If the kind attached to p is (j, v, d_1, ..., d_{j-1}),
+ check v = x . rho_i(T_{s, B_{i, 0}}) and d_f = T_{B_{i, f-1}, B_{i, f}}
+ for f < j. All these checks precede the cut.
+
+ Suffix Q_y^{(i)}: candidate origins tau_{p'} = k + L - p' for p'
+ in P_i. Two decoding paths:
+ - Stage 0 (i = 0): require A_1(tau_{p'}) false for every
+ candidate. Apply end guard to the full candidate list,
+ obtaining anchor q. Require a unique p' with A_0(tau_{p'},
+ q) true. All A_0 evaluations use this same anchor, so no
+ additional unbounded end searches.
+ - Stage 1 (i = 1): require a unique p' such that exists
+ gamma in Delta_0 with A_1(tau_{p'} + gamma). Bounded
+ controls, no q involved. After decoding p', apply the
+ exact end rule at tau_{p'} to obtain q and the argument end.
+
+ After decoding, set s' = k - p' and use the kind at p'. The
+ suffix supplies later products d_f for j < f <= l_i, checks
+ the line-constancy condition, then applies H_i and compares to
+ y.
+
+
+9.7 Aligned split proposition
+
+ Proposition. For i = 0, 1, the languages P_x^{(i)}, Q_y^{(i)}
+ satisfy the two split hypotheses of Part 4 for the update
+ g_{i+1}, with D = D_i and D' = D_{i+1}.
+
+
+9.8 Recovery chain
+
+The input and output of each split are now established:
+
+ g_2 on D_1*: height after stage-1 split = 0 -> 2.
+ g_1 on D_1*: Boolean recovery, stays at 2.
+ g_1 on D_0*: stage-0 split, 2 -> 3.
+ g_0 on D_0*: Boolean recovery, stays at 3.
+ g_0 on E*: main split, 3 -> 4.
+
+Finally, the composite g_0 update on E* through the affine recovery
+lemma gives a graph test for the linear part x -> x T_w on E*: for
+the whole word w in E*, T_w is exactly T(w). Applying to e_{1_M}
+in V gives e_{T(w)}, so the surviving basis index distinguishes the
+fiber T^{-1}(m). This final recovery is Boolean.
+
+So the graph language on E* from e_{1_M} to e_m has height at most
+4. This is the top of the ladder. In Part 10 we compile everything
+back to the original alphabet Sigma and close the last gap (words
+that are not complete episode sequences).
+
+
+PART 10. COMPILATION OVER THE ORIGINAL ALPHABET
+
+
+10.1 Periodic templates a b^h c
+
+Every component language S (P_x, Q_y, E, D_0, D_1, the leftover
+class F) has a single "unbounded continuation": the end-marker
+search that keeps going as far as the case keeps repeating letters.
+So the word follows one fixed period b until its first mismatch (or
+until it ends). This makes each component a finite union of
+templates.
+
+ Lemma (periodic templates). Take a finite collection of
+ templates
+
+ a b^h c, h >= 0
+
+ with fixed words a, b, c (b != eps). Suppose a test on each
+ template uses only:
+ (i) letters in fixed finite collections of windows at
+ offsets from the argument's start or end;
+ (ii) order and availability of endpoints from fixed finite
+ sets of offsets;
+ (iii) M-products between endpoints whenever available, and
+ lengths modulo fixed positive integers;
+ (iv) fixed finite combinations, choices, and calculations
+ from this data.
+
+ Then the accepted words have a generalized expression of height
+ <= 1. Adding or removing a finite language preserves this bound.
+ Furthermore, every exact-end test whose reference or decoded
+ origin is chosen from finitely many offsets relative to the test
+ start is covered by a finite language and finitely many such
+ templates.
+
+ Sketch. Fix a template. For large h, availability conditions
+ stabilize; the growing middle contains complete copies of b.
+ Any partial product has form u T(b)^{h-j} v for fixed u, v, j.
+ Because M is finite, powers of T(b) are ultimately periodic (if
+ two powers coincide, multiplying further gives a period). So
+ every product, every length-mod-n condition, and every finite
+ combination is ultimately periodic in h. Accepted exponents
+ become a finite set plus progressions { h_0 + f*k : k >= 0 }.
+ Each progression gives a b^{h_0} (b^f)^* c of height 1; finite
+ exceptions have height 0. Union over the finitely many templates:
+ height 1.
+
+ For the "Furthermore", fix an end-rule origin. Present-marker
+ case has bounded length (finite language). Absent-marker case:
+ finite choices of letters through the seed, sample short period
+ and phase, and fixed-length tail at the first mismatch give
+ a = prefix through seed, b = period word, c = post-mismatch
+ tail. Finitely many choices. QED.
+
+
+10.2 Component bounds
+
+ Proposition. The episode languages E, D_0, D_1 and every suffix
+ component Q_y have height at most one. Every prefix component
+ P_x has height zero. All bounds hold over the original alphabet
+ Sigma.
+
+ Sketch. Prefix P_x comes from fixed finite offset sets, so it is
+ finite (height 0).
+
+ Episode and suffix languages each have one exact-end rule on
+ their entire argument. For E, D_0, D_1 it is the true episode
+ rule; for Q_y at the main or stage-0 split it is the reference
+ rule inside the end guard; for Q_y at stage 1 it is the decoded
+ rule. Finitely many reference or decoded offsets. Apply the
+ template lemma.
+
+ All remaining operations - marker searches, usability, phase and
+ lattice choices, additional candidate translates, boundary
+ placement near centers, buffer boundary offsets, line-constancy,
+ total table Phi_i computations, terminal map H_i - inspect
+ bounded windows at fixed nominal offsets or are finite
+ combinations of actual partial products. All partial products
+ have endpoints in a finite set of start offsets, except for the
+ argument end itself, which the anchor rule pins to end - b_tail.
+ So all data are ultimately periodic in the template length. QED.
+
+
+10.3 The remainder
+
+Not every word is a complete sequence of episodes: some words stop
+before finishing an episode. Define
+
+ F = ~(E Sigma*), Sigma* = ~0.
+
+So F consists of words that cannot start with a complete episode.
+
+ Lemma. For every d in M, F intersect T^{-1}(d) has height at
+ most one.
+
+ Sketch. Choose a threshold length exceeding all bounded windows
+ at a first start and all possible first-episode lengths in the
+ present-marker case. A longer word in F cannot have a present
+ end marker: that would already make a complete episode prefix.
+ Its marker-absent seed has a fixed period; either no mismatch
+ has appeared, or its first mismatch is within b_tail of the end
+ (if it were farther, the prefix ending at q + b_tail would be a
+ complete episode). Finite choices of the bounded initial word,
+ the period, the phase, and the final partial period give
+ templates a b^h c. On every template T(u) = d is ultimately
+ periodic in h, so the template lemma gives a height-one
+ language with that value on the template cover. Intersecting
+ with F keeps the same bound. Words below the threshold form a
+ finite language. QED.
+
+ Lemma (unique parsing). Every word admits a unique factorization
+ into a sequence of episodes followed by a word in F.
+
+ Proof. Repeatedly remove an episode prefix while one exists.
+ Every episode is nonempty, so this terminates. The remaining
+ word is in F. The prefix-code property makes each removed
+ prefix unique. Any alternative E*F factorization must remove the
+ same successive episodes; it also cannot stop earlier while an
+ episode prefix remains. QED.
+
+
+PART 11. PROOF OF THE MAIN THEOREM
+
+
+11.1 Assembling the expression
+
+Fix m, d, f in M with d f = m. Set:
+
+ G_d = graph language on E* from e_{1_M} to e_d (height <= 4)
+ F_f = F intersect T^{-1}(f) (height <= 1)
+
+The unique-parsing lemma says every word w in T^{-1}(m) is in
+exactly one such product G_d F_f (with d = T(episodes), f =
+T(remainder)), and conversely every word in such a product lies in
+T^{-1}(m) because T(w) = d f = m. So
+
+ T^{-1}(m) =
+ union over (d, f) in M^2 with d f = m of G_d F_f.
+
+Each factor has height at most 4 (resp. 1); their concatenation has
+height at most max(4, 1) = 4; the finite union over M^2 also has
+height at most 4. All operations are over the original alphabet
+Sigma.
+
+
+11.2 The main theorem
+
+ Theorem. For every finite alphabet Sigma and every regular
+ language L contained in Sigma*, one has h(L) <= 4.
+
+ Proof. Follow the reduction (Section 2.1) from L to a morphism
+ T : Sigma* -> M and a finite union of fibers T^{-1}(m). For
+ each fiber our construction gives an expression of height at
+ most 4 over Sigma. Finite unions do not increase height. QED.
+
+
+11.3 What is not proved
+
+ - The construction gives no bound on the length of expressions
+ or on the running time to find them. It is constructive in
+ principle but not in complexity.
+
+ - The construction does not exhibit any specific regular
+ language that requires generalized star height > 1. It is
+ compatible with the conjecture that height 1 always suffices.
+
+ - The bound 4 is not claimed optimal. The companion paper
+ (Height3) improves it to 3; whether 1 suffices is open.
+
+
+PART 12. WHAT WE GAINED AND THE GLOSSARY
+
+
+12.1 The bound 4
+
+Every regular language has generalized star height at most 4.
+Companion papers improve this to 3; whether 1 suffices is a
+still-open problem.
+
+The present paper's proof uses three conceptually distinct tools,
+each contributing something real.
+
+ - Splits. A star-producing operation: converts a graph test
+ on a smaller episode class into one on a larger class. Each
+ split adds one to the height.
+
+ - Affine corrections. A probabilistic construction
+ (Erdos-Lovasz local lemma) that lets a single correction
+ function hide one interval product from any cut, for every
+ tuple of inputs simultaneously and every choice of tuple.
+
+ - Finite clock and multiple scales. A bounded-disjunction
+ system that converts unbounded tag ambiguity into bounded
+ tag uncertainty, and a set of scales that keeps interval
+ products stable under small origin shifts.
+
+These three tools are independent of the companion "Generalized
+star height at most three" paper's method. They also do not rely on
+that paper's stronger numerical bound. Together they show directly
+that the generalized star height is finite-term bounded for every
+regular language, with no dependence on Sigma's size, the language
+L, or the number of automaton states.
+
+
+12.2 What is still open
+
+ - Does every regular language have generalized star height at
+ most one? Known partial results: aperiodic monoids
+ (Schutzenberger), finite commutative groups (Henneman),
+ nilpotent groups of class two (Pin-Straubing-Therien).
+
+ - Can the methods here be sharpened to give an explicit lower
+ bound, if some language actually requires height > 1? No such
+ language is currently known.
+
+ - Is there a bound on expression length or on how large the
+ finite choices must be? The present paper gives none.
+
+
+12.3 Glossary
+
+ Sigma finite alphabet
+ Sigma* all finite words over Sigma, including eps
+ L a regular language, subset of Sigma*
+ P + Q, PQ union, concatenation of languages
+ ~P complement of P in Sigma*
+ P* Kleene star
+ ht(E) star height: maximum nesting depth of * in E
+ h(L) generalized star height: min ht(E) over
+ expressions E for L
+ M finite monoid, image of transition morphism
+ T morphism Sigma* -> M
+ T^{-1}(m) fiber of T at m
+ V = F_2^M vector space over F_2 with basis indexed by M
+ T_{a,b} monoid product of letters at positions
+ a through b-1
+ prefix code E subset of Sigma+ with no element a proper
+ prefix of another
+ E* concatenations of episodes; unique
+ factorization (prefix-code property)
+ graph language from x to y on D*: words whose composite
+ update sends x to y (domain D* required)
+ split lemma converts a graph test on D'* to one on D*,
+ using prefix P_x and suffix Q_y. +1 height.
+ affine-line lemma existence of correction beta hiding one
+ interval product of any tuple of M-values,
+ uniformly in the input state and tuple
+ affine recovery from graph languages of an affine composite,
+ extract graph language of the product of
+ linear parts, via finite Boolean operations
+ clock modulus n and sets I_alpha, J_alpha, plus
+ bad set W. Bounded disjunction of "how tags
+ agree at a residue."
+ marker well-spaced integer positions deciding
+ whether a long block is periodic
+ U_0, U_1, U_2 nested vector spaces for the two lifts
+ g_0, g_1, g_2 episode updates at three levels
+ D_0, D_1, D_2 exceptional classes; at each stage the
+ "skip" class is fixed
+ a b^h c template with ultimate period b and
+ finite a, c
+
+End of glossary.
+
+The bound 4 is what this paper establishes. The proof is a single
+coherent construction that reduces every regular fiber to a finite
+union of episode-sequence components and a remainder, and it
+isolates the three techniques (splits, affine corrections, finite
+clock plus scales) that make the problem tractable.
+
+The height-one problem remains open.