Star height

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.

See also


  • 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

Search another word or see Star heighton Dictionary | Thesaurus |Spanish
Copyright © 2015, LLC. All rights reserved.
  • Please Login or Sign Up to use the Recent Searches feature