Quantifier alternation for infinite words

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

Thomas Place, Marc Zeitoun, Théo Pierron

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
• Title not available (Why is that?)
• Separating Regular Languages with Two Quantifiers Alternations

Cited In (9)

• Quantifier Alternation for Infinite Words
• Title not available (Why is that?)
• Level Two of the Quantifier Alternation Hierarchy over Infinite Words
• 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
• Somewhat finite approaches to infinite sentences.
• 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)