License: Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license (CC BY-NC-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2012.124
URN: urn:nbn:de:0030-drops-38538
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2012/3853/
Go to the corresponding LIPIcs Volume Portal

Fijalkow, Nathanael ; Zimmermann, Martin

Cost-Parity and Cost-Streett Games

pdf-format:
13.pdf (0.5 MB)

Abstract

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 as well as the corresponding finitary conditions.

For cost-parity games we show that the first player has positional winning strategies and that determining the winner lies in NP intersection Co-NP. For cost-Streett games we show that the first player has finite-state winning strategies and that determining the winner is EXPTIME-complete. This unifies the complexity results for the classical and finitary variants of these games. Both types of cost games can be solved by solving linearly many instances of their classical variants.

BibTeX - Entry

@InProceedings{fijalkow_et_al:LIPIcs:2012:3853,
  author =	{Nathanael Fijalkow and Martin Zimmermann},
  title =	{{Cost-Parity and Cost-Streett Games}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012) },
  pages =	{124--135},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-47-7},
  ISSN =	{1868-8969},
  year =	{2012},
  volume =	{18},
  editor =	{Deepak D'Souza and Telikepalli Kavitha and Jaikumar Radhakrishnan},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2012/3853},
  URN =		{urn:nbn:de:0030-drops-38538},
  doi =		{10.4230/LIPIcs.FSTTCS.2012.124},
  annote =	{Keywords: Parity Games, Streett Games, Costs, Scoring Functions}
}

Keywords: Parity Games, Streett Games, Costs, Scoring Functions
Collection: IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012)
Issue Date: 2012
Date of publication: 14.12.2012

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI