# Generalized star height at most three > Three nested stars are enough to describe any regular language once complement is allowed. Plain-English explainer, Lean status and sources. Canonical: https://closedform.nishachay.tech/e/openai-math-2026-134/ Last updated: 2026-10-11 **Three nested stars are enough to describe any regular language once complement is allowed.** **Trust:** Formal proof listed · **Papers:** 3 · **First paper:** September 25, 2026 · **Field:** Theoretical computer science · **Entry:** 134 *Explained by AI.* Drafted by one AI model and checked sentence by sentence against the paper by a different one. Spot a mistake? Report an error. A regular expression describes a set of words, and a star means "repeat as often as you like." If you may also take complements, some stars become unnecessary. These papers prove that no regular language ever needs stars nested more than three deep (Lean proof listed). This answers whether any fixed bound exists. Whether depth one always suffices is still open. ## At a glance - **First step:** 1963 (Lawrence Eggan, star height of regular events) - **Significance:** Major. It answers whether a fixed bound on generalized star height exists for all regular languages. The gap between one and three remains. - **Trust:** Formal proof listed - **Field:** Theoretical computer science (3 papers) ## The explanation Take every word made of the letters a and b that contains ab somewhere. There are 16 words of length four, and 11 of them qualify. The five that do not are aaaa, baaa, bbaa, bbba and bbbb. A regular expression (a short formula for a set of words) can describe this set. The usual formula reads: anything, then ab, then anything. Writing "anything" needs a star. The star means "repeat as often as you like." Now allow one more operation, the complement. It means every word not in a given set. The empty set contains no words, so its complement is every word. That writes "anything" with no star at all. So once complement is allowed, the set above needs zero stars. Some sets still need a star. Over the single letter a, take the words of even length. Up to length ten, that is 6 of the 11 possible lengths. Without a star, a one-letter set is always finite or cofinite (missing only finitely many words). The even lengths are neither, so this set needs one star. The generalized star height of a set of words counts stars inside stars. It is the smallest nesting depth of stars that any formula for the set needs, when complement is allowed. The sets in question are regular languages. These are the sets a finite automaton can recognize. A finite automaton is a machine with finitely many states that reads a word letter by letter. The question asks whether one fixed depth works for every regular language. Without complement, the answer is no. In 1963, Lawrence Eggan linked ordinary star height to the loops in an automaton's diagram. In 1966, Françoise Dejean and Marcel-Paul Schützenberger showed ordinary star height is unbounded, even with two letters. Those lower bounds do not carry over once complement is added. In 1965, Schützenberger described exactly which languages need no star in the generalized setting. Later work proved a depth of one for special families. Pin, Straubing and Thérien did this in 1992 for languages recognized by certain finite groups. Nothing gave a bound for every regular language. That was the obstacle: the known results covered only restricted families. A general regular language has no special structure to exploit. Every regular language does come with a finite monoid. That is a finite table recording how each word moves the automaton between states. The task is to compute that table's value for any word with only a few nested stars. These papers prove a uniform bound (Lean proof listed). Every regular language, over any finite alphabet, has generalized star height at most three[1]. The formulas use the same letters as the language, and complement means all other words over those letters[2]. Three separate papers give three separate proofs, of the bounds thirteen, four and three. None uses another's numerical result[3]. The proof of three cuts each word into pieces called episodes, which can be found in only one way[4]. It checks the front and back of each piece separately. A clock (a word-length counter that cycles) forces the two checks to agree, or to differ in one way only[5]. The paper builds each piece's computation so that this one mismatch still gives the right answer[6]. Two such splitting steps, each adding one star, reach depth three[7]. The bound limits the nesting only. The paper gives no bound on how long the formulas are or how long building them takes[8]. It also does not show that any language needs more than one star[9]. Whether depth one always suffices is still undecided. Howard Straubing's 2002 account treats that as a different question from the existence of a fixed bound[10]. How sure is this? A computer proof checker called Lean has checked a formal proof of the main statement. It says every regular language over a finite alphabet has depth at most three. Complements are taken over the same alphabet. The formal statement does not separately encode every construction step of the paper with the bound thirteen. No specialist review has been published. **What it doesn't show.** This does not show that any language needs more than one nested star. ## Where it came from This result comes from an unreleased OpenAI model, published in the openai/math release on 6 October 2026. ## Hype check Major for automata theory if the proof holds. Lean has checked a formal proof of the depth-three statement. The formulas may be huge, the question of depth one stays open, and no specialist review is published. ## Words used - **Regular language:** A set of words that a machine with finitely many states can recognize. - **Regular expression:** A short formula for a set of words, built from letters, union, joining words end to end, and the star. - **Kleene star:** The operation that repeats words from a set any number of times, including zero. - **Complement:** All words over the alphabet that are not in a given set. - **Generalized star height:** The smallest nesting depth of stars needed to write a language when complement is also allowed. - **Cofinite:** Missing only finitely many words. - **Finite monoid:** A finite table recording how words combine; here, how each word moves an automaton between states. ## The original papers (3) - [Finite Monoid Computations and a Uniform Generalized Star-Height Bound](https://github.com/openai/math/blob/main/preprints/Finite-Monoid-Computations-and-a-Uniform-Generalized-Star-Height-Bound-September-25-2026/Finite-Monoid-Computations-and-a-Uniform-Generalized-Star-Height-Bound-September-25-2026.pdf) - September 25, 2026 - [Generalized Star Height at Most Four](https://github.com/openai/math/blob/main/preprints/Generalized-Star-Height-at-Most-Four-September-25-2026/Generalized-Star-Height-at-Most-Four-September-25-2026.pdf) - September 25, 2026 - [Generalized Star Height at Most Three](https://github.com/openai/math/blob/main/preprints/Generalized-Star-Height-at-Most-Three-September-25-2026/article.pdf) - September 25, 2026 - [Lean notes](https://github.com/openai/math/blob/main/lean/docs/134.md) ## Quoted lines from the paper (10) [1] From [Generalized Star Height at Most Four](https://github.com/openai/math/blob/main/preprints/Generalized-Star-Height-at-Most-Four-September-25-2026/Generalized-Star-Height-at-Most-Four-September-25-2026.pdf): > Every regular language over a finite alphabet has generalized star height at most four over that same alphabet. [2] From [Generalized Star Height at Most Three](https://github.com/openai/math/blob/main/preprints/Generalized-Star-Height-at-Most-Three-September-25-2026/article.pdf): > The expressions in the theorem use the letters of $\Sigma$ itself. [3] From [Generalized Star Height at Most Three](https://github.com/openai/math/blob/main/preprints/Generalized-Star-Height-at-Most-Three-September-25-2026/article.pdf): > Each of the three papers gives its own complete proof; the numerical theorem of one is not used to prove another. [4] From [Generalized Star Height at Most Three](https://github.com/openai/math/blob/main/preprints/Generalized-Star-Height-at-Most-Three-September-25-2026/article.pdf): > This makes the episode boundaries unique. [5] From [Generalized Star Height at Most Three](https://github.com/openai/math/blob/main/preprints/Generalized-Star-Height-at-Most-Three-September-25-2026/article.pdf): > A clock restricts the pairs they can jointly realize: either they agree, or there is only one possible unequal pair. [6] From [Generalized Star Height at Most Three](https://github.com/openai/math/blob/main/preprints/Generalized-Star-Height-at-Most-Three-September-25-2026/article.pdf): > A clock restricts the pairs they can jointly realize: either they agree, or there is only one possible unequal pair. [7] From [Generalized Star Height at Most Three](https://github.com/openai/math/blob/main/preprints/Generalized-Star-Height-at-Most-Three-September-25-2026/article.pdf): > The inner split starts from empty skip computations and gives height two; recovery makes those computations the skips for the outer split, giving height three. [8] From [Generalized Star Height at Most Three](https://github.com/openai/math/blob/main/preprints/Generalized-Star-Height-at-Most-Three-September-25-2026/article.pdf): > The construction gives an upper bound on nesting, without a bound on expression size or running time. [9] From [Generalized Star Height at Most Three](https://github.com/openai/math/blob/main/preprints/Generalized-Star-Height-at-Most-Three-September-25-2026/article.pdf): > It does not exhibit a language of generalized height greater than one, and does not decide whether one always suffices. [10] From [Generalized Star Height at Most Three](https://github.com/openai/math/blob/main/preprints/Generalized-Star-Height-at-Most-Three-September-25-2026/article.pdf): > A universal finite upper bound and a universal upper bound of one are different assertions; Straubing distinguishes them explicitly in his account of the problem. ## Other sources - [L. C. Eggan, “Transition graphs and the star-height of regular events”, Michigan Mathematical Journal 10 (1963), 385–397](https://doi.org/10.1307/mmj/1028998975) - [F. Dejean and M.-P. Schützenberger, “On a question of Eggan”, Information and Control 9 (1966), 23–25](https://doi.org/10.1016/S0019-9958(66)90083-0) - [M.-P. Schützenberger, “On finite monoids having only trivial subgroups”, Information and Control 8 (1965), 190–194](https://doi.org/10.1016/S0019-9958(65)90108-7) - [J.-É. Pin, H. Straubing and D. Thérien, “Some results on the generalized star-height problem”, Information and Computation 101 (1992), 219–250](https://doi.org/10.1016/0890-5401(92)90063-L) - [H. Straubing, “On logical descriptions of regular languages”, LATIN 2002, LNCS 2286, 528–538](https://doi.org/10.1007/3-540-45995-2_46) ## Related - [The computational complexity of Weisfeiler–Leman refinement](https://closedform.nishachay.tech/e/openai-math-2026-133/) - Theoretical computer science - [Exact Fourier transforms below n log n](https://closedform.nishachay.tech/e/openai-math-2026-130/) - Theoretical computer science - [Almost-linear-time exact matching and prescribed-degree factors in general graphs](https://closedform.nishachay.tech/e/openai-math-2026-120/) - Theoretical computer science - [Integer multiplication below n log n](https://closedform.nishachay.tech/e/openai-math-2026-109/) - Theoretical computer science - [Matrix multiplication with exponent at most 9/4](https://closedform.nishachay.tech/e/openai-math-2026-107/) - Theoretical computer science - [Theoretical computer science](https://closedform.nishachay.tech/science/mathematics/theoretical-computer-science/) - Field · 40 results - [Open since the 1960s](https://closedform.nishachay.tech/open-since/1960s/) - Era · 33 results - [Lean-checked results](https://closedform.nishachay.tech/trust/lean-checked/) - Trust · 242 results - [Report an error](https://github.com/nishachay/closed-form/issues/new?template=report-error.yml&labels=entry-error&title=%5Bentry%20134%5D%20)