Cerny type automata and rank conjecture
Fuente:
arXiv
Guardado en:
| Autor principal: | |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866913673162784768 |
|---|---|
| author | Rystsov, Igor |
| author_facet | Rystsov, Igor |
| contents | The aim of this paper is to prove the Černý conjecture and the rank conjecture for Černý type automata and monoids. A transformation monoid is said to be Černý type if it is generated by a simple idempotent and a regular group of permutations. We prove Černý conjecture for the Černý type synchronizing automata and the rank conjecture for the Černý type transformation monoids. In particular, we obtain the tight bound for the reset threshold of Černý type synchronizing monoids. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_19166 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Cerny type automata and rank conjecture Rystsov, Igor Formal Languages and Automata Theory The aim of this paper is to prove the Černý conjecture and the rank conjecture for Černý type automata and monoids. A transformation monoid is said to be Černý type if it is generated by a simple idempotent and a regular group of permutations. We prove Černý conjecture for the Černý type synchronizing automata and the rank conjecture for the Černý type transformation monoids. In particular, we obtain the tight bound for the reset threshold of Černý type synchronizing monoids. |
| title | Cerny type automata and rank conjecture |
| topic | Formal Languages and Automata Theory |
| url | https://arxiv.org/abs/2501.19166 |