Abstract
We compare games under delayed control and delay games, two types of infinite games modelling asynchronicity in reactive synthesis. Our main result, the interreducibility of the existence of sure winning strategies for the protagonist, allows to transfer known complexity results and bounds on the delay from delay games to games under delayed control, for which no such results had been known. We furthermore analyze existence of randomized strategies that win almost surely, where this correspondence between the two types of games breaks down.
| Original language | English |
|---|---|
| Journal | Electronic Proceedings in Theoretical Computer Science, EPTCS |
| Volume | 390 |
| Pages (from-to) | 220-235 |
| Number of pages | 16 |
| ISSN | 2075-2180 |
| DOIs | |
| Publication status | Published - 30 Sept 2023 |
| Event | 14th International Symposium on Games, Automata, Logics, and Formal Verification, G and ALF 2023 - Udine, Italy Duration: 18 Sept 2023 → 20 Sept 2023 |
Conference
| Conference | 14th International Symposium on Games, Automata, Logics, and Formal Verification, G and ALF 2023 |
|---|---|
| Country/Territory | Italy |
| City | Udine |
| Period | 18/09/2023 → 20/09/2023 |
Bibliographical note
Publisher Copyright:© M. Fränzle, S. Winter & M. Zimmermann.