Family 134Theoretical computer scienceNo LeanNot yet digested
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.
Manuscripts in this family · 3
Finite Monoid Computations and a Uniform Generalized Star-Height Bound
Sep 25, 2026·Finite-Monoid-Computations-and-a-Uniform-Generalized-Star-Height-Bound-September-25-2026.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.
Generalized Star Height at Most Four
Sep 25, 2026·Generalized-Star-Height-at-Most-Four-September-25-2026.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.
Generalized Star Height at Most Three
Sep 25, 2026·article.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.