Going Higher in First-Order Quantifier Alternation Hierarchies on Words

DOI10.1145/3303991MaRDI QIDQ5244385zbMATH OpenOpenAlexWikidataFDO

Authors Thomas Place, Marc Zeitoun

Publication date 21 November 2019

Published in Journal of the ACM (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1707.05696

zbMATH Keywords

decidable characterizationdot-depth hierarchyfirst-order logiclogical hierarchiesmembership problemquantifier alternationregular languagesseparation problemStraubing-Thérien hierarchy

Mathematics Subject Classification ID

Decidability of theories and sets of sentences (03B25) Model theory of finite structures (03C13) Automata and formal grammars in connection with logical questions (03D05)

Abstract: 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 $mathcalB{Sigma}_2$ (finite boolean combinations of formulas having only one alternation) and ${Sigma}_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.

Recommendations

• Going Higher in the First-Order Quantifier Alternation Hierarchy on Words
• scientific article; zbMATH DE number 408810
• Level two of the quantifier alternation hierarchy over infinite words
• Level Two of the Quantifier Alternation Hierarchy over Infinite Words
• On FO 2 Quantifier Alternation over Words
• Quantifier hierarchies over the first-order definable tree languages
• The Quantifier Alternation Hierarchy of Synchronous Relations
• On the complexity of free word orders
• Quantifier alternation in first-order formulas with infinite spectra
• On the strictness of the quantifier structure hierarchy in first-order logic

Cited in

(22)

• Level two of the quantifier alternation hierarchy over infinite words
• Characterizing level one in group-based concatenation hierarchies
• Difference hierarchies and duality with an application to formal languages
• Quantifier alternation for infinite words
• Alternation hierarchies of first order logic with regular predicates
• Quantifier alternation in two-variable first-order logic with successor is decidable
• scientific article; zbMATH DE number 408810 (Why is no real title available?)
• The covering problem
• Separating regular languages with two quantifiers alternations
• scientific article; zbMATH DE number 1396734 (Why is no real title available?)
• The Quantifier Alternation Hierarchy of Synchronous Relations
• Separation for dot-depth two
• Going Higher in the First-Order Quantifier Alternation Hierarchy on Words
• Level Two of the Quantifier Alternation Hierarchy over Infinite Words
• Positive First-order Logic on Words and Graphs
• First-order separation over countable ordinals
• The omega-reducibility of pseudovarieties of ordered monoids representing low levels of concatenation hierarchies
• All about unambiguous polynomial closure
• The regular languages of first-order logic with one alternation
• A generic characterization of generalized unary temporal logic and two-variable first-order logic
• Dot-depth three, return of the j-class
• A purely algebraic proof of the omega-reducibility of pseudovarieties representing low half levels of concatenation hierarchies

This page was built for publication: Going Higher in First-Order Quantifier Alternation Hierarchies on Words

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5244385)