Gonze, Fran¸cois and Gusev, Vladimir V. and Gerencsér, Balázs and Jungers, Raphaël M. and Volkov, Mikhail V. (2017) On the interplay between Babai and Černý’s conjectures. LECTURE NOTES IN ARTIFICIAL INTELLIGENCE, 10396. pp. 185-197. ISSN 0302-9743
|
Text
1704.04047v2.pdf Download (279kB) | Preview |
Abstract
Motivated by the Babai conjecture and the Černý conjecture, we study the reset thresholds of automata with the transition monoid equal to the full monoid of transformations of the state set. For automata with n states in this class, we prove that the reset thresholds are upperbounded by 2n2 -6n + 5 and can attain the value (Formula presented). In addition, we study diameters of the pair digraphs of permutation automata and construct n-state permutation automata with diameter (formula presented). © Springer International Publishing AG 2017.
| Item Type: | Article |
|---|---|
| Uncontrolled Keywords: | Automata theory; State-sets; Monoid of transformations; Algebra |
| Subjects: | Q Science / természettudomány > QA Mathematics / matematika |
| SWORD Depositor: | MTMT SWORD |
| Depositing User: | MTMT SWORD |
| Date Deposited: | 07 Dec 2017 17:04 |
| Last Modified: | 07 Dec 2017 17:04 |
| URI: | http://real.mtak.hu/id/eprint/70790 |
Actions (login required)
 |
Edit Item |
