Generalized star-height problem
{{Short description|Unsolved problem in formal language theory}}
{{unsolved|computer science|Can all regular languages be expressed using generalized regular expressions with a limited nesting depth of Kleene stars?}}
The generalized star-height problem in formal language theory is the open question whether all regular languages can be expressed using generalized regular expressions with a limited nesting depth of Kleene stars. Here, generalized regular expressions are defined like regular expressions, but they have a built-in complement operator. For a regular language, its generalized star height is defined as the minimum nesting depth of Kleene stars needed in order to describe the language by means of a generalized regular expression, hence the name of the problem.
More specifically, it is an open question whether a nesting depth of more than 1 is required, and if so, whether there is an algorithm to determine the minimum required star height.Sakarovitch (2009) p.171
Regular languages of star-height 0 are also known as star-free languages. The theorem of Schützenberger provides an algebraic characterization of star-free languages by means of aperiodic syntactic monoids. In particular star-free languages are a proper decidable subclass of regular languages.
See also
- Eggan's theorem and Generalized star height sections of the Star height article
- Star height problem
References
{{reflist}}
- {{cite book |author=Janusz A. Brzozowski |year=1980 |chapter=Open problems about regular languages |editor=Ronald V. Book |title=Formal Language Theory: Perspectives and Open Problems |pages=23–47 |publisher=Academic Press}}
- {{cite journal |author=Wolfgang Thomas |year=1981 |title=Remark on the star-height-problem |journal=Theoretical Computer Science |volume=13 |issue=2 |pages=231–237 |doi=10.1016/0304-3975(81)90041-4 |mr=0594062|doi-access=free }}
- {{cite journal |author1=Jean-Eric Pin |author2=Howard Straubing |author3=Denis Thérien |year=1992 |title=Some results on the generalized star-height problem |url=https://www.irif.fr/~jep//PDF/StarHeight.pdf |journal=Information and Computation |volume=101 |issue=2 |pages=219–250 |doi=10.1016/0890-5401(92)90063-L}}
- {{cite book |last=Sakarovitch |first=Jacques |title=Elements of automata theory |others=Translated from the French by Reuben Thomas |location=Cambridge |publisher=Cambridge University Press |year=2009 |isbn=978-0-521-84425-3 |zbl=1188.68177 }}
- {{cite journal |author=Marcel-Paul Schützenberger |authorlink=Marcel-Paul Schützenberger |year=1965 |title=On finite monoids having only trivial subgroups |journal=Information and Control |volume=8 |issue=2 |pages=190–194 |doi=10.1016/S0019-9958(65)90108-7 |zbl=0131.02001|doi-access=free }}
External links
- [http://www.liafa.jussieu.fr/~jep/Problemes/starheight.html Jean-Eric Pin: The star-height problem]
Category:Unsolved problems in computer science
Category:Automata (computation)
{{comp-sci-theory-stub}}