Star height problem

The star-height problem in formal language theory is the question whether all regular languages can be expressed using regular expressions with a limited nesting depth of Kleene stars. Specifically, is a nesting depth of more than 2 required? If so, can we determine how many are required?

This theoretical problem remained open for 25 years until it was solved by star height in 1988.

Also see generalized star height problem.

References

• Kosaburo Hashiguchi, Regular languages of star height one, Information and Control, 53: 199-210, 1982
• Kosaburo Hashiguchi, Algorithms for Determining Relative Star Height and Star Height, Inf. Comput. 78(2): 124-169, 1988