A quadratic upper bound on the reset thresholds of synchronizing automata containing a transitive permutation group
Fuente:
arXiv
Salvato in:
| Autore principale: | |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866910522967851008 |
|---|---|
| author | Zhu, Yinfeng |
| author_facet | Zhu, Yinfeng |
| contents | For any synchronizing $n$-state deterministic automaton, Černý conjectures the existence of a synchronizing word of length at most $(n-1)^2$. We prove that there exists a synchronizing word of length at most $2n^2 - 7n + 7$ for every synchronizing $n$-state deterministic automaton that satisfies the following two properties: 1. The image of the action of each letter contains at least $n-1$ states; 2. The actions of bijective letters generate a transitive permutation group on the state set. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2407_08135 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A quadratic upper bound on the reset thresholds of synchronizing automata containing a transitive permutation group Zhu, Yinfeng Formal Languages and Automata Theory 68Q45 For any synchronizing $n$-state deterministic automaton, Černý conjectures the existence of a synchronizing word of length at most $(n-1)^2$. We prove that there exists a synchronizing word of length at most $2n^2 - 7n + 7$ for every synchronizing $n$-state deterministic automaton that satisfies the following two properties: 1. The image of the action of each letter contains at least $n-1$ states; 2. The actions of bijective letters generate a transitive permutation group on the state set. |
| title | A quadratic upper bound on the reset thresholds of synchronizing automata containing a transitive permutation group |
| topic | Formal Languages and Automata Theory 68Q45 |
| url | https://arxiv.org/abs/2407.08135 |