Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2020.52
URN: urn:nbn:de:0030-drops-132930
URL: https://drops.dagstuhl.de/opus/volltexte/2020/13293/
Meyer, Roland ; van der Wall, Sören
On the Complexity of Multi-Pushdown Games
| pdf-format: |
|
Abstract
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.
BibTeX - Entry
@InProceedings{meyer_et_al:LIPIcs:2020:13293,
author = {Roland Meyer and S{\"o}ren van der Wall},
title = {{On the Complexity of Multi-Pushdown Games}},
booktitle = {40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020)},
pages = {52:1--52:35},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-174-0},
ISSN = {1868-8969},
year = {2020},
volume = {182},
editor = {Nitin Saxena and Sunil Simon},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/13293},
URN = {urn:nbn:de:0030-drops-132930},
doi = {10.4230/LIPIcs.FSTTCS.2020.52},
annote = {Keywords: concurrency, complexity, games, infinite state, multi-pushdown}
}
| Keywords: | concurrency, complexity, games, infinite state, multi-pushdown | |
| Seminar: | 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020) | |
| Issue date: | 2020 | |
| Date of publication: | 04.12.2020 |
