Star-free language

From Wikipedia, the free encyclopedia

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.[1] For instance, the language of words over the alphabet \{a,\,b\} that do not have consecutive a's can be defined by (\emptyset ^{c}aa\emptyset ^{c})^{c}, where X^{c} denotes the complement of a subset X of \{a,\,b\}^{*}. The condition is equivalent to having generalized star height zero.

Marcel-Paul Schützenberger characterized star-free languages as those with aperiodic syntactic monoids.[2][3] They can also be characterized logically as languages definable in FO[<], the monadic first-order logic over the natural numbers with the less-than relation,[4] as the counter-free languages[5] and as languages definable in linear temporal logic.[6]

All star-free languages are in uniform AC0.

See also

References

  1. ↑ Lawson (2004) p.235
  2. ↑ Marcel-Paul Schützenberger (1965). "On finite monoids having only trivial subgroups". Information and Computation 8 (2): 190–194. 
  3. ↑ Lawson (2004) p.262
  4. ↑ Straubing, Howard (1994). Finite automata, formal logic, and circuit complexity. Progress in Theoretical Computer Science. Basel: Birkhäuser. p. 79. ISBN 3-7643-3719-2. Zbl 0816.68086. 
  5. ↑ McNaughton, Robert; Papert, Seymour (1971). Counter-free Automata. Research Monograph 65. With an appendix by William Henneman. MIT Press. ISBN 0-262-13076-9. Zbl 0232.94024. 
  6. ↑ Kamp, Johan Antony Willem (1968). Tense Logic and the Theory of Linear Order. University of California at Los Angeles (UCLA). 
  • Lawson, Mark V. (2004). Finite automata. Chapman and Hall/CRC. ISBN 1-58488-255-7. Zbl 1086.68074. 
  • Diekert, Volker; Gastin, Paul (2008). "First-order definable languages". In Jörg Flum; Erich Grädel; Thomas Wilke. Logic and automata: history and perspectives. Amsterdam University Press. ISBN 978-90-5356-576-6.  Unknown parameter |unused_data= ignored (help)
Each category of languages is a proper subset of the category directly above it. Any language in each category is generated by a grammar and by an automaton in the category in the same line.


This article is issued from Wikipedia. The text is available under the Creative Commons Attribution/Share Alike; additional terms may apply for the media files.