Quantifier alternation for infinite words

DOI10.1007/978-3-662-49630-5_14zbMATH Open1476.03051arXiv1511.09011OpenAlexW2263935218MaRDI QIDQ2811342FDOQ2811342

Authors: Théo Pierron, Thomas Place, Marc Zeitoun 

Publication date: 10 June 2016

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Abstract: We investigate the expressive power of quantifier alternation hierarchy of first-order logic over words. This hierarchy includes the classes ${Sigma}_i$ (sentences having at most $i$ blocks of quantifiers starting with an $exists$) and $mathcalB{Sigma}_i$ (Boolean combinations of ${Sigma}_i$ sentences). So far, this expressive power has been effectively characterized for the lower levels only. Recently, a breakthrough was made over finite words, and decidable characterizations were obtained for $mathcalB{Sigma}_2$ and ${Sigma}_3$, by relying on a decision problem called separation, and solving it for ${Sigma}_2$. The contribution of this paper is a generalization of these results to the setting of infinite words: we solve separation for ${Sigma}_2$ and ${Sigma}_3$, and obtain decidable characterizations of $mathcalB{Sigma}_2$ and ${Sigma}_3$ as consequences.

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

Recommendations

• Going Higher in the First-Order Quantifier Alternation Hierarchy on Words
• Going Higher in First-Order Quantifier Alternation Hierarchies on Words
• Level Two of the Quantifier Alternation Hierarchy over Infinite Words
• Level two of the quantifier alternation hierarchy over infinite words
• Separating regular languages with two quantifiers alternations

Mathematics Subject Classification ID

Automata and formal grammars in connection with logical questions (03D05) Logic in computer science (03B70) Complexity of computation (including implicit computational complexity) (03D15)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• On finite monoids having only trivial subgroups
• Weak Second‐Order Arithmetic and Finite Automata
• Decision Problems of Finite Automata Design and Related Arithmetics
• Title not available (Why is that?)
• Polynomial closure and unambiguous product
• Separating regular languages with first-order logic
• Going Higher in the First-Order Quantifier Alternation Hierarchy on Words
• Efficient separability of regular languages by subsequences and suffixes
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Fragments of first-order logic over infinite words
• The Common Fragment of ACTL and LTL
• The dot-depth hierarchy of star-free languages is infinite
• Title not available (Why is that?)
• Separating regular languages by piecewise testable and unambiguous languages
• Quantifier alternation for infinite words
• Separation and the successor relation
• Separating regular languages with two quantifiers alternations

Cited In (12)

• Title not available (Why is that?)
• Level Two of the Quantifier Alternation Hierarchy over Infinite Words
• Rankers over infinite words (extended abstract)
• Separating regular languages with two quantifiers alternations
• Level two of the quantifier alternation hierarchy over infinite words
• Anti-powers in infinite words
• Going Higher in the First-Order Quantifier Alternation Hierarchy on Words
• Expressive power of existential first-order sentences of Büchi's sequential calculus
• Boundedness in languages of infinite words
• Somewhat finite approaches to infinite sentences.
• Quantifier alternation for infinite words
• Disquotation and infinite conjunctions

This page was built for publication: Quantifier alternation for infinite words

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