Browse › Theoretical computer science › 134 Generalized star height at most three
Generalized Star Height at Most Four
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 four over that same alphabet. We give a complete construction using an affine correction that hides one interval product, a finite clock, and several scales for moving boundaries through periodic words.
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 bound three over the same alphabet, which implies this paper's bound of four; the paper's own multiscale construction is not formalized step by step. [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 discussion of inverse-morphism closure and of whether height one 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 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:Generalized-Star-Height-at-Most-Four-September-25-2026,
author = {{OpenAI}},
title = {{Generalized Star Height at Most Four}},
howpublished = {OpenAI Math Release preprint
\href{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}{OAI:Generalized-Star-Height-at-Most-Four-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 Three · September 25, 2026