Encyclopedia > G > Generalized star height problem
Generalized star height problem
The generalized star-height problem in formal language theory is the open question whether all regular languages defined by regular expressions that include the complement operator can be expressed using regular expressions (possibly including the complement operator) with a limited nesting depth of Kleene stars. Specifically, it is an open question whether a nesting depth of more than 2 is required, and if so, whether it is possible to determine how many are required.
Information are taken from Wikipedia, the open encyclopedia, to which contribute many volunteers from around the whole world. Texts are available under the following conditions GNU Free Documentation License.
Encyklopedie (cz) Encyklopédia (sk) Enzyklopädie (de)