Playing Safe, Ten Years Later
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2022
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866914901486731264 |
|---|---|
| author | Colcombet, Thomas Fijalkow, Nathanaël Horn, Florian |
| author_facet | Colcombet, Thomas Fijalkow, Nathanaël Horn, Florian |
| contents | We consider two-player games over graphs and give tight bounds on the memory size of strategies ensuring safety objectives. More specifically, we show that the minimal number of memory states of a strategy ensuring a safety objective is given by the size of the maximal antichain of left quotients with respect to language inclusion. This result holds for all safety objectives without any regularity assumptions. We give several applications of this general principle. In particular, we characterize the exact memory requirements for the opponent in generalized reachability games, and we prove the existence of positional strategies in games with counters. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2212_12024 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Playing Safe, Ten Years Later Colcombet, Thomas Fijalkow, Nathanaël Horn, Florian Computer Science and Game Theory Formal Languages and Automata Theory We consider two-player games over graphs and give tight bounds on the memory size of strategies ensuring safety objectives. More specifically, we show that the minimal number of memory states of a strategy ensuring a safety objective is given by the size of the maximal antichain of left quotients with respect to language inclusion. This result holds for all safety objectives without any regularity assumptions. We give several applications of this general principle. In particular, we characterize the exact memory requirements for the opponent in generalized reachability games, and we prove the existence of positional strategies in games with counters. |
| title | Playing Safe, Ten Years Later |
| topic | Computer Science and Game Theory Formal Languages and Automata Theory |
| url | https://arxiv.org/abs/2212.12024 |