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.