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

The first question was answered in the negative when in 1963, Eggan gave examples of regular languages of star height n for every n. However, Eggan's example languages realizing star height n. His examples use a large alphabet, of size 2ⁿ-1 for the language with star height n. He thus asked whether we can also find examples over binary alphabets. This was proved to be true shortly afterwards by Dejean and Schützenberger (1966).

In contrast, the second question remained unresolved for 25 years until it was settled by Kosaburo Hashiguchi, who in 1988 published an algorithm to determine the star height of any regular language. The algorithm wasn't at all practical, being 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. This still greatly exceeds the margins of what is considered practically feasible.

[edit] See also

Generalized star height problem

[edit] References

Lawrence C. Eggan, Transition graphs and the star-height of regular events, Michigan Mathematical Journal, 10(4): 385–397, 1963
Françoise Dejean, Marcel-Paul Schützenberger: On a Question of Eggan, Information and Control 9(1): 23-25, 1966
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, Information and Computation 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