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.
- 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