Please use this identifier to cite or link to this item: http://hdl.handle.net/10995/102723
Title: On the Interplay between Aerný and Babai's Conjectures
Authors: Gonze, F.
Gusev, V. V.
Jungers, R. M.
Gerencsér, B.
Volkov, M. V.
Issue Date: 2019
Publisher: World Scientific Publishing Co. Pte Ltd
Citation: On the Interplay between Aerný and Babai's Conjectures / F. Gonze, V. V. Gusev, R. M. Jungers, et al. — DOI 10.1142/S0129054119400057 // International Journal of Foundations of Computer Science. — 2019. — Vol. 30. — Iss. 1. — P. 93-114.
Abstract: Motivated by the Babai conjecture and the Aerný 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 n2 4 + o(n2). © 2019 World Scientific Publishing Company.
Keywords: AERNÝ'S CONJECTURE
BABAI'S CONJECTURE
PERMUTATION AUTOMATA
SYNCHRONIZING AUTOMATA
URI: http://hdl.handle.net/10995/102723
Access: info:eu-repo/semantics/openAccess
SCOPUS ID: 85062518493
PURE ID: 9168414
5007193c-d33f-48b4-af6f-73389f2f68c7
ISSN: 1290541
DOI: 10.1142/S0129054119400057
Appears in Collections:Научные публикации, проиндексированные в SCOPUS и WoS CC

Files in This Item:
File Description SizeFormat 
2-s2.0-85062518493.pdf276,92 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.