Generalized star-height problem
Unsolved problem in formal language theory
In formal language theory, the generalized star-height problem 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 with 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.
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. A 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.
Sources and credits
This article is adapted from the Wikipedia article “Generalized star-height problem”, written by its contributors and licensed under CC BY-SA 4.0. Fathomly has changed the layout, removed citation markers, navigation and maintenance notices, and adjusted punctuation. This adapted version is shared under the same license. For references, see the original article.
Fathomly is not affiliated with or endorsed by the Wikimedia Foundation. Spotted a problem? Tell us.