Infinite-state games with finitary conditions

Chatterjee, Krishnendu and Fijalkow, Nathanaël (2013) Infinite-state games with finitary conditions. In: EACSL: European Association for Computer Science Logic, September 2 - 5, 2013, Torino, Italy.

[img] Text
ChKr_Infinite-state_games_2013_17.pdf - Published Version
Available under License Creative Commons Attribution.
[IST-2016-624-v1+1]
Download (534Kb)
Official URL: http://dx.doi.org/10.4230/LIPIcs.CSL.2013.181

Abstract

We study two-player zero-sum games over infinite-state graphs equipped with ω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 ω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.

Item Type: Conference or Workshop Item (Paper)
Uncontrolled Keywords: synthesis, Two-player games, Pushdown games, Bounds in omega-regularity, Infinite-state systems
Subjects: 000 Computer science, knowledge & general works > 000 Computer science, knowledge & systems
Research Group: Chatterjee Group
SWORD Depositor: Sword Import User
Depositing User: Sword Import User
Date Deposited: 20 Jul 2016 15:33
Last Modified: 05 Sep 2017 14:17
URI: https://repository.ist.ac.at/id/eprint/624

Actions (login required)

View Item View Item