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. For instance, the language of words over the alphabet that do not have consecutive a's can be defined by , where denotes the complement of a subset of .
Marcel-Paul Schützenberger characterized star-free languages as those with aperiodic syntactic monoids [1]. 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, as the languages acceptable by counter-free automata [2] and as languages definable in linear temporal logic [3].
All star-free languages are in uniform AC0.
See also
References
- ^ Marcel-Paul Schützenberger (1965). "On finite monoids having only trivial subgroups" (PDF). Information and Computation. 8 (2): 190–194.
- ^ McNaughton, Robert; Papert, Seymour (1971). Counter-free Automata. MIT Press. ISBN 0-262-13076-9.
- ^ Kamp, Johan Antony Willem (1968). Tense Logic and the Theory of Linear Order. University of California at Los Angeles (UCLA).
- Volker Diekert, Paul Gastin (2008). "First-order definable languages". In Jörg Flum, Erich Grädel, Thomas Wilke (ed.). Logic and automata: history and perspectives (PDF). Amsterdam University Press. ISBN 978-90-5356-576-6.
{{cite book}}: Unknown parameter|unused_data=ignored (help)CS1 maint: multiple names: editors list (link)