Generalized star-height problem
In-game article clicks load inline without leaving the challenge.
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.
Regular languages of generalized 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
- Janusz A. Brzozowski (1980). "Open problems about regular languages". In Ronald V. Book (ed.). Formal Language Theory: Perspectives and Open Problems. Academic Press. pp. 23–47.
- Wolfgang Thomas (1981). . Theoretical Computer Science. 13 (2): 231–237. doi:. MR .
- Jean-Eric Pin; Howard Straubing; Denis Thérien (1992). (PDF). Information and Computation. 101 (2): 219–250. doi:.
- Sakarovitch, Jacques (2009). Elements of automata theory. Translated from the French by Reuben Thomas. Cambridge: Cambridge University Press. ISBN 978-0-521-84425-3. Zbl .
- Marcel-Paul Schützenberger (1965). . Information and Control. 8 (2): 190–194. doi:. Zbl .