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)
“Our star was brighter perhaps when it had water in it.
Now there is no question even of that, but only
Of holding on to the hard earth so as not to get thrown off,
With an occasional dream, a vision ...”
—John Ashbery (b. 1927)
“The prevalence of suicide, without doubt, is a test of height in civilization; it means that the population is winding up its nervous and intellectual system to the utmost point of tension and that sometimes it snaps.”
—Havelock Ellis (1859–1939)
“But a problem occurs about nothing. For that from which something is made is a cause of the thing made from it; and, necessarily, every cause contributes some assistance to the effect’s existence.”
—Anselm of Canterbury (1033–1109)