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. However, the drawback is that this algorithm is of non-elementary complexity. A much more efficient algorithm was given by Daniel Kirsten in 2005, which runs, for a given nondeterministic finite automaton as input, in double-exponential space. Of course the guarantee on the memory requirement of that algorithm is still rather large.

[edit] See also

[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
Daniel Kirsten, Distance Desert Automata and the Star Height Problem, RAIRO - Informatique Théorique et Applications 39(3):455–509, 2005