Generalized star height at most three

The generalized star-height problem asks how deeply Kleene stars must be nested in regular expressions that may also use complement. Three manuscripts dated 25 September 2026 in OpenAI's public mathematics collection (github.com/openai/math) claim a uniform bound: every regular language over a finite alphabet has generalized star height at most three. This page summarizes the published claim and lists publicly available follow-up work. Statements are the respective authors' claims; the publication of a paper, code or a formal proof is not presented here as independent verification.

Background

• As recounted in the introduction of the main manuscript:
  • For the ordinary star height, without complement, Eggan connected star height with the cycle structure of transition graphs, and Dejean and Schützenberger showed that it is unbounded already over a two-letter alphabet.
  • Generalized height zero gives the star-free languages, which Schützenberger characterized as those recognized by finite aperiodic monoids.
  • Pin, Straubing and Thérien proved height at most one for languages recognized by finite nilpotent groups of class two and further classes of finite monoids, and Bourne and Ruškuc proved height-one bounds for some factor-counting languages.

The original result

• Claim. The manuscript Generalized Star Height at Most Three states that for every finite alphabet Σ and every regular language L ⊆ Σ^*, L is defined by a generalized regular expression over Σ of star height at most three. Complement is taken in Σ^*, and complement does not raise the height.
  • The expressions use the letters of Σ itself; their size may depend on the language. The bound is on nesting, not on expression size or running time.
• Method, as described: finite-monoid computations are expressed through a prefix code of word pieces.
• Companions. Generalized Star Height at Most Four and Finite Monoid Computations and a Uniform Generalized Star-Height Bound give weaker uniform bounds by related methods.
• Sources. At commit 1581d4c:
  • Generalized Star Height at Most Three;
  • Generalized Star Height at Most Four;
  • Finite Monoid Computations and a Uniform Generalized Star-Height Bound.
• Formalization, as described by the repository. The scope note lean/docs/134.md states that the Lean formalization proves the bound of three for every regular language over a finite alphabet. The Comparator challenge is GeneralizedStarHeight.

Public follow-up work

Date	Work	Relation	Public claim	Public status (checked 22 October 2026)
2026-10-08	MathVet (GitHub; review of openai/math, tables at repository commit bb5fdb6, 18 October 2026)	Review (fidelity of the formal statements)	Rates this family "full" and records a sandboxed Comparator pass for GeneralizedStarHeight, whose axioms are the standard three.	MathVet states that it does not claim any theorem false and reports what was machine-checked as stated.
2026-10-10	cert-machine, openai/math lane K: run 38019899278 for GeneralizedStarHeight	Verification (two kernels)	Records that Lean's default kernel and the nanoda kernel accept the solution, in 238 s.	Repository.
2026-10-20 (latest commit)	jiamo/lambda-computability (GitHub, commit 035a085)	Use (Lean port)	A Lean library on lambda calculus and computability. Its NOTICE file lists the collection's StarHeight directory, 37 files, as adapted to its own Lean and Mathlib versions, and states that "the mathematics and the proofs are upstream's".	GitHub repository.
2026-10-22	tangentproofs/star-height (GitHub, commit d92db5e)	Use (Lean port and exposition)	The collection's star-height formalization, vendored from commit 1581d4c and moved to Lean v4.35.0-rc1 and a newer Mathlib, about 12,000 lines in 37 files, with a check that the main theorem uses only the standard axioms. It adds a static site that explains each declaration in plain English with demonstrations and quizzes. The README credits the result and the original Lean proof to OpenAI.	GitHub repository.

Notes

• The earlier results are due to the authors named in the Background section, as recounted by the manuscript.
• The list covers follow-ups found in public sources up to the date above; it is not a priority or completeness claim.