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 can be expressed using regular expressions with a built-in complement operator of limited star height, i. e. with a limited nesting depth of Kleene stars. 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.
See also
* star height problem
References
* M.P. Schützenberger, "On finite monoids having only trivial subgroups", Information and Control, 8, 190–194 (1965).
* Jean-Eric Pin, Howard Straubing and Denis Thérien, "Some results on the generalized star-height problem", Information and Computation, 101(2):219–250, December 1992. Available from http://www.liafa.jussieu.fr/~jep/Resumes/StarHeight.html
Wikimedia Foundation.
2010.
Look at other dictionaries:
Star height problem — The star height problem in formal language theory is the question whether all regular languages can be expressed using regular expressions of limited star height, i. e. with a limited nesting depth of Kleene stars. Specifically, is a nesting… … Wikipedia
Star height — In mathematics, the star height h ( E ) of a regular expression E over a finite alphabet A is defined as follows [ The definition given here is that of generalized star height since regular expressions are allowed to use the complement operator.] … Wikipedia
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, boolean operators and concatenation but no Kleene star. For instance, the language of… … Wikipedia
Kleene star — In mathematical logic and computer science, the Kleene star (or Kleene closure) 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 *. It is widely… … Wikipedia
List of computability and complexity topics — This is a list of computability and complexity topics, by Wikipedia page. Computability theory is the part of the theory of computation that deals with what can be computed, in principle. Computational complexity theory deals with how hard… … Wikipedia
List of mathematics articles (G) — NOTOC G G₂ G delta space G networks Gδ set G structure G test G127 G2 manifold G2 structure Gabor atom Gabor filter Gabor transform Gabor Wigner transform Gabow s algorithm Gabriel graph Gabriel s Horn Gain graph Gain group Galerkin method… … Wikipedia
Langage rationnel — Les langages rationnels ou langages réguliers ou encore langages reconnaissables peuvent être décrits de plusieurs façons équivalentes: ce sont les langages décrits par les expressions régulières ou rationnelles,d où le nom de langages réguliers; … Wikipédia en Français
List of formal language and literal string topics — This is a list of formal language and literal string topics, by Wikipedia page. Contents 1 Formal languages 2 Literal strings 3 Classical cryptography Formal languages Abstract syntax tree … Wikipedia
Sternhöhenproblem — Die Sternhöhe ist ein Begriff aus der Theoretischen Informatik. Inhaltsverzeichnis 1 Definition 2 Sternhöhenproblem 3 Verallgemeinerte Sternhöhe 4 Verallgemeinertes Sternhöhenproblem 5 … Deutsch Wikipedia
Sternhöhe (Informatik) — Die Sternhöhe ist ein Begriff aus der Theoretischen Informatik. Sie gibt zu einem regulären Ausdruck das Maximum aller verschachtelten Anwendungen des Kleene Stern Operators an. Inhaltsverzeichnis 1 Definition 2 Sternhöhenproblem 3… … Deutsch Wikipedia
