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.

See also

• star height problem

References

• 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