Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH scholarly article en Meyer, Roland; van der Wall, Sören https://www.dagstuhl.de/lipics License: Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)
when quoting this document, please refer to the following
DOI:
URN: urn:nbn:de:0030-drops-132930
URL:

;

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


DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI