Generalized star height: three nested repetitions for every regular language

← All digests

Family 134 · Theoretical computer science
Importance 4/5 · Provisional editorial rating
Sources consulted 2026-10-09

1. The question

Regular expressions describe patterns by combining alternatives, concatenation, and repetition. The Kleene star turns a language $L$ into all finite concatenations of words from $L$, including the empty concatenation. Nesting stars seems to permit increasingly complicated patterns of repeated repetition.

How much nesting is actually necessary if expressions may also use complement—accepting exactly the words that another expression rejects?

This is the generalized star-height problem. Complement can replace some repetitive structure with a Boolean condition, so lower bounds for ordinary regular expressions do not automatically apply. The question is about the expressive depth needed to describe a language, with no limit on how long the final expression may become.

This family contains three constructions claiming absolute upper bounds of thirteen, four, and three. The strongest says that every regular language over every finite alphabet has generalized star height at most three, using that same alphabet. It does not settle whether height one always suffices, and it does not provide a language that requires height two or three.

2. Background and essential definitions

Fix a finite alphabet $\Sigma$, and let $\Sigma^*$ be the set of all finite words over it. A language is any subset of $\Sigma^*$. It is regular if a deterministic finite automaton recognizes it.

Generalized expressions begin with the empty language $0$, the singleton empty-word language $1$, and individual letters. Their operations are union, concatenation, complement relative to $\Sigma^*$, and star. If $P,Q$ are expressions, their heights satisfy

$$\begin{aligned} \operatorname{ht}(P\cup Q)&=\operatorname{ht}(PQ) =\max\{\operatorname{ht}(P),\operatorname{ht}(Q)\},\\ \operatorname{ht}(\neg P)&=\operatorname{ht}(P),\\ \operatorname{ht}(P^*)&=\operatorname{ht}(P)+1. \end{aligned}$$

The basic constants and letters have height zero. The generalized star height $h_\Sigma(L)$ is the minimum height among expressions defining $L$, not the height of one arbitrarily chosen expression.

Height-zero languages are called star-free, but they need not be finite. For example, all words are described by $\neg0$, which has height zero even though the usual notation $\Sigma^*$ contains a star. Conversely, over the one-letter alphabet $\{a\}$, the language $(aa)^*$ of even lengths requires height one: star-free unary languages are finite or cofinite, while the even-length language is neither.

A finite monoid is a finite set with an associative multiplication and an identity. Each word induces a transformation of an automaton’s states; these transformations form a monoid. Reading concatenated words corresponds to multiplying their transformations. Thus recognizing a regular language can be reduced to testing the product of its letters in a finite monoid.

3. Development history and previous partial results

Eggan related ordinary star height to the cycle structure of transition graphs. Dejean and Schützenberger established unbounded ordinary star height already over a two-letter alphabet. Their 1966 result concerns expressions without complement, which is why it does not settle the generalized problem.

Schützenberger’s 1965 theorem characterized star-free languages through finite aperiodic monoids. Aperiodicity means that powers of every element eventually stabilize: for each $m$, some $r$ satisfies $m^r=m^{r+1}$. This algebraic viewpoint connects iteration depth with the structure of finite computations.

Height-one theorems cover broader classes. Henneman obtained such a bound for finite abelian groups. Pin, Straubing, and Thérien extended it to finite nilpotent groups of class two and other recognizing structures; their primary account also develops closure properties relevant to the alphabet issue.

Counting languages supply further partial results. Bourne and Ruškuc treated words in which a fixed short factor occurs a prescribed number of times modulo an integer, counting overlapping occurrences. Bourne later extended this to arbitrary fixed factors in his thesis. These are nontrivial uses of repetition and counting, but they concern specified classes rather than every regular language.

Two unresolved formulations must be separated. One asks whether some universal finite bound exists; the stronger asks whether that bound can always be one. Straubing explicitly distinguishes them in his logical account. The new family claims uniform boundedness, while leaving the height-one question open.

4. What the new manuscripts claim

For every finite alphabet $\Sigma$ and every regular language $L\subseteq\Sigma^*$, M3 states

$$h_\Sigma(L)\le3.$$

M1 gives the bound thirteen through prediction trials and full decision histories. M2 gives four through multiscale movement of boundaries in periodic words. M3 gives three through shift tables and a decoder controlling all candidate cuts. Each manuscript presents its own construction; the stronger numerical statement is not used as a premise to prove the weaker ones.

The bound is independent of the alphabet size, the language, and the number of states in a recognizing automaton. Finite parameters and expression lengths may nevertheless depend enormously on the language. The papers make no useful complexity or size guarantee for constructing the resulting expression.

The expressions use the original letters of $\Sigma$. Auxiliary states, tags, and clock residues index finite collections of tests; they do not become new input symbols. Complement is always taken inside the same $\Sigma^*$.

That convention prevents a misleading shortcut. Some low-height representations work by mapping words into a different alphabet and taking an inverse image. Known height-preservation statements have restrictions on the allowed morphism. The existence of an arbitrary coding does not itself prove a low-height expression over the original alphabet.

The family supplies upper bounds only. It neither proves that three is necessary for some language nor decides the minimum generalized star height of a given language. The possibility of a universal bound of one remains compatible with all three theorems.

