On the complexity of multi-pushdown games

DOI10.4230/LIPICS.FSTTCS.2020.52MaRDI QIDQ6839850zbMATH OpenFDO

Authors Roland Meyer, Sören van der Wall

Publication date 23 March 2026

Copyright license Creative Commons Attribution 3.0 Unported

Full work available at URL https://doi.org/10.4230/LIPICS.FSTTCS.2020.52

zbMATH Keywords

complexityconcurrencygamesinfinite statemulti-pushdown

Mathematics Subject Classification ID

Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.) (68N30) Theory of computing (68Qxx)

Cites work

• A constraint-based approach to solving games on infinite graphs
• A Deterministic Subexponential Algorithm for Solving Parity Games
• A Finite Semantics of Simply-Typed Lambda Terms for Infinite Runs of Automata
• A model for behavioural properties of higher-order programs
• A Saturation Method for Collapsible Pushdown Systems
• A unifying view on SMT-based software verification
• Alternation
• Automata, logics, and infinite games. A guide to current research
• C-SHORe: a collapsible approach to higher-order verification
• Domains for Higher-Order Games
• Finitary semantics of linear logic and higher-order model-checking
• From multi to single stack automata
• FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science
• Games on Higher Order Multi-stack Pushdown Systems
• Games on Multi-stack Pushdown Systems
• Global model checking of ordered multi-pushdown systems
• Graph structure and monadic second-order logic. A language-theoretic approach
• scientific article; zbMATH DE number 3467028 (Why is no real title available?)
• scientific article; zbMATH DE number 1500523 (Why is no real title available?)
• scientific article; zbMATH DE number 2086664 (Why is no real title available?)
• scientific article; zbMATH DE number 1456956 (Why is no real title available?)
• scientific article; zbMATH DE number 7361952 (Why is no real title available?)
• scientific article; zbMATH DE number 7297868 (Why is no real title available?)
• MSO decidability of multi-pushdown systems via split-width
• MULTI-PUSH-DOWN LANGUAGES AND GRAMMARS
• Nested interpolants
• Pushdown processes: Games and model-checking
• Reachability analysis of pushdown automata: Application to model-checking
• Reachability of multistack pushdown systems with scope-bounded matching relations
• Regular canonical systems
• Revisiting underapproximate reachability for multipushdown systems
• Saturation of Concurrent Collapsible Pushdown Systems
• Saturation-Based Model Checking of Higher-Order Recursion Schemes.
• Succinct progress measures for solving parity games
• Symbolic Backwards-Reachability Analysis for Higher-Order Pushdown Systems
• The tree width of auxiliary storage
• Tools and Algorithms for the Construction and Analysis of Systems
• Types and higher-order recursion schemes for verification of higher-order programs

This page was built for publication: On the complexity of multi-pushdown games

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