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

Quantitative Reductions and Vertex-Ranked Infinite Games

Weinert, Alexander (2020) Quantitative Reductions and Vertex-Ranked Infinite Games. Information and Computation, 278, Seite 104596. Elsevier. doi: 10.1016/j.ic.2020.104596. ISSN 0890-5401.

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

Offizielle URL: https://www.sciencedirect.com/science/article/abs/pii/S0890540120300845

Kurzfassung

We introduce quantitative reductions, a novel technique for structuring the space of quantitative games and solving them that does not rely on a reduction to qualitative games. We show that such reductions exhibit the same desirable properties as their qualitative counterparts and additionally retain the optimality of solutions. Moreover, we introduce vertex-ranked games as a general-purpose target for quantitative reductions and show how to solve them. In such games, the value of a play is determined only by a qualitative winning condition and a ranking of the vertices. We provide quantitative reductions of quantitative request-response games to vertex-ranked games, thus showing ExpTime-completeness of solving the former games. Moreover, we reduce quantitative Muller games to vertex-ranked games, yielding a new proof of ExpTime-membership of the problem of solving the former games. Furthermore, we exhibit the usefulness and flexibility of vertex-ranked games by showing how to use such games to compute fault-resilient strategies for safety specifications. This work lays the foundation for a general study of fault-resilient strategies for more complex winning conditions.

elib-URL des Eintrags:https://elib.dlr.de/134511/
Dokumentart:Zeitschriftenbeitrag
Titel:Quantitative Reductions and Vertex-Ranked Infinite Games
Autoren:
AutorenInstitution oder E-Mail-AdresseAutoren-ORCID-iDORCID Put Code
Weinert, AlexanderAlexander.Weinert (at) dlr.dehttps://orcid.org/0000-0001-8143-246XNICHT SPEZIFIZIERT
Datum:12 Juni 2020
Erschienen in:Information and Computation
Referierte Publikation:Ja
Open Access:Ja
Gold Open Access:Nein
In SCOPUS:Ja
In ISI Web of Science:Ja
Band:278
DOI:10.1016/j.ic.2020.104596
Seitenbereich:Seite 104596
Herausgeber:
HerausgeberInstitution und/oder E-Mail-Adresse der HerausgeberHerausgeber-ORCID-iDORCID Put Code
Orlandini, AndreaItalian National Research Council – CNR, Italy; andrea.orlandini (at) istc.cnr.itNICHT SPEZIFIZIERTNICHT SPEZIFIZIERT
Zimmermann, Martinmartin.zimmermann (at) liverpool.ac.ukhttps://orcid.org/0000-0002-8038-2453NICHT SPEZIFIZIERT
Verlag:Elsevier
ISSN:0890-5401
Status:veröffentlicht
Stichwörter: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:17 Jun 2020 11:10
Letzte Änderung:30 Okt 2023 12:45

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.