View source for 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 ([https://github.com/openai/math 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'' ⊆ Σ<sup>*</sup>, ''L'' is defined by a generalized regular expression over Σ of star height at most three. Complement is taken in Σ<sup>*</sup>, 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 <code>1581d4c</code>:
** [https://github.com/openai/math/tree/1581d4cbdd69a0faf34b2089614fe2a814316a6a/preprints/Generalized-Star-Height-at-Most-Three-September-25-2026 Generalized Star Height at Most Three];
** [https://github.com/openai/math/tree/1581d4cbdd69a0faf34b2089614fe2a814316a6a/preprints/Generalized-Star-Height-at-Most-Four-September-25-2026 Generalized Star Height at Most Four];
** [https://github.com/openai/math/tree/1581d4cbdd69a0faf34b2089614fe2a814316a6a/preprints/Finite-Monoid-Computations-and-a-Uniform-Generalized-Star-Height-Bound-September-25-2026 Finite Monoid Computations and a Uniform Generalized Star-Height Bound].
* '''Formalization, as described by the repository.''' The scope note [https://github.com/openai/math/blob/1581d4cbdd69a0faf34b2089614fe2a814316a6a/lean/docs/134.md 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 <code>GeneralizedStarHeight</code>.

== Public follow-up work ==
{| class="wikitable"
! Date !! Work !! Relation !! Public claim !! Public status (checked 22 October 2026)
|-
| 2026-10-08 || [https://github.com/mathvet/mathvet MathVet] (GitHub; review of openai/math, tables at repository commit <code>bb5fdb6</code>, 18 October 2026) || Review (fidelity of the formal statements) || Rates this family "full" and records a sandboxed Comparator pass for <code>GeneralizedStarHeight</code>, 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 [https://github.com/carlostoledo1891/cert-machine/blob/d93dd5b48e798372da73a42ac2275a3eeacd9a5e/corpus/openai-math/kernel-runs/38019899278/GeneralizedStarHeight.json 38019899278] for <code>GeneralizedStarHeight</code> || 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) || [https://github.com/jiamo/lambda-computability/tree/035a085b376d957b0086455dbf8129c2a4b2f52f jiamo/lambda-computability] (GitHub, commit <code>035a085</code>) || Use (Lean port) || A Lean library on lambda calculus and computability. Its <code>NOTICE</code> file lists the collection's <code>StarHeight</code> 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 || [https://github.com/tangentproofs/star-height/tree/d92db5e81e0baf1d6f684b32a9c2abb61ac0ed2b tangentproofs/star-height] (GitHub, commit <code>d92db5e</code>) || Use (Lean port and exposition) || The collection's star-height formalization, vendored from commit <code>1581d4c</code> 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.

[[Category:OpenAI results]]