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
- Kosaburo Hashiguchi, Algorithms for Determining Relative Star Height and Star Height, Inf. Comput. 78(2): 124-169, 1988Template:Math-stub