Generalized star-height problem

The generalized star-height problem in formal language theory is the open question whether all regular languages defined by regular expressions that include the complement operator can be expressed using regular expressions (possibly including the complement operator) with a limited nesting depth of Kleene stars. Specifically, it is an open question whether a nesting depth of more than 2 is required, and if so, whether it is possible to determine how many are required.

Regular languages of star-height 0 are also known as star-free languages. The theorem of Schützenberger provides an algebraic characterization of star-free languages by means of aperiodic syntactic monoids. In particular star-free languages are a proper decidable subclass of regular languages.

See also

• star height problem

References

• M.P. Schützenberger, "On finite monoids having only trivial subgroups", Information and Control, 8, 190-194 (1965).

• Jean-Eric Pin, Howard Straubing and Denis Thérien, Some results on the generalized star-height problem, Information and Computation, 101(2):219-250, December 1992. Available from http://www.liafa.jussieu.fr/~jep/Resumes/StarHeight.html