This page uses content from Wikipedia and is licensed under CC BY-SA.

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 that do not have consecutive a's can be defined by , where denotes the complement of a subset of . The condition is equivalent to having generalized star height zero.

An example of a regular language which is not star-free is .^{[2]}

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

All star-free languages are in uniform AC^{0}.

**^**Lawson (2004) p.235**^**Arto Salomaa (1981).*Jewels of Formal Language Theory*. Computer Science Press. p. 53. ISBN 978-0-914894-69-8.**^**Marcel-Paul Schützenberger (1965). "On finite monoids having only trivial subgroups" (PDF).*Information and Computation*.**8**(2): 190–194. doi:10.1016/s0019-9958(65)90108-7.**^**Lawson (2004) p.262**^**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.**^**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.**^**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*(PDF). Amsterdam University Press. ISBN 978-90-5356-576-6.

P ≟ NP | This theoretical computer science–related article is a stub. You can help Wikipedia by expanding it. |