5. Why the advance matters

Provisional importance: 4/5. A uniform finite bound would substantially clarify the expressive structure of all regular languages when Boolean operations are available. It says that arbitrarily complicated finite-state behavior need not force arbitrarily deep nested repetition in this expression model.

The contrast with ordinary star height is mathematically significant. Adding complement changes the hierarchy enough that unbounded nesting without complement can coexist with a universal constant bound in the generalized setting.

The three constructions also expose a common principle: finite computations can be expressed through a bounded number of independently checked splits, while potentially enormous finite bookkeeping is absorbed into Boolean combinations. This explains why a depth theorem need not be a succinctness theorem.

The score reflects a broad structural result in formal-language theory. It does not suggest that regular expressions used in software will automatically become shorter, faster to match, or easier to read after applying the construction. Expression length and evaluation efficiency are separate resources.

6. The main idea

Turn a word into a sequence of finite updates

Fix a finite monoid recognizing the language. The construction parses a word into nonempty pieces called episodes and one final remainder. Episodes form a prefix code: no episode is a proper prefix of another. Consequently, an episode sequence has a unique parsing.

Each episode acts on a finite state space. A graph language records that the composed action of a sequence sends state $x$ to state $y$. The goal is to describe these graph languages with bounded star height, then select the accepting final states.

The basic operation splits an episode into a prefix test and a suffix test. The prefix checks an incoming state; the suffix checks an outgoing state. Their metadata choices are independent because they occur in separate factors of an expression.

This independence creates two obligations. Every pair of successful tests must consume exactly one true episode and describe its actual update. Conversely, every required episode and incoming state must admit at least one successful split. Assuming that the two sides silently coordinate their guesses would not meet the first obligation.

Absorb ambiguity into an affine correction

Represent monoid actions as linear maps over a finite vector space. It can be easier to transmit an affine update,

$$v\longmapsto vA+b,$$

than the original linear action alone. The correction $b$ can later be removed: subtracting the output at zero from the output at $v$ recovers $vA$. Finite unions and intersections express this comparison without increasing star height.

A finite clock limits which independently guessed tags can coexist at a cut. Matching tags describe the intended transmission; a controlled exceptional mismatch can be absorbed into a predetermined affine correction. Separate endpoint guards ensure that both tests are discussing the same episode length before clock information is used.

Markers provide recognizable local boundaries. When markers are absent over a long region, periodicity supplies structure instead. Powers in a finite monoid are eventually periodic, so a cut can sometimes move through a repeated region without changing the relevant product. No cancellation law or commutativity of the monoid is assumed.

Handle exceptional episodes with a second split

M3 uses a finite shift table to make one unknown interval product irrelevant to a corrected output. The prefix knows earlier products, the suffix knows later ones, and a finite condition accounts for all possibilities in the interval crossing the cut.

Some episodes fail the first split’s availability conditions. An earlier collection of candidate cuts—the stencil—handles these exceptions. The suffix uses a failed condition as evidence of the true episode origin. Counting all false candidate origins, including those with incorrect metadata, leaves a usable copy of every required kind of cut. After recovering the origin, the test separately checks the exact endpoint.

The second split transmits a total table defined even at hypothetical prefix values that no actual prefix realizes. This uniformity allows the same finite algebra to apply throughout the expression rather than relying on an unstated promise about successful guesses.

The height calculation then has the form

$$0\longrightarrow2\longrightarrow3.$$

Each split introduces one controlled layer beyond the initial setup. Component tests have height at most one because their only unbounded portions follow fixed periodic templates. Boolean recovery and concatenation with the final remainder add no star.

M2 uses three splits instead, giving $0\to2\to3\to4$, with two different residual decoders and several movement scales. M1 handles five residual witness types using prediction histories, requiring twelve split steps and yielding thirteen. These are different constructions of the same kind of boundedness, not twelve or three stars counted merely in a final printed formula.

7. Scope, limitations, and open questions

The result concerns generalized expressions with complement. It does not bound ordinary star height, and it does not remove the stars already nested inside the operand of a complement.

The universal height-one question remains open in these manuscripts. No language requiring generalized height greater than one is exhibited. Determining exact minimum height and deciding related membership questions require separate results.

The construction allows enormous finite sets, tables, and expressions. Bounded nesting depth therefore gives no polynomial expression-size bound and no efficient conversion algorithm. Exhaustive finite choices are compatible with the theorem’s scope.

Finally, the original-alphabet requirement and independent-witness conditions are substantive parts of the claims. The digest describes how the manuscripts address them, without independently checking the split, clock, or decoding arguments.

8. Sources and further reading

Schützenberger gives the height-zero algebraic characterization; Pin–Straubing–Thérien develops height-one classes and relevant closure properties. Bourne’s thesis illustrates modular factor-counting languages. The three source manuscripts below respectively present the bounds thirteen, four, and three and their distinct finite-computation constructions.

Source manuscripts

• M1. OpenAI, Finite Monoid Computations and a Uniform Generalized Star-Height Bound (2026).
• M2. OpenAI, Generalized Star Height at Most Four (2026).
• M3. OpenAI, Generalized Star Height at Most Three (2026).

Sources consulted on 9 October 2026 at repository revision fd4aeeb. Download the manuscript citations.