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, boolean operators and concatenation but no Kleene star. For instance, the language of words over the alphabet {a,b} that do not have consecutive a's can be defined by 
.
Marcel-Paul Schützenberger characterized star-free languages as those with aperiodic syntactic monoids. They can also be characterized logically as languages definable in FO[<], the first-order logic over the less-than relation but without the BIT predicate (McNaughton and Papert) and as languages definable in linear temporal logic (Kamp).
[edit] See also
[edit] References
- Schützenberger M.P. (1965). "On Finite monoids having only trivial subgroups". Information and Computation 8 (2): 190-194.
- McNaughton R. and Papert S. (1971). Counter-free Automata. MIT Press. ISBN 0-262-13076-9.
 |
This mathematics-related article is a stub. You can help Wikipedia by expanding it. |
