elib
DLR-Header
DLR-Logo -> http://www.dlr.de
DLR Portal Home | Impressum | Datenschutz | Kontakt | English
Schriftgröße: [-] Text [+]

Parity games with weights

Schewe, Sven und Weinert, Alexander und Zimmermann, Martin (2019) Parity games with weights. Logical Methods in Computer Science, 15 (3), 20:1-20:50. Technische Universität Braunschweig. doi: 10.23638/LMCS-15(3:20)2019. ISSN 1860-5974.

[img] PDF - Postprintversion (akzeptierte Manuskriptversion)
616kB

Offizielle URL: https://lmcs.episciences.org/5705

Kurzfassung

Quantitative extensions of parity games have recently attracted significant interest. These extensions include parity games with energy and payoff conditions as well as finitary parity games and their generalization to parity games with costs. Finitary parity games enjoy a special status among these extensions, as they offer a native combination of the qualitative and quantitative aspects in infinite games: The quantitative aspect of finitary parity games is a quality measure for the qualitative aspect, as it measures the limit superior of the time it takes to answer an odd color by a larger even one. Finitary parity games have been extended to parity games with costs, where each transition is labeled with a nonnegative weight that reflects the costs incurred by taking it. We lift this restriction and consider parity games with costs with arbitrary integer weights. We show that solving such games is in NP and coNP, the signature complexity for games of this type. We also show that the protagonist has finite-state winning strategies, and provide tight pseudo-polynomial bounds for the memory he needs to win the game. Naturally, the antagonist may need infinite memory to win. Moreover, we present tight bounds on the quality of winning strategies for the protagonist. Furthermore, we investigate the problem of determining, for a given threshold b, whether the protagonist has a strategy of quality at most b and show this problem to be EXPTIME-complete. The protagonist inherits the necessity of exponential memory for implementing such strategies from the special case of finitary parity games.

elib-URL des Eintrags:https://elib.dlr.de/131260/
Dokumentart:Zeitschriftenbeitrag
Titel:Parity games with weights
Autoren:
AutorenInstitution oder E-Mail-AdresseAutoren-ORCID-iDORCID Put Code
Schewe, Svensven.schewe (at) liverpool.ac.ukhttps://orcid.org/0000-0002-9093-9518NICHT SPEZIFIZIERT
Weinert, Alexanderalexander.weinert (at) dlr.dehttps://orcid.org/0000-0001-8143-246XNICHT SPEZIFIZIERT
Zimmermann, Martinmartin.zimmermann (at) liverpool.ac.ukhttps://orcid.org/0000-0002-8038-2453NICHT SPEZIFIZIERT
Datum:13 August 2019
Erschienen in:Logical Methods in Computer Science
Referierte Publikation:Ja
Open Access:Ja
Gold Open Access:Ja
In SCOPUS:Ja
In ISI Web of Science:Ja
Band:15
DOI:10.23638/LMCS-15(3:20)2019
Seitenbereich:20:1-20:50
Verlag:Technische Universität Braunschweig
ISSN:1860-5974
Status:veröffentlicht
Stichwörter:Informatik, Spieltheorie, Quantitative Spiele
HGF - Forschungsbereich:Luftfahrt, Raumfahrt und Verkehr
HGF - Programm:Raumfahrt
HGF - Programmthema:Technik für Raumfahrtsysteme
DLR - Schwerpunkt:Raumfahrt
DLR - Forschungsgebiet:R SY - Technik für Raumfahrtsysteme
DLR - Teilgebiet (Projekt, Vorhaben):R - Vorhaben SISTEC (alt)
Standort: Köln-Porz
Institute & Einrichtungen:Institut für Simulations- und Softwaretechnik
Institut für Simulations- und Softwaretechnik > Verteilte Systeme und Komponentensoftware
Hinterlegt von: Weinert, Alexander
Hinterlegt am:28 Nov 2019 12:10
Letzte Änderung:28 Nov 2019 12:10

Nur für Mitarbeiter des Archivs: Kontrollseite des Eintrags

Blättern
Suchen
Hilfe & Kontakt
Informationen
electronic library verwendet EPrints 3.3.12
Gestaltung Webseite und Datenbank: Copyright © Deutsches Zentrum für Luft- und Raumfahrt (DLR). Alle Rechte vorbehalten.