In theoretical computer science and formal language theory, 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 word, the empty set symbol, all boolean operators – including complementation – and concatenation but no Kleene star. The condition is equivalent to having generalized star height zero. For instance, the language \Sigma^* of all finite words over an alphabet \Sigma can be shown to be star-free by taking the complement of the empty set,. Then, the language of words over the alphabet {a,,b} that do not have consecutive a's can be defined as, first constructing the language of words consisting of aa with an arbitrary prefix and suffix, and then taking its complement, which must be all words which do not contain the substring aa. An example of a regular language which is not star-free is (aa)^, i.e. the language of strings consisting of an even number of "a". For (ab)^ where a \neq b, the language can be defined as, taking the set of all words and removing from it words starting with b, ending in a or containing aa or bb. However, when a = b, this definition does not create (aa)^*. 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 natural numbers with the less-than relation, as the counter-free languages and as languages definable in linear temporal logic. All star-free languages are in uniform AC0.