First-order logic and star-free sets (Q1088982)

In the paper a version of the Thomas theorem on the correspondence between star-free languages and a hierarchy of first-order logic formulas based on the alternation of existential and universal quantifiers is proved. The proof is based on the Straubing hierarchy of aperiodic languages. The main result is generalized to the case of languages with infinite words.