Browse › Theoretical computer science › 134 Generalized star height at most three
Finite Monoid Computations and a Uniform Generalized Star-Height Bound
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 a generalized regular expression of star height at most thirteen over that same alphabet. We prove this uniform bound by representing finite monoid computations as affine updates and recovering them through twelve successive split constructions.
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; it does not name this specific paper. [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 the uniform bound three, which implies this paper's bound of thirteen, and does not encode the paper's construction steps separately. [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 to 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 distinction between uniform boundedness and the height-one question.
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 the height-three 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. [family-level]
Elsewhere
- Emergent Mind: family 134
Independent sites; their content is not reviewed here.
Cite
@misc{OAI:Finite-Monoid-Computations-and-a-Uniform-Generalized-Star-Height-Bound-September-25-2026,
author = {{OpenAI}},
title = {{Finite Monoid Computations and a Uniform Generalized Star-Height Bound}},
howpublished = {OpenAI Math Release preprint
\href{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}{OAI:Finite-Monoid-Computations-and-a-Uniform-Generalized-Star-Height-Bound-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:
- Generalized Star Height at Most Four · September 25, 2026
- Generalized Star Height at Most Three · September 25, 2026