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 Kosaburo Hashiguchi. The answer to all questions is yes: Hashiguchi published an algorithm to determine an expression's 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\n* Kosaburo Hashiguchi, Algorithms for Determining Relative Star Height and Star Height, Inf. Comput. 78(2): 124-169, 1988

Category:Formal languages\nCategory:Theorems