DEDICATION

To generalized star height, and to the exploration of the exact
threshold between bounded and unbounded generalized star height.

A finite alphabet Sigma is fixed. Words are finite sequences of
letters; the empty word is eps. Sigma* denotes the set of all words.
A language is any subset of Sigma*. A regular expression is built
from the empty language, the language {eps}, and single letters, by
union, concatenation, complement in Sigma*, and Kleene star. The
star height ht(E) of an expression is the deepest nesting of stars:

  ht(empty)         = 0
  ht({eps})         = 0
  ht({a})           = 0    for each letter a
  ht(P union Q)     = max(ht(P), ht(Q))
  ht(P Q)           = max(ht(P), ht(Q))
  ht(complement P)  = ht(P)
  ht(P*)            = 1 + ht(P).

The star height of a regular language L is the least ht(E) over all
expressions E with L(E) = L. An absolute bound for this quantity,
uniform in Sigma and in L, is the subject.

The theorem proved is the following.

  Every regular language over a finite alphabet has star height at
  most 4.

The bound depends on neither Sigma, L, nor the size of a recognizing
automaton. Whether the sharper bound 1 always suffices is open.

Background. Eggan introduced ordinary star height and separated the
first few levels using transition graphs of deterministic automata.
Dejean and Schutzenberger proved unbounded ordinary star height over
a binary alphabet.

./eggan-1963.pdf
./dejean-schutzenberger-1966.pdf

Schutzenberger characterized the languages of ordinary star height
zero, equivalently the languages of generalized star height zero, as
those recognized by finite aperiodic monoids.

./schutzenberger-1965.pdf

Henneman proved that every language recognized by a finite
commutative group has generalized star height at most one. Pin,
Straubing, and Therien extended the conclusion to finite nilpotent
groups of class two and established closure properties for the
star-height strata. Straubing formulated the absolute boundedness
question and the sharper question whether height one always suffices.
Earlier reports include studies of the height-three case and of
uniform computations for finite monoids.

./pst-1992.pdf
./straubing2002.pdf
./height3.pdf
./uniform13.pdf

Reduction. A regular language L is recognized by a finite monoid M
through a morphism T: Sigma* -> M. The syntactic monoid of L is
finite, so M can always be chosen finite. Letter a of Sigma maps to
T(a) in M, and a concatenation w = a_1 a_2 ... a_k maps to the
product T(a_1) T(a_2) ... T(a_k) in reading order. Because M is
finite, no complexity claim is made; only the depth of stars is
bounded.

For integers A < B in the indexing of a word w let T_w[A, B] be the
product of the letters between positions A and B in reading order.
When the word is fixed, T[A, B] is used.

Linearizing. Set V = F2^M, the F2-vector space with basis indexed by
M. For m, c in M define e_m rho_0(c) = e_{m c}. This is a linear
right action rho_0: V x M -> V. A word w acts on V by
v -> v rho_0(T(w)), the linear map associated to T(w). The graph
languages below construct this map on nice subclasses of words.

Episodes and prefix codes. A prefix code over Sigma is a set E of
nonempty words such that no member of E is a proper prefix of
another. Every word in E* has a unique factorization into episodes:
two factorizations w = e_1 e_2 ... = f_1 f_2 ... of the same word
first differ at some length L; the prefixes e_1 and f_1 of the
prefix of w of length L are comparable as prefixes, and the
prefix-code property forces e_1 = f_1. Cancel and iterate.

Graph languages. Let D be a subset of E, and (G_e) for e in D a
family of deterministic updates of a finite set S. For x, y in S
write W[x, y](D) for the set of w in D* whose factorization
e_1 ... e_k satisfies G_{e_k}(... G_{e_1}(x) ...) = y. The empty
word of D* corresponds to the identity update.

The graph languages have the form

  W[x, y] = union over e in D with G_e(x) = y of {e}
            union over z in S of W[x, z](D) W[z, y](D).

When x = y, the empty word eps belongs to W[x, y].

The split principle. At each stage graph languages on a larger
episode class D are built from graph languages on a smaller skipped
class D'. The inductive step is the following lemma.

Lemma (split). Let D' subset D, and let (G_e) for e in D be
deterministic updates of a finite set S. Choose languages P_x, Q_y
for x, y in S. Assume:

  (i) If a word in D* has a prefix uv with u in P_x and v in Q_y,
  then the first episode e of that word exists, uv = 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)}.

Let W[x, y] denote the graph languages on D', and W'[x, y] the graph
languages on D. Then for every x, y in S,

  W'[x, y] = D* cap [ W[x, y]
      union ( union_a W[x, a] P_a )
            ( union_{b,c} Q_b W[b, c] P_c )*
            ( union_f Q_f W[f, y] ) ].

If D, every P_x, and every Q_y have height at most one, and every
W[x, y] has height at most b >= 0, then W'[x, y] has height at most
max(2, b+1).

