2026-08-17T20:53:10Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:13293 2024-03-06T10:52:03Z ddc:004 open_access

On the Complexity of Multi-Pushdown Games Meyer, Roland van der Wall, Sören concurrency complexity games infinite state multi-pushdown We study the influence of parameters like the number of contexts, phases, and stacks on the complexity of solving parity games over concurrent recursive programs. Our first result shows that k-context games are b-EXPTIME-complete, where b = max{k-2, 1}. This means up to three contexts do not increase the complexity over an analysis for the sequential case. Our second result shows that for ordered k-stack as well as k-phase games the complexity jumps to k-EXPTIME-complete. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Roland Meyer and Sören van der Wall 2020 Is Part Of LIPIcs, Volume 182, 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2020.52 urn:nbn:de:0030-drops-132930 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2020.52 eng https://creativecommons.org/licenses/by/3.0/legalcode