The Quantifier Alternation Hierarchy of Synchronous Relations

DOI10.4230/LIPIcs.MFCS.2019.29OpenAlexW2958258072MaRDI QIDQ5092389

Varun Ramanathan, Diego Figueira, Pascal Weil

Publication date: 21 July 2022

Full work available at URL: https://hal.science/hal-02109188

zbMATH Keywords

first-order logiccharacterizationsynchronous relationsquantifier alternationautomatic relations

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Polynomial closure and unambiguous product
• Concatenation hierarchies: new bottle, old wine
• Sets recognized by n-tape automata
• Definable relations and first-order query languages over strings
• An Introduction to Finite Automata and their Connection to Logic
• Going Higher in the First-Order Quantifier Alternation Hierarchy on Words
• CONCUR 2004 - Concurrency Theory
• On finite monoids having only trivial subgroups
• Ordering by Divisibility in Abstract Algebras

This page was built for publication: The Quantifier Alternation Hierarchy of Synchronous Relations