Generalized star height at most three

What OpenAI claims

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)

Papers (3)

1. Finite Monoid Computations and a Uniform Generalized Star-Height Bound

   25 September 2026 · Preprint, not peer reviewed · PDF

   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.

2. Generalized Star Height at Most Four

   25 September 2026 · Preprint, not peer reviewed · PDF

   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.

3. Generalized Star Height at Most Three

   25 September 2026 · Preprint, not peer reviewed · PDF

   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.

Status

Preprint. The papers have not been independently reviewed. Treat the result as OpenAI's claim until other mathematicians have checked it. If a video exists, it illustrates the statement; it is not the proof.