Infinite-state games with finitary conditions

Chatterjee, Krishnendu; Fijalkow, Nathanaël

doi:10.4230/LIPIcs.CSL.2013.181

Document

Infinite-state games with finitary conditions

Authors Krishnendu Chatterjee, Nathanaël Fijalkow

Part of: Volume: Computer Science Logic 2013 (CSL 2013)
Part of: Series: Leibniz International Proceedings in Informatics (LIPIcs)
Part of: Conference: Computer Science Logic (CSL)
License: Creative Commons Attribution 3.0 Unported license
Publication Date: 2013-09-02

PDF

File

PDF

LIPIcs.CSL.2013.181.pdf

Filesize: 0.52 MB
16 pages

Document Identifiers

DOI: 10.4230/LIPIcs.CSL.2013.181
URN: urn:nbn:de:0030-drops-41970

Subject Classification

Keywords

Two-player games
Infinite-state systems
Pushdown games
Bounds in omega-regularity
Synthesis

Metrics

Access Statistics
Total Accesses (updated on a weekly basis)

0

Document

0

Metadata

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.

Cite As Get BibTex

Krishnendu Chatterjee and Nathanaël Fijalkow. Infinite-state games with finitary conditions. In Computer Science Logic 2013 (CSL 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 23, pp. 181-196, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013) https://doi.org/10.4230/LIPIcs.CSL.2013.181

Author Details

Krishnendu Chatterjee

Nathanaël Fijalkow

Any Issues?

Feedback on the Current Page

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail