License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CSL.2013.181
URN: urn:nbn:de:0030-drops-41970
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2013/4197/
Go to the corresponding LIPIcs Volume Portal

Chatterjee, Krishnendu ; Fijalkow, Nathanaël

Infinite-state games with finitary conditions

pdf-format:
17.pdf (0.5 MB)

Abstract

We study two-player zero-sum games over infinite-state graphs equipped with omega-B and finitary conditions.
Our first contribution is about the strategy complexity, i.e the memory required for winning strategies: we prove that over general infinite-state graphs, memoryless strategies are sufficient for finitary Büchi, and finite-memory suffices for finitary parity games.
We then study pushdown games with boundedness conditions, with two contributions. First we prove a collapse result for pushdown games with omega-B-conditions, implying the decidability of solving these games. Second we consider pushdown games with finitary parity along with stack boundedness conditions, and show that solving these games is EXPTIME-complete.

BibTeX - Entry

@InProceedings{chatterjee_et_al:LIPIcs:2013:4197,
  author =	{Krishnendu Chatterjee and Nathana{\"e}l Fijalkow},
  title =	{{Infinite-state games with finitary conditions}},
  booktitle =	{Computer Science Logic 2013 (CSL 2013)},
  pages =	{181--196},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-60-6},
  ISSN =	{1868-8969},
  year =	{2013},
  volume =	{23},
  editor =	{Simona Ronchi Della Rocca},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2013/4197},
  URN =		{urn:nbn:de:0030-drops-41970},
  doi =		{10.4230/LIPIcs.CSL.2013.181},
  annote =	{Keywords: Two-player games, Infinite-state systems, Pushdown games, Bounds in omega-regularity, Synthesis}
}

Keywords: Two-player games, Infinite-state systems, Pushdown games, Bounds in omega-regularity, Synthesis
Collection: Computer Science Logic 2013 (CSL 2013)
Issue Date: 2013
Date of publication: 02.09.2013

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