Uniform winning strategies for the synchronization games on subclasses of finite automata
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917140874919936 |
|---|---|
| author | Fernau, Henning Haase, Carolina Hoffmann, Stefan Volkov, Mikhail |
| author_facet | Fernau, Henning Haase, Carolina Hoffmann, Stefan Volkov, Mikhail |
| contents | The pseudovariety $\mathbf{DS}$ consists of all finite monoids whose regular $D$-classes form subsemigroups. We exhibit a uniform winning strategy for Synchronizer in the synchronization game on every synchronizing automaton whose transition monoid lies in $\mathbf{DS}$, and we prove that $\mathbf{DS}$ is the largest pseudovariety with this property. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_11007 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Uniform winning strategies for the synchronization games on subclasses of finite automata Fernau, Henning Haase, Carolina Hoffmann, Stefan Volkov, Mikhail Formal Languages and Automata Theory Computer Science and Game Theory 68Q45, 91A05, 20M07 The pseudovariety $\mathbf{DS}$ consists of all finite monoids whose regular $D$-classes form subsemigroups. We exhibit a uniform winning strategy for Synchronizer in the synchronization game on every synchronizing automaton whose transition monoid lies in $\mathbf{DS}$, and we prove that $\mathbf{DS}$ is the largest pseudovariety with this property. |
| title | Uniform winning strategies for the synchronization games on subclasses of finite automata |
| topic | Formal Languages and Automata Theory Computer Science and Game Theory 68Q45, 91A05, 20M07 |
| url | https://arxiv.org/abs/2512.11007 |