Generalized star height problem
Encyclopedia
The generalized star-height problem in formal language theory is the open question whether all regular language
s can be expressed using generalized regular expressions with a limited nesting depth of Kleene star
s. 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 language
s of star-height 0 are also known as star-free language
s. The theorem of Schützenberger
provides an algebraic characterization of star-free languages by means of aperiodic syntactic monoid
s. In particular star-free languages are a proper decidable subclass of regular languages.
Regular language
In theoretical computer science and formal language theory, a regular language is a formal language that can be expressed using regular expression....
s can be expressed using generalized regular expressions with a limited nesting depth of Kleene star
Kleene star
In mathematical logic and computer science, the Kleene star is a unary operation, either on sets of strings or on sets of symbols or characters. The application of the Kleene star to a set V is written as V*...
s. 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
Star height
In theoretical computer science, more precisely in the theory of formal languages, the star height is a measure for the structural complexityof regular expressions: The star height equals the maximum nesting depth of stars appearing in the regular expression....
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
Algorithm
In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...
to determine the minimum required star height.
Regular language
Regular language
In theoretical computer science and formal language theory, a regular language is a formal language that can be expressed using regular expression....
s of star-height 0 are also known as star-free language
Star-free language
A regular language is said to be star-free if it can be described by a regular expression constructed from the letters of the alphabet, the empty set symbol, all boolean operators – including complementation – and concatenation but no Kleene star...
s. The theorem of Schützenberger
Marcel-Paul Schützenberger
Marcel-Paul "Marco" Schützenberger was a French mathematician and Doctor of Medicine. His work had impact across the fields of formal language, combinatorics, and information theory...
provides an algebraic characterization of star-free languages by means of aperiodic syntactic monoid
Syntactic monoid
In mathematics and computer science, the syntactic monoid M of a formal language L is the smallest monoid that recognizes the language L.-Syntactic quotient:...
s. In particular star-free languages are a proper decidable subclass of regular languages.