Half-Positional Objectives Recognized by Deterministic Büchi Automata
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2022
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909302698016768 |
|---|---|
| author | Bouyer, Patricia Casares, Antonio Randour, Mickael Vandenhove, Pierre |
| author_facet | Bouyer, Patricia Casares, Antonio Randour, Mickael Vandenhove, Pierre |
| contents | In two-player games on graphs, the simplest possible strategies are those that can be implemented without any memory. These are called positional strategies. In this paper, we characterize objectives recognizable by deterministic Büchi automata (a subclass of omega-regular objectives) that are half-positional, that is, for which the protagonist can always play optimally using positional strategies (both over finite and infinite graphs). Our characterization consists of three natural conditions linked to the language-theoretic notion of right congruence. Furthermore, this characterization yields a polynomial-time algorithm to decide half-positionality of an objective recognized by a given deterministic Büchi automaton. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2205_01365 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Half-Positional Objectives Recognized by Deterministic Büchi Automata Bouyer, Patricia Casares, Antonio Randour, Mickael Vandenhove, Pierre Computer Science and Game Theory Formal Languages and Automata Theory Logic in Computer Science In two-player games on graphs, the simplest possible strategies are those that can be implemented without any memory. These are called positional strategies. In this paper, we characterize objectives recognizable by deterministic Büchi automata (a subclass of omega-regular objectives) that are half-positional, that is, for which the protagonist can always play optimally using positional strategies (both over finite and infinite graphs). Our characterization consists of three natural conditions linked to the language-theoretic notion of right congruence. Furthermore, this characterization yields a polynomial-time algorithm to decide half-positionality of an objective recognized by a given deterministic Büchi automaton. |
| title | Half-Positional Objectives Recognized by Deterministic Büchi Automata |
| topic | Computer Science and Game Theory Formal Languages and Automata Theory Logic in Computer Science |
| url | https://arxiv.org/abs/2205.01365 |