First-order definable languages ∗
Volker Diekert, Paul Gastin · 2008
We give an essentially self-contained presentation of some principal results for first-order definable languages over finite and infinite words. We introduce the notion of a counter-free Büchi automaton; and we relate counter-freeness to aperiodicity and to the notion of very weak alternation. We also show that aperiodicity of a regular ∞-language can be decided in polynomial space, if the language is specified by some Büchi automaton. 1