Star height problem

From Wikipedia, the free encyclopedia

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?

Both questions have now been answered. In 1963, L. C. Eggan gave examples of regular languages of star height n for every n. The latter problem remained open for 25 years until it was solved by Kosaburo Hashiguchi, who in 1988 published an algorithm to determine the star height of a regular language.

Also see generalized star height problem.

[edit] References

• L. C. Eggan, Transition graphs and the star-height of regular events, Michigan Math. J., 10(4): 385-397, 1963
• 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