Going higher in the First-order Quantifier Alternation Hierarchy on Words

2014/04/27 by Thomas Place, Place, Thomas, Marc Zeitoun +1 · 1 voice · 1 citation
Biochemistry, Genetics and Molecular Biology · Computer Science · #Algorithms and Data Compression #DNA and Biological Computing #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #Logic in Computer Science (cs.LO) #semigroups and automata theory

paper · doi:10.48550/arxiv.1404.6832

openalex publication_date 2014/04/27 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We investigate the quantifier alternation hierarchy in first-order logic on finite words. Levels in this hierarchy are defined by counting the number of quantifier alternations in formulas. We prove that one can decide membership of a regular language to the levels BΣ₂ (boolean combination of formulas having only 1 alternation) and Σ₃ (formulas having only 2 alternations beginning with an existential block). Our proof works by considering a deeper problem, called separation, which, once solved for lower levels, allows us to solve membership for higher levels.

Cited by

• A Transfer Theorem for the Separation Problem

Discussions

• $ % \leq \renewcommand{\leq}{\leqslant} % mathcal \newcommand{\cB}{\mathcal{B}} \newcommand{\cP}{\mathcal{P}} \newcommand{\cPd}{\mathcal{P}^{\downarrow}} \newcommand{\cPu}{\mathcal{P}^{\uparrow}} \new [stackexchange, 4 points]

Related

• Going Higher in First-Order Quantifier Alternation Hierarchies on Words
• Quantifier Alternation for Infinite Words
• Level Two of the Quantifier Alternation Hierarchy over Infinite Words
• Nesting negations in FO2 over infinite words
• Quantifier Alternation in Two-Variable First-Order Logic with Successor Is Decidable