Proof. Soundness. A word accepted by the right side lies in D*, so
it has a unique factorization into episodes. A W-factor lies in
W[x, y](D'), hence consumes a sequence of D'-episodes, and the
prefix-code property forces this sequence to align with the
factorization. A P Q-pair, by (i), consumes exactly one further
episode and updates the state from a to b as announced. Alternating
the W-factors and the P Q pairs and finishing with the trailing
Q W, induction on the number of alternations gives the required
composite update from x to y. The initial alternative W[x, y]
already produces the required update when no gap episode occurs.

Completeness. Take a word in D* whose composite update sends x to
y. Every episode e outside D' is split using (ii) into a word of
P_a Q_b with b = G_e(a). The surrounding D'-episodes absorb into
W-factors. Interleaving these splits into the alternation gives
acceptance by the right side. If no gap episode occurs, the word
lies in W[x, y].

Height. The domain D* has height at most 2, since a single outer
star over the alternating language E covers any length of
concatenation of episodes. The union ( union_a W[x, a] P_a ) has
height at most max(1, b). The starred union over the middle has
height max(1, b) + 1. Intersecting with D* gives height at most
max(2, b+1). QED

Affine updates. A map G: U -> U on an F2-vector space U is affine
if G(u) = u L + c for a linear map L and a fixed c in U. The
composition of affine maps G_i(u) = u L_i + c_i satisfies
G_2(G_1(u)) = u L_1 L_2 + (c_1 L_2 + c_2), an affine update with
linear part L_1 L_2 and constant c_1 L_2 + c_2.

Lemma (affine recovery). Let U be a finite-dimensional F2-vector
space, D a subset of a prefix code E, and each G_e for e in D an
affine update of U. Suppose (R_{v, y}) for v, y in U are graph
languages for the affine composite w -> u L(w) + c(w) computed on
the word w in D*. Then the graph language of the linear part,
{v -> v L(w) = y}, equals

  union over f in U of ( R_{v, y + f} intersect R_{0, f} ).

Proof. For any w in D*, the affine composite sends v to
v L(w) + c(w) and 0 to c(w). The value v L(w) equals y exactly when
v L(w) + c(w) equals y + c(w) and 0 L(w) + c(w) equals c(w).
Choosing f = c(w) matches the displayed intersection. Conversely, a
pair (v, y + f) and (0, f) in the two graph languages with common w
forces v L(w) = y. QED

The recovery step uses only finite Boolean operations and therefore
does not increase height. The same observation applies to any finite
Boolean combination of graph languages on the same episode sequence.

Affine-line lemma. Let M be a finite monoid acting on a
finite-dimensional F2-vector space U by a right linear action rho.
There exist l >= 1 and a function beta: M^l -> U with the following
property. For every v in U and every tuple d = (d_1, ..., d_l) in
M^l, at least one index j in {1, ..., l} makes the map

  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.

Proof. Put qU = |U|. If m = |M| = 1 or qU = 1, take l = 1 and
beta = 0. Assume m, qU > 1 from here. Choose l later. Choose the
values of beta independently and uniformly in U.

For a state v and tuple d in M^l, let B[v, d] be the event that no
coordinate line through d has the stated constancy. Condition on the
value beta(d). Constancy along one coordinate line prescribes beta
at the other m - 1 points of that line, an event of probability
qU^{1-m}. Different coordinate lines through d have disjoint sets of
noncentral points, so those constancy events are conditionally
independent, and the conditional failure probability given beta(d)
does not depend on the value beta(d). Therefore

  Pr(B[v, d]) = p[l] := (1 - qU^{1-m})^l.

Each B[v, d] depends only on the random values at points of Hamming
distance at most one from d, so it is independent of the joint
family of events whose centers lie at distance greater than two from
d. The number of potentially dependent events, including one factor
of qU for every possible state at every neighboring center, is at
most

  D[l] := qU (1 + l m + l^2 m^2) - 1.

The symmetric Lovasz local lemma (Erdos and Lovasz, 1975) is
applied next.

./erdos-lovasz-1975.pdf

Suppose a finite
family of events has a dependency graph of maximum degree D and each
event has probability at most u (1 - u)^D for some 0 < u < 1. Then
the simultaneous non-occurrence of every event has positive
probability. The bound is proved by induction on the size of a
conditioning set. For a set S of k events the induction claims:
(a) every member of S fails simultaneously with positive
probability, and (b) the conditional probability of any event A
outside S, given the failure of every member of S, is at most u.
Partition S into the neighbors S_1 and the non-neighbors S_0 of A.
If S_1 is empty, joint independence from S_0 gives (b) without
correction. Otherwise

  Pr(A | every member of S fails)
    <= Pr(A | every member of S_0 fails) /
       Pr(every member of S_1 fails | every member of S_0 fails)
    <= Pr(A) / (1 - u)^{|S_1|}
    <= u.

The denominator is bounded below by revealing the members of S_1
one at a time and applying (b) at a set whose size is at most k - 1.
The numerator uses joint independence from S_0. Statement (a) for S
at size k follows by dropping one member of S and applying (b) at
size k - 1. This closes the induction.

Apply the lemma with D = D[l] and u = 1 / (2 D[l]). Bernoulli's
inequality gives

  u (1 - u)^{D[l]}
    = 1/(2 D[l]) (1 - 1/(2 D[l]))^{D[l]}
    >= 1/(4 D[l]).

The failure probability p[l] decays exponentially in l while D[l]
grows only like l^2 m^2 qU. Choose l large enough that
p[l] <= 1/(4 D[l]). The local-lemma hypothesis holds, so some beta
satisfies the conclusion of the lemma at every state and tuple. QED

To apply the lemma to a word segment, choose ordered checkpoints
B_0 < B_1 < ... < 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 transmits 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. The corrected segment
function is thereby computable at B_l for at least one interval.

Finite clock. The affine-line lemma requires the prefix and suffix to
share finite data. Such a collection is a tag. The next lemma builds
a finite clock controlling independent tag choices through two
length residues measured from scheduled reference positions. Its
relation permits either matching tags or a single specified
mismatch, which is later absorbed into an affine correction. A
second property bounds ambiguous pairs of candidate origins uniformly
in their common translation.

Lemma (finite clock). Let Lambda be a finite nonempty set, R a finite
set, and Q >= 1 an integer. Set F = 400 and C = 2^{|Lambda|}(1 + 4 F^2).
There exist a positive integer n, all of whose prime factors exceed Q,
sets I_alpha, J_alpha subset 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:

  (i) For every s in Z/n, the relation
    E(s) = {(alpha, lambda) in Lambda x Lambda : s in I_alpha + J_lambda}
    is either a subset of the diagonal or a singleton consisting of
    one off-diagonal pair. If s is not in W, it is the full diagonal.

  (ii) For every u in Z/n,
    #{ (p, p') in R x R : p != p', u + v_{p'} - v_p in W } <= C.

Proof. For each map chi: Lambda -> {L, R} reserve one first
coordinate and a batch of coordinates. Write r = |R|. Assign each
coordinate a distinct prime order q satisfying
q > max(Q, 400, 2^{r+1}). Euclid's argument supplies a prime beyond
any prescribed finite list. The batch contains a dedicated coordinate
for every ordered list ((p_a, p'_a))_{a=0}^{F-1} of ordered pairs of
distinct elements of R whose underlying unordered edges are distinct
and form a forest. A spare coordinate is added if needed so the batch
has positive odd size. Write G for the product of the coordinate
groups; G is finite.

Identify a coordinate of prime order q with the subgroup q^-1 Z/Z of
the circle T = R/Z. Let norm_T(x) denote circular distance from x to
zero; call a coordinate value small if norm_T(x) <= 1/100. Put
C_I = {0, 1, 3}/6 and C_J = {2, 4, 5}/6 in T.

For each tag alpha impose the following constraints in the chi block.
If chi(alpha) = L, the first coordinate of I_alpha is zero, that of
J_alpha is nonzero, and in every batch coordinate the I_alpha value
sits within 1/16 of C_I and the J_alpha value within 1/16 of C_J. If
chi(alpha) = R, the first coordinate of I_alpha is nonzero, that of
J_alpha is zero, and in a strict majority of batch coordinates both
I_alpha and J_alpha are small. The constraints over all blocks
define I_alpha and J_alpha in G. Let W be the union over chi of two
obstructions: the first coordinate is zero; or no batch coordinate
is small.

Sums and differences inside one batch. For a left tag and any target
t in T, choose c_I in C_I, c_J in C_J, and a displacement delta with
|delta| <= 1/12 so that t = c_I + c_J + delta in T. Round
c_I + delta/2 to a nearest grid point i and set j = t - i. Both are
grid points, their distances from c_I and c_J are at most
1/24 + 1/(2q) < 1/16 since q > 400, and c_I + c_J runs over all six
multiples of 1/6 as c_I, c_J vary. Any target t has a decomposition
t = i + j with i in I_alpha and j in J_alpha at every batch
coordinate. Consequently, every allowed left-tag difference i - j
obeys norm_T(i - j) >= 1/6 - 2/16 = 1/24 at every batch coordinate.

For a right tag, write the batch size as 2k + 1 and choose a small
target coordinate. At that coordinate assign the target to the first
summand and zero to the second. Partition the other 2k coordinates
into two sets of size k. On the first set put zero in the first
summand and the target in the second; on the second set the reverse.
Both summands have at least k + 1 small coordinates. Any two allowed
right-tag values therefore share a small coordinate, since their
small-coordinate sets are strict majorities. Their difference obeys
norm_T(i - j) <= 2/100 < 1/24 in that coordinate. So the difference
sets I_alpha - J_alpha and I_alpha' - J_alpha' are disjoint whenever
a block places alpha on the left and alpha' on the right.

Full relation. If s is not in W, every first coordinate of s is
nonzero and every batch has a small coordinate. The decompositions
t = 0 + t and t = t + 0 at the first coordinates, plus the batch
decompositions, give s in I_alpha + J_alpha for every tag alpha.
Choices in distinct blocks are independent and combine to give the
required element of G.

Suppose an off-diagonal pair (alpha, alpha') belongs to E(s). For a
competing pair (lambda, mu) with {lambda, mu} different from
{alpha, alpha'}, choose chi placing alpha on the left, alpha' on the
right, and both lambda and mu on the same side; this is possible
since identifying two distinct tags on one side does not identify
them on opposite sides. In that block, (alpha, alpha') forces the
first coordinate of s to be zero, whereas (lambda, mu) requires
nonzero. No such competitor belongs to E(s). The only remaining
possible competitor is (alpha', alpha). If both pairs represented s
there would be i_alpha + j_alpha' = i_alpha' + j_alpha, hence
i_alpha - j_alpha = i_alpha' - j_alpha'. A block that separates alpha
from alpha' contradicts the disjointness of the difference sets.
This proves (i).

Roster. Index R as p_0, ..., p_{r-1}. In every first coordinate set
v_{p_j} = 2^j. For a < b,
  2^b - 2^a = 2^a (2^{b-a} - 1).
The exact power of two dividing the integer difference determines a,
after which the odd factor determines b - a. Distinct ordered pairs
give distinct nonzero integers bounded in magnitude by 2^r < q, so
reduction modulo q is injective on ordered differences. For any
translate u at most one ordered pair (p, p') has
u + v_{p'} - v_p equal to zero in a fixed first coordinate.

For a dedicated batch coordinate of a list ((p_a, p'_a)), let z_a be
a grid point at circular distance at most 1/(2q) from a/F. Prescribe
(v_{p'_a} - v_{p_a}) at that coordinate to equal z_a. These
prescriptions are simultaneously satisfiable: choose a root value in
each tree, propagate along its edges, and assign arbitrary values to
remaining vertices and spare coordinates. Doing this in every
coordinate produces the desired elements v_p in G.

For a fixed translate t of the batch, one of the equally spaced
points a/F lies at distance at most 1/(2F) from -t, and the
corresponding prescribed difference satisfies
norm_T(t + z_a) <= 1/(2F) + 1/(2q) < 1/400 < 1/100. So each dedicated
list has a pair whose translated difference is small in its dedicated
coordinate, uniformly in the translate.

Whole-batch bound. Fix u in G and a batch. An ordered pair (p, p')
with p != p' is bad for the batch if u + v_{p'} - v_p has no small
coordinate in the batch. If more than 4 F^2 bad pairs existed, form
the simple undirected graph of their underlying unordered pairs,
discarding isolated vertices. If a spanning forest had at most F - 1
edges, its nontrivial components would span at most 2F - 2 vertices,
since a component with h >= 2 vertices contributes h - 1 edges and
h <= 2(h - 1), producing at most (2F - 2)(2F - 3) < 4 F^2 ordered
pairs, contradiction. Select F edges of the spanning forest and
orient each as one of the bad pairs. These F edges form a dedicated
list, and the covering estimate makes one of the pairs small in its
dedicated coordinate, contradiction. Each batch has at most 4 F^2
bad ordered pairs, and the same counting applies when the roster is
too small to admit a dedicated list.

Counting. Every ordered pair (p, p') in W for some translate u has
either its translated difference in a first-coordinate obstruction or
its translated difference with no small coordinate in some batch. The
first-coordinate construction contributes at most one ordered pair per
chi block, and each of the 2^{|Lambda|} blocks contributes at most
1 + 4 F^2. Combining,
  #{ (p, p') : p != p', u + v_{p'} - v_p in W }
    <= 2^{|Lambda|} (1 + 4 F^2)
for every u in G. This gives (ii).

One cyclic clock. Let n be the product of all coordinate primes. The
residue map from Z/n to G is injective since the coordinate primes are
pairwise coprime, and both groups have n elements, so the map is an
isomorphism. Transport all constructed sets through the inverse. Sums,
differences, and both properties (i) and (ii) are preserved, and every
prime factor of n exceeds Q. QED

Polynomial roster. A different roster uses the polynomial-evaluation
scheme underlying Reed-Solomon codes. Fix a prime P, a positive
integer k_0, and distinct points xi_1, ..., xi_R in F_P. A roster slot
p is a polynomial over F_P of degree less than k_0, including the zero
polynomial; its digit at scale r is p(xi_r). A nonzero polynomial of
degree less than k_0 has at most k_0 - 1 roots, so any k_0 evaluations
determine the slot and two distinct slots agree in at most k_0 - 1
digits. The finite-clock lemma accepts any roster, so this polynomial
roster serves whenever many residues are required. Only the
elementary root bound over the prime field is used; the coding theory
that follows from the Reed-Solomon construction plays no role.

./reed-solomon-1960.pdf

Local markers. The marker-versus-local-periodicity principle appears
in Krieger's analysis of subsystems of topological Markov chains,
with a finite clopen merging formulation in Meyerovitch.

./krieger1982.pdf
./meyerovitch-2025.pdf

Lemma (local markers). Let d >= 2 and K > 3 d^2 be integers. There is
a translation-equivariant rule that marks integer positions of any
two-sided word such that:

  (i) distinct markers are at distance at least d;

  (ii) the decision at z uses only [z - r, z + r) for a fixed finite
  integer r >= K;

  (iii) if there is no marker in [z - d, z + d], then the length-K
  block starting at z has a positive period less than d.

Proof. List the finitely many length-K words having no positive
period below d. Process them in a fixed order. When processing one of
these words, mark all of its starts not within distance < d of an
earlier marker. Two starts added at the same step cannot be at
distance a < d, since their overlap would make a a period of the
listed word, a contradiction. This gives (i) by induction. Each step
uses a length-K block and the decisions of earlier steps at offsets
of magnitude < d; induction over the finite list integrates these
into a finite inspection radius, enlarged to at least K. The
construction commutes with translations, giving (ii). A listed word
at z was either marked or was prevented from being marked by a
marker at distance < d. Marker absence in [z - d, z + d] therefore
excludes every listed word at z, giving (iii). QED

Periodic extension. In marker-free regions the boundary rule preserves
a congruence class modulo a full monoid period; preserving only a
phase modulo the period is not enough.

Lemma (periodic extension). A block of length K > 3 d^2 having a
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 there is no marker
in [z - H, z + H] with H >= d, then the actual letters on
[z - H + d, z + H - d + K) agree with that extension.

Proof. A length-K block with a period p < d forces a unique letter at
every integer congruent modulo p to a position inside the block, and
the period hypothesis is preserved by translations. Two blocks with
overlapping periodic runs that share at least K - d^2 letters must
agree on their common overlap, because the offset between the two
starts is itself a period of the overlap, forcing the least periods
to coincide. QED

Scale choices. Let N be a common multiple of |M| and of every
eventual period of every element of M. Call a positive integer
smooth if all of its prime divisors divide N. Choose thresholds
S_r < S'_r, a positive
step delta_r, a movement bound R_r = n delta_r, and digit positions
f_r(0) < f_r(1) < ... < f_r(P - 1) at each scale, in increasing order
of r. For each r:

  (i) choose S_r >= 1 with S_r >= S'_{r-1} if r > 1; choose delta_r
  smooth and divisible by N sigma for every smooth positive integer
  sigma <= S_r, so that gcd(delta_r, n) = 1;

  (ii) put J_r = n + sum_{b < r} h'_b; choose the digit positions so
  all ordered differences of unequal digits are distinct and
  separated from one another and from zero by more than
  10 (J_r + R_r + 1); write h'_r for their diameter;

  (iii) choose S'_r > max(S_r, 10 (h'_r + J_r + R_r + 1)).

Assign slot p the numerical offset
  sum_{r=1}^{R_s} f_r(x_r(p)) + eps_p,  0 <= eps_p < n,
with eps_p chosen so the offset is congruent to v_p modulo n. For two
slots whose highest differing digit is at scale r, the sum of all
smaller-coordinate differences plus the correction difference has
absolute value less than J_r, while the difference at scale r exceeds
10 (J_r + R_r + 1). The positions are distinct and the offsets of the
resulting stencil P_0 are separated by more than 2.

Inner controls. The inner boundary rule needs marker parameters
dwarfing every scale and every monoid period. Choose integers

  d_o > 10 (1 + n + sum_r h'_r + sum_r R_r),
  K_o > 3 d_o^2,

and fix the marking rule of the local-markers lemma with d = d_o,
K = K_o, and radius r_o >= K_o. Choose an integer

  H > 10 ((N + m + 1) d_o + (max_r R_r) + 1).

For an inner center z let u(z) be the first marker in [z - H, z + H],
or bottom when none exists. When u(z) is not bottom, put B(z) = u(z).

When u(z) is bottom, the periodic-extension lemma supplies a
periodic extension of the block starting at z. Let d < d_o be its
least period and sigma the largest smooth divisor of d. Among the
length-d period words at the different phases choose the
lexicographically least. Their starts form a single class x modulo d,
since equality of two rotations contradicts minimality of d. Let y(z)
be the largest integer at most z in x + sigma Z, and let B(z) be the
least integer at least z satisfying

  B(z) = x        (mod d),
  B(z) = y(z)     (mod sigma N).

The definition does not depend on the representative of x. Since
gcd(d, sigma N) = sigma and d / sigma is coprime to N, the two
residues agree modulo sigma and together define one class modulo
d N. In particular z <= B(z) < z + d N. All the choices commute with
translations of the letters and do not use an external choice of
position origin. In both the present and absent cases, B(z) lies in
[z - H, z + H].

Center spacing. Choose an even integer

  G > 10 (H + r_o + (max_r R_r) + 1).

For the main segment set

  o_j = (j + 1) G,
  z_j = t + o_j,  B_j = B(z_j),  (0 <= j <= l),
  c_j = (o_{j-1} + o_j) / 2,  (1 <= j <= l).

At another proposed origin tau, write z_j(tau) = tau + o_j and
B_j(tau) = B(z_j(tau)). The notation without an argument refers to
the true origin t. The main cut offsets from t form the finite set

  H_cut = { c_j + delta_r a :
            1 <= j <= l, 1 <= r <= R_s, 0 <= a < n }.

A cut of role (j, r) lies strictly between B_{j-1} and B_j, and every
inspection window for boundaries through j-1 is before this cut.
Conversely, for a suffix beginning at k and any hypothesized role
(j, r), a candidate origin k - c_j - delta_r a has its first required
center at k + G/2 - delta_r a. Since delta_r a < R_r, the center
spacing puts the inspections for this center and all later centers
after k.

Usability. Call scale r usable at origin t if, at each of its Z
centers z_j,

  (i) u(z_j + h) = u(z_j) for every integer h with |h| <= R_r,
  including agreement on absence;

  (ii) if u(z_j) = bottom, then either sigma <= S_r, or the inclusive
  interval [z_j - R_r, z_j + R_r] contains no point of x + sigma Z.

In this definition d, sigma, x refer to the periodic extension at the indicated
center. All windows needed by these checks are mandatory.

Lemma (transport of boundary products). Suppose scale r is usable at
origin t and h is a multiple of delta_r with |h| <= R_r. Write
B_j^{(h)} = B(z_j + h). Then

  T[B_{j-1}, B_j] = T[B_{j-1}^{(h)}, B_j^{(h)}]   (1 <= j <= l).

For a fixed endpoint b >= z_l + H, the trailing transfer also gives

  T[B_l, b] = T[B_l^{(h)}, b].

Both statements apply to finite words whenever the prescribed windows
and product intervals are available. They hold for arbitrary finite
monoids, without a commutativity assumption.

Proof. Three steps: the two boundaries at each center lie in one
class modulo d N; the periodic run around each boundary is long
enough; and monoid-power periodicity turns the shift into an identity
on the level of ordered products.

A common boundary class. Consider one center z. Usability (i) keeps
the marker status unchanged. If both boundaries are absent, the old
and new periodic blocks determine the same two-sided extension, since
|h| <= R_r < d_o and the blocks have length K_o > 3 d_o^2. Thus the
least period d, the smooth divisor sigma, and the phase class x
modulo d are common to both. Both boundaries satisfy
B = x mod d and B = y mod sigma N, with y the largest point at most
the shifted center in x + sigma Z. The largest-at-most clause changes
y by exactly h, which is a multiple of delta_r and hence of sigma.
Since gcd(d, sigma N) = sigma and d / sigma is coprime to N, the two
congruences combine to B(z + h) = B(z) modulo d N. In the remaining
case of usability (ii), when sigma > S_r, the interval
[z - R_r, z + R_r] contains no point of the lattice x + sigma Z and
the boundary does not move at all. In either case,

  B(z + h) - B(z) = q d N  with |q| d N <= 2 H + R_r.

Long periodic runs. Fix a center z with u(z) = bottom. The
periodic-extension lemma and the marker-free window imply that the
actual word is d-periodic on the length (K_o - d_o) window beginning
at z + H - d_o. Because both B(z) and z lie in [z - H, z + H], the
boundary B(z) sits strictly inside this run. The same applies at the
shifted center z + h. Together, the two runs cover the region of
radius 2 H + R_r used by the transport identity.

Monoid-power periodicity. Let m be the length-d period word treated
as an element of M. Its powers satisfy m^k = m^(k + N) once
k >= N^2, by pigeonhole on the finitely many values m^0, m^1, ....
Since N is a multiple of the eventual period of m by construction,
the element m^(q N) is independent of q >= 1. Because delta_r is a
multiple of N sigma, the shift h is a multiple of N, and by the
common-class calculation the boundary difference is q d N, a multiple
of d N. A segment of length q d N has the product m^(q N), so two
such segments have equal ordered products. This gives

  T[B_{j-1}, B_j] = T[B_{j-1} + q_{j-1} d N, B_j + q_j d N]
                  = T[B_{j-1}^{(h)}, B_j^{(h)}].

The left identity shifts both endpoints by the common amount
q_{j-1} d N. The right follows by moving the right endpoint from
B_j + q_{j-1} d N to B_j + q_j d N in steps of d N: each step
contributes the monoid element m^(q N), the same for every q >= 1,
so the contributions telescope out of the product. The trailing
transfer uses the periodic extension at z_l on the right and the same
argument, giving T[B_l, b] = T[B_l^{(h)}, b] for any fixed
b >= z_l + H. No step uses commutativity. QED

Proposition (inner ambiguity). For every stage-0 tag alpha and every
u in Z/n,

  #{(p, p') in R_0^2 : p != p', u + v_{p'} - v_p in W and some
     gamma in Delta_0 has A_1(t + p - p' + gamma)} <= C_0,

where Delta_0 = P_0 - P_0, A_1 is the finite predicate on offsets
whose checks lie before the main cut, and
C_0 = C + 2^{R_s} (3 Z + 1)^{R_s} P^{2 Z}.

Proof. Let D denote the displayed set, and fix a stage-0 tag alpha,
its roster offset p_alpha, and a translate u. By the clock, the pairs
in D lie in at most 2^{R_s} (1 + 4 F^2) W-classes. If for some class
the number of pairs exceeds M_1 = P^{k_0} / (2^{R_s} (1 + 4 F^2)),
then two pairs in that class share all of their first k_0
evaluations. The underlying polynomials agree on k_0 distinct field
elements; because a nonzero polynomial of degree less than k_0 has at
most k_0 - 1 roots, the two slots have the same polynomial, hence
coincide, contradicting p != p'. Every W-class therefore contributes
at most M_1 pairs.

Fix one W-class. Its pairs are indexed by gamma offsets in Delta_0.
For each gamma, the predicate A_1 makes at most 3 choices at each of
the Z centers and at most P^{2 Z} distinct first-coordinate
witnesses across the R_s scales. Summing the Z-center choices over
the R_s scales gives the finite bound (3 Z + 1)^{R_s} P^{2 Z} on the
number of gamma surviving A_1 at one translate. Multiplying,

  |D| <= 2^{R_s} (1 + 4 F^2) (3 Z + 1)^{R_s} P^{2 Z} <= C_0.

QED

The concrete roster. Set

  Z = l + 1,  k_0 = 2 Z + 1,  R_s = 2 k_0 - 1.

There are Z centers for the boundaries and R_s scales for each cut
role. The tag set is

  alpha = (j, r, v, d_1, ..., d_{j-1}, X, Y),
  1 <= j <= l, 1 <= r <= R_s, v, X, Y in V, d_f in M.

Its ambiguity constant C depends only on the tag set, before any
roster or position is chosen.

Let kappa_0 be the number of stage-0 buffer kinds. Choose a prime
P > R_s large enough that

  floor(P^{k_0} / kappa_0) > C_0,
  C_0 = C + 2^{R_s} (3 Z + 1)^{R_s} P^{2 Z}.

Such a prime exists because k_0 = 2 Z + 1 > 2 Z. Roster slots are the
polynomials of degree less than k_0 over F_P, including the zero
polynomial. Choose distinct xi_1, ..., xi_{R_s} in F_P and give slot p
the digits

  x_r(p) = p(xi_r).

A nonzero polynomial of degree less than k_0 has at most k_0 - 1
roots, so any k_0 of the evaluations determine the slot, and two
distinct slots differ in at least R_s - k_0 + 1 = k_0 digits. Apply
the finite-clock lemma to this roster, avoiding every prime at most
N. Fix the resulting modulus n, tag sets I_alpha, J_alpha, bad set
W, and roster residues v_p in Z/n. Every prime divisor of n exceeds N
by construction, and enlarging the modulus does not change C_0.

End system. An episode ends at a deterministic anchor. The end
system consists of four parts.

  (i) A second instance of the local-markers lemma, called the end
  markers, with parameters d_e > 2 (h_e + w) + 1 and K_e > 3 d_e^2
  and radius r_e >= K_e.

  (ii) At each proposed origin, a seed block of length K_e placed at
  a fixed offset o_e.

  (iii) An anchor rule that maps an integer t to an integer q or to
  bottom.

  (iv) A fixed positive integer b_tail larger than the extent of the
  end windows.

Define eta(t) as the first end marker in [t - H_e, t + H_e], or
bottom when none exists. The definition is translation-equivariant.
Let z_e(t) = t + o_e. When eta(t) = bottom, the periodic-extension
lemma applied to the block at z_e(t) of length K_e yields a two-sided
periodic extension with least period d < d_e. Compare the extension
to the actual letters and let q be the first mismatch position, if
any. Otherwise q is undefined and the episode is incomplete. When q
is defined, the episode beginning at s with true origin t = s + L
ends at q + b_tail.

Placement. The four envelopes are chosen in acyclic order.

  (A) Fix the buffer offsets from s and place buffer 1, including
  a_1, before buffer 0.

  (B) Choose L large enough that the inner envelope, containing the
  inner windows of the buffer cuts, sits after all buffer data.

  (C) Choose o_e large enough that the end envelope, containing the
  end markers, the seed block, and the end windows, sits after the
  inner envelope.

  (D) Choose b_tail large enough that the fixed tail follows the end
  envelope.

Each step only enlarges a translation. All the data of the episode is
therefore determined by the local letters around the cut and end
windows.

Lemma (placement). 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 every relevant
  inner-system window and cut, then every relevant end-system window
  and seed.

  (ii) Every bounded window required at main hypotheses or at aligned
  buffer hypotheses is 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.

Proof. The four envelopes are chosen in order (A)-(D); each step
enlarges a translation by a finite amount and preserves the previous
order. QED

Lemma (end ambiguity). Let Delta_0 = P_0 - P_0 be the set of ordered
origin differences allowed at stage 0. Then, uniformly in t,

  #{(p, p') in P_1^2 : p != p',
     some gamma in Delta_0 has A_1(t + p - p' + gamma)} <= 2 |Delta_0|,

where A_1 is the finite predicate that the end marker eta agrees
across every candidate window at the resulting true-origin shift.

Proof. Fix gamma in Delta_0 and one endpoint of the search window
[t - H_e, t + H_e]. As p - p' ranges over Delta_0 + Delta_1, the
candidate marker positions lie in a bounded interval of diameter at
most 2 h_1 + 2 w < d_e, which contains at most one end marker by the
separation of markers at distance d_e. That marker pins p - p' to an
interval of length 2 w <= d_e/2 - 1, so at most one nonzero ordered
pair survives at that endpoint. Two endpoints and |Delta_0| choices
of gamma give 2 |Delta_0| pairs. QED

End guard. A suffix with candidate list {k - h : h in H} forms its
end guard by requiring eta to agree across every candidate in the
list and by applying the exact-end test (anchor rule plus endpoint
q + b_tail) at one fixed reference candidate.

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 strictly
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. The
conclusion holds even if the proposed suffix initially ends before e
or extends past e.

Proof. On the true episode every candidate window is present and the
true anchor q is among the candidates. A premature suffix lacks at
least one such window, and the exact-end test at the reference
candidate fails because the endpoint q + b_tail lies beyond the
suffix argument. An excessive suffix, ending past q + b_tail, has the
true anchor q available as a mandatory endpoint; the exact-end test
requires the last consumed position to be q + b_tail and therefore
fails. Every window belonging to a candidate list is mandatory: a
test never removes an unavailable candidate and then checks
uniqueness among those remaining. Under this convention the placement
lemma supplies the windows on every correct use, and the preceding
two paragraphs cover the incorrect ones. QED

Affine lifts. The recovery chain embeds each update into a larger
linear update that mirrors it on a distinguished basis and then
surfaces the original by Lemma (affine recovery). Recall U_0 = V and
U_{i+1} = F2^(U_i x M) for i = 0, 1, with basis elements written
[v, c], v in U_i and c in M.

Every g_{i,e} for e in D_i is linear. Base case: for e in D_0 the
action on V is g_0(e)(x) = x T_e, linear over F2 since v -> v T_e is
linear. Inductive step: the lift g_{i+1,e} below is defined linearly
from g_{i,e}, so linearity passes to i + 1. No g_{i,e} carries a
nonzero affine constant, and the affine corrections from the
affine-line lemma enter only inside the buffer computations that feed
the graph languages of the split.

Define the linear map M_{i+1,e}: U_{i+1} -> U_{i+1} on basis
elements by

  M_{i+1,e}([v, 1_M]) = [g_{i,e}(v), 1_M]   for all v in U_i,
  M_{i+1,e}([v, c])   = [v A_{i,e}, c d_e]   for c != 1_M,

where g_{i,e}(v) = v A_{i,e} is the linear decomposition of g_{i,e}
and d_e in M is a fixed element depending on e. The assignment
v -> [g_{i,e}(v), 1_M] is linear in v because g_{i,e} is linear, so
the two cases define M_{i+1,e} on a generating set and extend
uniquely to a linear map on U_{i+1}. Set g_{i+1,e} = M_{i+1,e}.

Lemma (lift update). For i in {0, 1}, e in D_i, and v in U_i,

  g_{i+1,e}([v, 1_M]) = [g_{i,e}(v), 1_M].

Consequently for any sequence e_1 ... e_k in D_i*, the composite
g_{i+1,e_1} ... g_{i+1,e_k} sends [v, 1_M] to
[g_{i,e_k}(... g_{i,e_1}(v) ...), 1_M].

Proof. The first statement is the defining prescription of g_{i+1,e}
on the distinguished slice. For the composite, induct on k: for k = 0
the empty sequence gives the identity; for k >= 1, apply the induction
hypothesis to e_1 ... e_{k-1} to reach
[g_{i,e_{k-1}}(... g_{i,e_1}(v) ...), 1_M], then apply the identity at
e_k. QED

Lemma (sequence lift). For any D subset of D_i and any i in {0, 1},
graph languages for g_{i+1} on D* yield graph languages for g_i on
D* by finite Boolean operations. The height does not increase.

Proof. For w = e_1 ... e_k in D*, the composite g_{i+1,w} is linear
and by lift-update g_{i+1,w}([v, 1_M]) = [g_{i,w}(v), 1_M]. The
graph language W_{g_i}[x, y](D*) therefore equals the graph language
of g_{i+1} restricted to the distinguished slice,
W_{g_{i+1}}[[x, 1_M], [y, 1_M]](D*). The restriction uses only finite
Boolean operations, so the height of W_{g_i} on D* is at most that of
W_{g_{i+1}} on D*. QED

Splits. The semantic construction breaks each episode into a prefix
and a suffix at a specified cut and glues the pieces back by the split
lemma. Three split applications are needed:

  Split      Update tested   Episode class   Skipped class
  ---------  -------------   -------------   -------------
  main       g_0             E               D_0
  stage 0    g_1             D_0             D_1
  stage 1    g_2             D_1             D_2 = empty

They are invoked in reverse order: stage 1, then stage 0, then main.
Every episode update g_i is fixed on the entire episode before any
split is selected.

Two orders of composition coexist. Along the word, buffer 1 precedes
buffer 0, then the main segment, then the end segment. The total
update tables are defined in the order g_0, g_1, g_2. The graph tests
for g_i use the buffer system, the inner system, and the end system
in that order, and each uses only the data from its own prefix and
suffix sides of the cut.

Decoding predicates. For e in E with true origin t and anchor q, let
A_0(t, q) and A_1(t) be finite predicates:

  A_0(t, q) holds iff, at the true candidate p_alpha, the prefix and
  suffix together pass the uniqueness test at every cut role (j, r)
  in the finite offset set H_cut.

  A_1(t) holds iff the end guard for eta succeeds at every shift of
  the origin t + gamma with gamma in Delta_0.

Set D_0 = {e in E : A_0(t, q) or A_1(t)}.

For e in D_0, let B_0(t, q) and B_1(t) be the analogous predicates
after the stage-0 corrections have been applied. Set
D_1 = {e in D_0 : B_0(t, q) or B_1(t)}.

Finally D_2 = the empty set. Every complete episode of E or D_0 or D_1
belongs to exactly one of these predicates at its true origin, since
the tests are computed by bounded inspection of the letters around t
and q.

Main split. Let P_x^main and Q_y^main be the split prefix and suffix
at the main cut. They satisfy the two hypotheses of the split lemma
for g_0, with D = E and D' = D_0.

Soundness. Suppose a prefix u of a word in E* factors as
P_x^main Q_y^main. The prefix length is positive and its cut lies
strictly inside the first episode, so there is a first episode e with
true origin t and anchor q. The clock's property (i) then gives
either alpha = lambda on the diagonal (one tag on both sides of the
cut) or one off-diagonal pair (alpha, lambda). Line constancy from
the affine-line lemma gives the buffer-corrected affine composite at
B_l, and Lemma (affine recovery) strips the added correction to
expose exactly the linear part g_0(e)(x) = x T_e.

Completeness. Fix e notin D_0 and x in V. Then A_0 fails and A_1
fails at every shift by Delta_0. The inner ambiguity proposition
supplies at least one usable scale r; the affine-line lemma supplies
an interval j at that scale; the clock gives a tag; the coprimality
gcd(delta_r, n) = 1 allows a residue a such that both clock tests
succeed on the prefix and suffix sides. The split returns
g_0(e)(x) = y.

Stage 0 split. Let P_x^{(0)} and Q_y^{(0)} be the split prefix and
suffix at the stage-0 cut, taken inside the buffer 0 segment of the
episode with the buffer 1 segment preceding. They satisfy the two
hypotheses of the split lemma for g_1, with D = D_0 and D' = D_1.

Soundness and completeness follow the same pattern, using the clock
with the stage-0 predicate. Because g_1 is defined to encode g_0
through the lift, the same affine-recovery step extracts g_1(e)(x)
from the graph language on U_1.

Stage 1 split. Let P_x^{(1)} and Q_y^{(1)} be the split prefix and
suffix at the stage-1 cut, taken inside the buffer 1 segment. They
satisfy the two hypotheses of the split lemma for g_2, with D = D_1
and D' = D_2 = empty.

Since D_2 is empty, the split hypotheses are vacuous for the skipped
class: every episode of D_1 already lies in D_1, which is the episode
class itself. Completeness reduces to the triviality W[x,y](empty) =
{eps} when x = y and empty otherwise. The height acquisition at this
bottom step comes from the trivial language {eps}, which has star
height 0.

Template lemma. Each split prefix language P_x^{(i)} and each split
suffix Q_y^{(i)}, read as a language over Sigma, is accepted by a
deterministic test that uses only the following finite data: letters
in bounded windows at fixed offsets from the cut, the exact order of
endpoints, M-products across intervals between them, and length
residues modulo fixed n. Such a language is a finite union of
templates a b^h c with fixed words a, b, c (b nonempty) and h >= 0.

Consequently each P_x^{(i)} and Q_y^{(i)} has generalized star height
at most 1.

Proof. Fix all of the finite data. For each fixed pattern of
endpoints, the test reads a two-sided word whose only nonlocal
quantity is the length of the period between two consecutive
endpoints. The M-product across a run of b's raised to the h-th
power depends on h only through the eventual periodic behavior of
the finite monoid M, so after the preperiod the test is invariant
under increasing h by the period. The accepted language, restricted
to this fixed endpoint pattern and this fixed test residue, is
therefore a finite union of templates a b^h c with h ranging over one
arithmetic progression. Since only finitely many endpoint patterns
and test residues occur, the language is a finite union of such
templates. The language {a b^h c : h >= 0} equals {a} {b}* {c} at
height 1; finite unions, intersections, and concatenations of height
1 languages remain at height 1. QED

Recovery chain. The height bookkeeping follows the split order in
reverse: stage 1, then stage 0, then main.

Stage 1. The split prefix P_x^{(1)} and suffix Q_y^{(1)} have height
at most 1. The skipped class D_2 is empty, so W[x, y](D_2) has
height 0. The split lemma applied to the episode class D_1, testing
update g_2, therefore gives graph languages for g_2 on D_1 of height
at most max(2, 0 + 1) = 2.

Sequence lift. Lemma (sequence lift) at i = 1 transforms graph
languages for g_2 on D_1 into graph languages for g_1 on D_1 of the
same height 2.

Stage 0. The split prefix P_x^{(0)} and suffix Q_y^{(0)} have height
at most 1. The skipped class D_1 has graph languages for g_1 on D_1
of height 2. The split lemma applied to the episode class D_0,
testing update g_1, gives graph languages for g_1 on D_0 of height
at most max(2, 2 + 1) = 3.

Sequence lift. Lemma (sequence lift) at i = 0 transforms graph
languages for g_1 on D_0 into graph languages for g_0 on D_0 of the
same height 3.

Main. The split prefix P_x^main and suffix Q_y^main have height at
most 1. The skipped class D_0 has graph languages for g_0 on D_0 of
height 3. The split lemma applied to the episode class E, testing
update g_0, gives graph languages for g_0 on E of height at most
max(2, 3 + 1) = 4.

Now g_0(e)(x) = x T_e is the monoid action on V = F2^M. Take
x = 1_M and y = e_m; the graph language W[1_M, e_m](E) equals
{w in E* : T(w) = m}. Its height is at most 4.

Final theorem. Every regular language over a finite alphabet has
generalized star height at most 4.

Proof. Fix a regular language L over Sigma and let M be its
syntactic monoid, finite. Let T: Sigma* -> M be the syntactic
morphism. Choose L_0 = |M| + 1 and let E = Sigma^{L_0} be the prefix
code of all words of length L_0 over Sigma.

Every word w in Sigma* factors uniquely as w = e_1 e_2 ... e_k r with
e_a in E, k >= 0, and r in Remainders, where Remainders is the finite
set of words of length less than L_0. Uniqueness follows from the
prefix-code property of E. Apply the recovery chain to E: for every
m in M, the graph language U_m = {w in E* : T(w) = m} has star
height at most 4.

For w = e_1 ... e_k r, the syntactic value is
T(w) = T(e_1) ... T(e_k) T(r) = T(e_1 ... e_k) T(r). Therefore
w belongs to L exactly when T(e_1 ... e_k) T(r) in T(L), i.e.,
T(e_1 ... e_k) in T(L) T(r)^{-1}. This gives

  L = union over r in Remainders of
      union over m in T(L) of U_{m T(r)^{-1}} {r}.

Each set on the right is a graph language of height at most 4
concatenated with the single word r, whose language {r} has star
height 0. Finite unions and concatenations by height 0 languages
preserve the height bound. Therefore L has generalized star height at
most 4.

Kleene's theorem (1951) ensures that every regular language over
Sigma is described by some regular expression; the construction above
produces such an expression, and it has star height at most 4. This
completes the proof.

A complementary question, whether star height 1 always suffices,
remains open. The proofs in the papers cited above for nilpotent
class-two groups, and the analogues of the height-four construction
for a uniform bound, leave the sharp threshold at 4 unresolved.