Nathanaël Fijalkow ; Martin Zimmermann - Parity and Streett Games with Costs

lmcs:794 - Logical Methods in Computer Science, June 26, 2014, Volume 10, Issue 2 - https://doi.org/10.2168/LMCS-10(2:14)2014
Parity and Streett Games with Costs

Authors: Nathanaël Fijalkow ORCID-iD; Martin Zimmermann ORCID-iD

    We consider two-player games played on finite graphs equipped with costs on edges and introduce two winning conditions, cost-parity and cost-Streett, which require bounds on the cost between requests and their responses. Both conditions generalize the corresponding classical omega-regular conditions and the corresponding finitary conditions. For parity games with costs we show that the first player has positional winning strategies and that determining the winner lies in NP and coNP. For Streett games with costs we show that the first player has finite-state winning strategies and that determining the winner is EXPTIME-complete. The second player might need infinite memory in both games. Both types of games with costs can be solved by solving linearly many instances of their classical variants.


    Volume: Volume 10, Issue 2
    Published on: June 26, 2014
    Accepted on: June 25, 2015
    Submitted on: June 5, 2013
    Keywords: Computer Science - Logic in Computer Science,Computer Science - Computational Complexity,Computer Science - Computer Science and Game Theory
    Fundings :
      Source : OpenAIRE Research Graph
    • Expressive Power of Tree Logics; Funder: European Commission; Code: 239850
    • Games and Automata for Logic Extensions; Funder: European Commission; Code: 259454

    Linked data

    Source : ScholeXplorer IsReferencedBy ARXIV 1709.04854
    Source : ScholeXplorer IsReferencedBy DOI 10.1007/s00236-019-00345-7
    Source : ScholeXplorer IsReferencedBy DOI 10.4230/lipics.csl.2018.34
    Source : ScholeXplorer IsReferencedBy DOI 10.48550/arxiv.1709.04854
    • 10.4230/lipics.csl.2018.34
    • 10.1007/s00236-019-00345-7
    • 10.1007/s00236-019-00345-7
    • 10.1007/s00236-019-00345-7
    • 1709.04854
    • 10.48550/arxiv.1709.04854
    Synthesizing optimally resilient controllers
    Neider, Daniel ; Weinert, Alexander ; Zimmermann, Martin ;

    17 Documents citing this article

    Share

    Consultation statistics

    This page has been seen 504 times.
    This article's PDF has been downloaded 239 times.