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. (Lean)
Manuscripts (3)
Finite Monoid Computations and a Uniform Generalized Star-Height Bound
September 25, 2026 · source · cite as \cite{OAI:Finite-Monoid-Computations-and-a-Uniform-Generalized-Star-Height-Bound-September-25-2026}
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.
Generalized Star Height at Most Four
September 25, 2026 · source · cite as \cite{OAI:Generalized-Star-Height-at-Most-Four-September-25-2026}
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.
Generalized Star Height at Most Three
September 25, 2026 · source · cite as \cite{OAI:Generalized-Star-Height-at-Most-Three-September-25-2026}
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.
Result 134 · Theoretical computer science. Imported from openai/math, a collection of manuscripts produced by an OpenAI model; results are at different stages of verification. Discussion below is by Lemma members.
Source: https://github.com/openai/math/blob/main/CONTENTS.md