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 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.
Famous quotes containing the words generalized, star, height and/or problem:
“One is conscious of no brave and noble earnestness in it, of no generalized passion for intellectual and spiritual adventure, of no organized determination to think things out. What is there is a highly self-conscious and insipid correctness, a bloodless respectability submergence of matter in manner—in brief, what is there is the feeble, uninspiring quality of German painting and English music.”
—H.L. (Henry Lewis)
“What is Africa to me:
Copper sun or scarlet sea,
Jungle star or jungle track,
Strong bronzed men, or regal black
Women from whose loins I sprang
When the birds of Eden sang?”
—Countee Cullen (1903–1946)
“Much more frequent in Hollywood than the emergence of Cinderella is her sudden vanishing. At our party, even in those glowing days, the clock was always striking twelve for someone at the height of greatness; and there was never a prince to fetch her back to the happy scene.”
—Ben Hecht (1893–1964)
“Every child is an artist. The problem is how to remain an artist once he grows up.”
—Pablo Picasso (1881–1973)