Via aperiod syntact monoids

Marcel-Paul Schützenberger characterized star-free languages as those with aperiodic syntactic monoids.^[4][5] Said differently, they are characterised as languages accepted by some aperiodic finite-state automaton (known as counter-free languages)^[6].

Logical characterisation

They can also be characterized logically as languages definable in FO[<], the first-order logic over the natural numbers with the less-than relation^[7]. First-order variables denote positions in words and < means that a position is strictly before another one. Here are some examples.

• The language ${\displaystyle \Sigma ^{*}}$(all words) is captured by the tautology ${\displaystyle \top }$ (no constraints on the words)
• The language of that have no consecutive a's is defined by the FO[<] formula ${\displaystyle \forall x\forall y\,{\Big (}{\big (}a(x)\land x<y\land \neg \exists z(x<z\land z<y){\big )}\implies \neg a(y){\Big )}}$ meaning for all positions ${\displaystyle x}$ and ${\displaystyle y}$, if ${\displaystyle x}$ contains letter ${\displaystyle a}$ and if ${\displaystyle y}$ is the position after ${\displaystyle x}$ (${\displaystyle y}$ is after ${\displaystyle x}$ but there is no positions in between ${\displaystyle x}$ and ${\displaystyle y}$), then there is ${\displaystyle y}$ does not contain letter ${\displaystyle a}$.

They can also be characterized by formulas in linear temporal logic.^[8] Here are some examples.

• Again, The language ${\displaystyle \Sigma ^{*}}$ is captured by the tautology ${\displaystyle \top }$
• The language of that have no consecutive a's is defined by the formula in linear temporal logic ${\displaystyle G(a\rightarrow X\lnot a)}$ where is the meaning is as follows: always (operator ${\displaystyle G}$), if there is letter ${\displaystyle a}$ then at the next step (operator ${\displaystyle X}$) there is no letter ${\displaystyle a}$.

Membership

All star-free languages are in uniform AC⁰. More precisely, given a star-free language ${\displaystyle L}$, deciding whether a word belongs to ${\displaystyle L}$ is in uniform AC⁰.

Non-emptiness

It takes non-elementary time to decide whether a star-free language over two letters is empty. More precisely, the non-emptiness problem of starfree language is defined as follows.

• Input: a string in the symbols of ${\displaystyle \{a,\,b\}}$, empty set, concatenation, union, intersection, and complement.
• Output: Whether this language contains any element.

This problem is decidable, but only in nonelementary time. As immediate corollaries, it is decidable but nonelementary to decide whether two starfree languages are equal, are disjoint, or contain one another.^[9]