The Alternation Hierarchy of First-Order Logic on Words is Decidable

Corentin Barloy, Michaël Cadilhac, Charles Paperman +1

We show that for any $i>0$, it is decidable, given a regular language, whether it is expressible in the ${\Sigma }_i[<]$ fragment of first-order logic FO[<]. This settles a question open…