Ramsey quantifiers over automatic structures: complexity and applications to verification

DOI10.1145/3531130.3533346MaRDI QIDQ6649458

Moses Ganardi, Pascal Bergsträßer, Georg Zetzsche, Anthony Widjaja Lin

Publication date: 6 December 2024

zbMATH Keywords

automatic structuresRamsey quantifiermonadic decomposabilityrecurrent reachability

Mathematics Subject Classification ID

Logic in computer science (03B70) Specification and verification (program logics, model checking, etc.) (68Q60)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Magidor-Malitz reflection
• Simulating alternating tree automata by nondeterministic automata: New results and new proofs of the theorems of Rabin, McNaughton and Safra
• Haskell overloading is DEXPTIME-complete
• Finite presentations of infinite structures: Automata and interpretations
• Reachability problems on regular ground tree rewriting graphs
• Accelerating tree-automatic relations
• Is Ramsey's theorem omega-automatic?
• Decision problems among the main subfamilies of rational relations
• Automata Presenting Structures: A Survey of the Finite String Case
• Transition Graphs of Rewriting Systems over Unranked Trees
• The complexity of XPath query evaluation and XML typing
• Algorithmic Metatheorems for Decidable LTL Model Checking over Infinite Systems
• Some natural decision problems in automatic graphs
• Regularity and Related Problems for Deterministic Pushdown Automata
• Monadic Decomposition
• Automatic Structures
• Variable independence for first-order definable constraints
• CONCUR 2004 - Concurrency Theory
• Automated Technology for Verification and Analysis
• Recurrent Reachability Analysis in Regular Model Checking
• Bounded Regular Sets
• A regularity test for pushdown machines
• Automata, Languages and Programming

This page was built for publication: Ramsey quantifiers over automatic structures: complexity and applications to verification