Adversarial Synchronization
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2026
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866911399351943168 |
|---|---|
| author | Lipin, Anton E. Volkov, Mikhail V. |
| author_facet | Lipin, Anton E. Volkov, Mikhail V. |
| contents | We study a variant of the synchronization game on finite deterministic automata. In this game, Alice chooses one input letter of an automaton $A$ on each of her moves while Bob may respond with an arbitrary finite word over the input alphabet of $A$; Alice wins if the word obtained by interleaving her letters with Bob's responses resets $A$. We prove that if Alice has a winning strategy in this game on $A$, then $A$ admits a reset word whose length is strictly smaller than the number of states of $A$. In contrast, for any $k\ge 1$, we exhibit automata with shortest reset-word length quadratic in the number of states, on which Alice nevertheless wins a version of the game in which Bob's responses are restricted to arbitrary words of length at most $k$. We provide polynomial-time algorithms for deciding the winner in various synchronization games, and we analyze the relationships between variants of synchronization games on fixed-size automata. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_18362 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Adversarial Synchronization Lipin, Anton E. Volkov, Mikhail V. Formal Languages and Automata Theory Computer Science and Game Theory 68Q45, 91A05 We study a variant of the synchronization game on finite deterministic automata. In this game, Alice chooses one input letter of an automaton $A$ on each of her moves while Bob may respond with an arbitrary finite word over the input alphabet of $A$; Alice wins if the word obtained by interleaving her letters with Bob's responses resets $A$. We prove that if Alice has a winning strategy in this game on $A$, then $A$ admits a reset word whose length is strictly smaller than the number of states of $A$. In contrast, for any $k\ge 1$, we exhibit automata with shortest reset-word length quadratic in the number of states, on which Alice nevertheless wins a version of the game in which Bob's responses are restricted to arbitrary words of length at most $k$. We provide polynomial-time algorithms for deciding the winner in various synchronization games, and we analyze the relationships between variants of synchronization games on fixed-size automata. |
| title | Adversarial Synchronization |
| topic | Formal Languages and Automata Theory Computer Science and Game Theory 68Q45, 91A05 |
| url | https://arxiv.org/abs/2601.18362 |