Gonze, François and Gusev, Vladimir V. and Gerencsér, Balázs and Jungers, Raphaël M. and Volkov, Mikhail V. (2019) On the Interplay Between Černý and Babai’s Conjectures. INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE, 30 (1). pp. 93-114. ISSN 0129-0541
|
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 threshold is upper-bounded by 2n2−6n+5 and can attain the value n(n−1)2. In addition, we study diameters of the pair digraphs of permutation automata and construct n-state permutation automata with diameter n24+o(n2).
| Item Type: | Article |
|---|---|
| Subjects: | Q Science / természettudomány > QA Mathematics / matematika |
| SWORD Depositor: | MTMT SWORD |
| Depositing User: | MTMT SWORD |
| Date Deposited: | 11 Mar 2019 15:33 |
| Last Modified: | 11 Mar 2019 15:33 |
| URI: | http://real.mtak.hu/id/eprint/92048 |
Actions (login required)
 |
Edit Item |
