Please use this identifier to cite or link to this item:
http://elar.urfu.ru/handle/10995/102755
Title: | On the interplay between babai and Černý’s conjectures |
Authors: | Gonze, F. Gusev, V. V. Gerencsér, B. Jungers, R. M. Volkov, M. V. |
Issue Date: | 2017 |
Publisher: | Springer Verlag |
Citation: | On the interplay between babai and Černý’s conjectures / F. Gonze, V. V. Gusev, B. Gerencsér, et al. — DOI 10.1007/978-3-319-62809-7_13 // Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). — 2017. — Vol. 10396 LNCS. — P. 185-197. |
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. |
Keywords: | ALGEBRA MONOID OF TRANSFORMATIONS STATE-SETS AUTOMATA THEORY |
URI: | http://elar.urfu.ru/handle/10995/102755 |
Access: | info:eu-repo/semantics/openAccess |
SCOPUS ID: | 85026730431 |
WOS ID: | 000442555100019 |
PURE ID: | 6322da45-3e82-4290-a7e2-888dffb80a41 1970289 |
ISSN: | 3029743 |
ISBN: | 9783319628080 |
DOI: | 10.1007/978-3-319-62809-7_13 |
Appears in Collections: | Научные публикации ученых УрФУ, проиндексированные в SCOPUS и WoS CC |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
2-s2.0-85026730431.pdf | 276,92 kB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.