Star height problem (Solved)

Recomm. for undergrads: no
Posted by: porton
on: December 28th, 2011
Solved by: Eggan (1963), Hashiguchi (1988)
Conjecture   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 one always sufficient? If not, is there an algorithm to determine how many are required?


*Lawrence C. Eggan: Transition graphs and the star-height of regular events, Michigan Mathematical Journal, 10(4): 385–397, 1963.

* indicates original appearance(s) of problem.

This was solved ages ago!

See the referenced Wikipedia article.

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.