A regular language

Regular language

In theoretical computer science and formal language theory, a regular language is a formal language that can be expressed using regular expression....

 is said to be star-free if it can be described by a regular expression

Regular expression

In computing, a regular expression provides a concise and flexible means for "matching" strings of text, such as particular characters, words, or patterns of characters. Abbreviations for "regular expression" include "regex" and "regexp"...

 constructed from the letters of the alphabet, the empty set

Empty set

In mathematics, and more specifically set theory, the empty set is the unique set having no elements; its size or cardinality is zero. Some axiomatic set theories assure that the empty set exists by including an axiom of empty set; in other theories, its existence can be deduced...

 symbol, all boolean operators – including complementation

Complement (set theory)

In set theory, a complement of a set A refers to things not in , A. The relative complement of A with respect to a set B, is the set of elements in B but not in A...

 – and concatenation

Concatenation

In computer programming, string concatenation is the operation of joining two character strings end-to-end. For example, the strings "snow" and "ball" may be concatenated to give "snowball"...

 but no Kleene star

Kleene star

In mathematical logic and computer science, the Kleene star is a unary operation, either on sets of strings or on sets of symbols or characters. The application of the Kleene star to a set V is written as V*...

. 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

Marcel-Paul Schützenberger

Marcel-Paul "Marco" Schützenberger was a French mathematician and Doctor of Medicine. His work had impact across the fields of formal language, combinatorics, and information theory...

 characterized star-free languages as those with aperiodic

Aperiodic monoid

In mathematics, an aperiodic semigroup is a semigroup S such that for every x ∈ S, there exists a nonnegative integer n such thatxn = xn + 1.An aperiodic monoid is an aperiodic semigroup which is a monoid...

 syntactic monoid

Syntactic monoid

In mathematics and computer science, the syntactic monoid M of a formal language L is the smallest monoid that recognizes the language L.-Syntactic quotient:...

s . They can also be characterized logically as languages definable in FO[<], the monadic first-order logic

First-order logic

First-order logic is a formal logical system used in mathematics, philosophy, linguistics, and computer science. It goes by many names, including: first-order predicate calculus, the lower predicate calculus, quantification theory, and predicate logic...

 over the natural numbers with the less-than relation, as the languages acceptable by counter-free automata and as languages definable in linear temporal logic

Linear temporal logic

In logic, Linear temporal logic is a modal temporal logic with modalities referring to time. In LTL, one can encode formulae about the future of paths such as that a condition will eventually be true, that a condition will be true until another fact becomes true, etc. It is a fragment of the more...

.