| Autor: |
Gonze, François, Gusev, Vladimir V., Jungers, Raphaël M., Gerencsér, Balázs, Volkov, Mikhail V. |
| Předmět: |
|
| Zdroj: |
International Journal of Foundations of Computer Science; Jan2019, Vol. 30 Issue 1, p93-114, 22p |
| Abstrakt: |
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 2 n 2 − 6 n + 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 n 2 4 + o (n 2). [ABSTRACT FROM AUTHOR] |
| Databáze: |
Complementary Index |
| Externí odkaz: |
|
