Star height problem

The star-height problem in formal language theory is the question whether all regular languages can be expressed using regular expressions of limited star height, i. e. with a limited nesting depth of Kleene stars. Specifically, is a nesting depth of more than 2 required? If so, is there an algorithm to 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.

ee also

*Generalized star height problem

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