Going Higher in First-Order Quantifier Alternation Hierarchies on Words
Thomas Place, Marc Zeitoun · Journal of the ACM · 2019
We investigate quantifier alternation hierarchies in first-order logic on finite words. Levels in these hierarchies are defined by counting the number of quantifier alternations in formulas. We prove that one can decide membership of a regular language in the levels BΣ 2 (finite Boolean combinations of formulas having only one alternation) and Σ 3 (formulas having only two alternations and beginning with an existential block). Our proofs work by considering a deeper problem, called separation , which, once solved for lower levels, allows us to solve membership for higher levels.