Browse › Theoretical computer science › 134 Generalized star height at most three
Generalized Star Height at Most Three
Open PDFCite Report a problem Add a reference or comment Interested in working on this Start a discussion
Edit NOTES.md · Existing issues · Source on GitHub
Abstract
Every regular language over a finite alphabet has generalized star height at most three, with complement taken in the same free monoid. We express finite-monoid computations using a prefix code of word pieces.
If the PDF does not display here, open it directly: Open PDF.
Notes
No notes yet. Add a reference, a comment or your name with the buttons above, or edit NOTES.md on GitHub.
Automatically collected notes (unreviewed)
work in progress
Collected automatically by AI tools (Claude Opus 5.5 and GPT-6 Astra, 2026-10-21) and not checked by a person. May be wrong or incomplete. Report an error.
Follow-up works
- Elias Botsford, Generalized Star Height One for Computations via Run Padding (Zenodo preprint, doi:10.5281/zenodo.23254500, 2026-10-09). States that it is motivated by the release's claim that every regular language has generalized star height at most three and studies a complementary height-one phenomenon (run padding, actions with at most one nontrivial cycle per letter). [family-level]
Formalization
- mathcommunity/oai-math-revised, lean/docs/134.md: Generalized star height at most three (release Lean scope notes). Says the formalization proves that every regular language over a finite alphabet has a generalized expression over the same alphabet of star height at most three, with complement in the same free monoid. [family-level]
- OpenAI, lean/OAI/Computability/StarHeight/Main.lean (openai/math repository). Contains the theorem
OAI.GeneralizedStarHeight.main, statingHasHeightAtMost L 3for every regularLover a finite alphabet, reduced viaOAI.Computability.StarHeight.Recognitionto finite-monoid recognition andFiniteRecognition.recognized_height_three. [family-level]
Possibly relevant literature (found by the agent, not checked)
- Jean-Éric Pin, Open problems about regular languages, 35 years later (talk slides, Brzozowski 80, 2015-06-24). Slides 9–10 note that no language of generalized star height greater than one was known and recall that if the height-at-most-one languages form a variety then all regular languages have height at most one; this bears on the paper's remark that it does not decide whether height one always suffices.
Digests and expositions
- Azmat, Generalized Star Height Problem: How OpenAI’s Two-Split Proof Sets a Three-Level Ceiling (Binary Verse AI, 2026-10-18). Explains this manuscript’s two splits, shift tables and suffix decoder, situates the companion bounds of thirteen and four, and distinguishes exposition from an independent correctness audit.
Elsewhere
- VibeMathed: Problem record
- Emergent Mind: family 134
Independent sites; their content is not reviewed here.
Cite
@misc{OAI:Generalized-Star-Height-at-Most-Three-September-25-2026,
author = {{OpenAI}},
title = {{Generalized Star Height at Most Three}},
howpublished = {OpenAI Math Release preprint
\href{https://github.com/openai/math/blob/main/preprints/Generalized-Star-Height-at-Most-Three-September-25-2026/article.pdf}{OAI:Generalized-Star-Height-at-Most-Three-September-25-2026}},
year = {2026}
}Lean formalization
OpenAI provides Lean files for this family: lean/docs/134.md. The Lean statements have not been checked by people against the paper's claims.
Family 134: Generalized star height at most three
Every regular language over a finite alphabet has a generalized regular expression with at most three nested Kleene stars, allowing union, concatenation and complement over the same alphabet. This establishes an absolute bound independent of automaton size, resolving the uniform-boundedness version of the generalized star-height problem.
Other papers in this family:
- Finite Monoid Computations and a Uniform Generalized Star-Height Bound · September 25, 2026
- Generalized Star Height at Most Four · September 25, 2026