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 
that do not have consecutive a's can be defined by 
, where Xc denotes the complement of a subset X 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 first-order logic over the less-than relation [2] and as languages definable in linear temporal logic (Kamp).
See also
References
- ^ Schützenberger M.P. (1965). "On Finite monoids having only trivial subgroups". Information and Computation 8 (2): 190–194.
- ^ McNaughton, Robert; Papert S. (1971). Counter-free Automata. MIT Press. ISBN 0-262-13076-9.
|
||||||||||||||||||||||||||||||||||||||||||||||||
 |
This mathematical logic-related article is a stub. You can help Wikipedia by expanding it. |
This entry is from Wikipedia, the leading user-contributed encyclopedia. It may not have been reviewed by professional editors (see full disclaimer)
