Ramsey quantifiers over automatic structures: complexity and applications to verification

DOI10.1145/3531130.3533346MaRDI QIDQ6649458zbMATH OpenFDO

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

Publication date 6 December 2024

Full work available at URL https://doi.org/10.1145/3531130.3533346

zbMATH Keywords

automatic structuresRamsey quantifiermonadic decomposabilityrecurrent reachability

Mathematics Subject Classification ID

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

Cites work

• scientific article; zbMATH DE number 1033559 (Why is no real title available?)
• scientific article; zbMATH DE number 1088208 (Why is no real title available?)
• scientific article; zbMATH DE number 1948151 (Why is no real title available?)
• scientific article; zbMATH DE number 1903380 (Why is no real title available?)
• scientific article; zbMATH DE number 7561596 (Why is no real title available?)
• scientific article; zbMATH DE number 7058469 (Why is no real title available?)
• A regularity test for pushdown machines
• Accelerating tree-automatic relations
• Algorithmic metatheorems for decidable LTL model checking over infinite systems
• Automata Presenting Structures: A Survey of the Finite String Case
• Automata, Languages and Programming
• Automated Technology for Verification and Analysis
• Automatic structures: twenty years later
• Bounded Regular Sets
• CONCUR 2004 - Concurrency Theory
• Decision problems among the main subfamilies of rational relations
• Finite presentations of infinite structures: Automata and interpretations
• Haskell overloading is DEXPTIME-complete
• Is Ramsey's theorem omega-automatic?
• Magidor-Malitz reflection
• Monadic decomposition
• Reachability problems on regular ground tree rewriting graphs
• Recurrent Reachability Analysis in Regular Model Checking
• Regularity and Related Problems for Deterministic Pushdown Automata
• Simulating alternating tree automata by nondeterministic automata: New results and new proofs of the theorems of Rabin, McNaughton and Safra
• Some natural decision problems in automatic graphs
• The complexity of XPath query evaluation and XML typing
• Transition Graphs of Rewriting Systems over Unranked Trees
• Variable independence for first-order definable constraints

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

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