Quantifier Alternation for Infinite Words

DOI10.1007/978-3-662-49630-5_14zbMath1476.03051arXiv1511.09011OpenAlexW2263935218MaRDI QIDQ2811342

Thomas Place, Théo Pierron, Marc Zeitoun

Publication date: 10 June 2016

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

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

Mathematics Subject Classification ID

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

Related Items (3)

Level two of the quantifier alternation hierarchy over infinite words ⋮ Level Two of the Quantifier Alternation Hierarchy over Infinite Words ⋮ Quantifier Alternation for Infinite Words

Cites Work

• Fragments of first-order logic over infinite words
• The dot-depth hierarchy of star-free languages is infinite
• Polynomial closure and unambiguous product
• Separating Regular Languages with First-Order Logic
• Quantifier Alternation for Infinite Words
• Separating Regular Languages by Piecewise Testable and Unambiguous Languages
• Weak Second‐Order Arithmetic and Finite Automata
• Decision Problems of Finite Automata Design and Related Arithmetics
• Separating Regular Languages with Two Quantifiers Alternations
• Going Higher in the First-Order Quantifier Alternation Hierarchy on Words
• Efficient Separability of Regular Languages by Subsequences and Suffixes
• On finite monoids having only trivial subgroups
• The Common Fragment of ACTL and LTL
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Quantifier Alternation for Infinite Words