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.
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: |
| ||||||||||||
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: |
| ||||||||||||
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