Infinite-state games with finitary conditions

Authors Krishnendu Chatterjee, Nathanaël Fijalkow



PDF
Thumbnail PDF

File

LIPIcs.CSL.2013.181.pdf
  • Filesize: 0.52 MB
  • 16 pages

Document Identifiers

Author Details

Krishnendu Chatterjee
Nathanaël Fijalkow

Cite AsGet 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

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.
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
    PDF Downloads
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail