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: https://drops.dagstuhl.de/opus/volltexte/2013/4197/
Chatterjee, Krishnendu ; Fijalkow, Nathanaël
Infinite-state games with finitary conditions
| pdf-format: |
|
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 | |
| Seminar: | Computer Science Logic 2013 (CSL 2013) | |
| Issue date: | 2013 | |
| Date of publication: | 02.09.2013 |
