Every Regular Language Has Generalized Star Height At Most Four

OpenAI’s manuscript claims that every regular language over a finite alphabet can be described by a regular expression of generalized star height at most four, using that same alphabet. The bound is uniform: it does not increase with the number of states in an automaton recognizing the language. It says nothing useful about how long the resulting expression may be.

Generalized star height measures nesting, not the number of star symbols. A star applies repetition zero or more times: a* includes the empty word, a, aa, and so on. In (a* b)*, the written expression has height two because one star is inside another. But that does not establish that the language requires height two; a different expression for the same language might be shallower.

The permitted operations also include union, concatenation, and complement. Union and concatenation take the maximum height of their inputs, while complement leaves height unchanged. Complement is taken over the same alphabet: it denotes every word over that alphabet excluded by the expression. It does not erase stars already present. Even the language of all words, written as the complement of the empty language, has height zero.

The proof turns a deterministic finite automaton into a finite monoid: each word induces a transformation of the automaton’s states, and concatenated words compose those transformations in reading order. Since the monoid need not be commutative, the proof must preserve the order of products. Recognizing which monoid value a word produces is the central computational task.

The construction divides a word into complete episodes and a final unfinished remainder. Each episode has a prescribed end, and no complete episode is a proper prefix of another, so episode boundaries are unambiguous. Within an episode, consecutive intervals each carry a monoid product.

The key difficulty is a cut through one interval. The prefix can know the products before the cut, and the suffix can know those after it; neither knows the whole product crossing the cut. The two sides also make their finite guesses independently. The construction therefore has to ensure that every accepted pairing is sound—not merely that one fortunate pair of guesses gives the right answer.

The manuscript’s solution is to make the missing product irrelevant to a test. It uses fixed-length binary vectors, with addition modulo two, and a linear action of the monoid. A finite lemma supplies a tuple length and a correction, beta, determined by the full tuple of interval products but independent of the input vector. For every input vector and tuple, some coordinate can vary across the monoid without changing the corrected output. The successful coordinate may depend on the input and tuple; the tuple length and correction stay fixed.

A small example illustrates the cancellation. Take the monoid {0,1} with ordinary multiplication, set the input to one, and hold the last two interval products at one. As the first product changes from zero to one, the raw output changes, and beta changes with it. Their sum modulo two remains zero. A suffix can test constancy without knowing the missing product. The manuscript establishes the general existence of beta by a finite probability argument.

The correction can be removed from the computation without adding star height. Each local update has the form “apply a linear map, then add a fixed offset.” Composing updates preserves that form, so an entire episode sequence sends v to vL + c. Run the same word from v and from zero: the outputs are vL + c and c. Adding them modulo two cancels the offset and leaves vL. Intersections and finite unions over possible offsets let the language tests require both outcomes on the same word; those Boolean operations add no star.

Making the missing product irrelevant does not tell a suffix where an episode began. A finite clock controls which independently chosen tags can meet: the construction arranges either matching tags or one uniquely specified mismatch, which its correction handles.

Markers anchor boundaries. Away from markers, long windows force periodic letters, allowing boundaries to move at selected scales while preserving ordered monoid products. The movement must also respect a full monoid period and sufficiently long margins; periodic letters alone are not enough. The construction relies on neither cancellation nor rearrangement.

A polynomial roster supplies candidate copies of each needed cut. Counting ambiguous pairs of possible origins shows that enough copies survive. These timing and counting arguments are substantial parts of the proof, not consequences of the schematic diagrams.

Two residual stages handle episodes skipped by the main split. Their order matters: stage zero establishes a common exact end before identifying the unique origin; stage one identifies the origin using bounded tests before checking that origin’s exact end. Every candidate must have its required window. If a window is missing, the test rejects; it cannot discard an inconvenient candidate to manufacture uniqueness. The construction also uses the physical order of the buffers—buffer one precedes buffer zero—so each suffix can read the later update table. Those tables cover every monoid value, including hypothetical values no actual prefix realizes, and encode outputs as basis vectors so the lower-level computation can be recovered by the same two-run method.

The height accounting depends on keeping each component test shallow, even when its guessed origin is wrong. Each suffix has at most one unbounded periodic continuation. After finitely many choices, its words have a fixed beginning, repeated copies of a fixed nonempty block, and a fixed ending. Finite monoid powers and length residues eventually repeat, so accepted repetition counts reduce to finite exceptions and finitely many arithmetic progressions.

For counts of the form h₀ + fk, the corresponding words can be written with a fixed beginning, h₀ copies of the block, a star over f copies, and a fixed ending. For example: A B² (B³)* C. This uses one star, with all blocks literal words over the original alphabet.

When a split extends a graph test from skipped episodes to a larger class, the height bound becomes max(2, B + 1), where B bounds the skipped tests. The floor of two comes from the episode-domain test; the split adds a star around earlier tests. Recovery by two runs does not add height.

| Stage | Height bound | |---|---:| | Empty sequence | 0 | | Stage one split | 2 | | Stage zero split | 3 | | Main split | 4 |

The final two-run recovery reads the true monoid product at the same height. The unfinished remainder has height-one monoid-value tests; joining it to episode sequences and taking a finite union over accepting products keeps the total bound at four.

The claim is a uniform nesting bound, not an efficient expression-length guarantee. It also does not show that any language needs more than one star level. A companion paper is said to claim a bound of three by a different construction; that result is not a premise of the four-level argument.