Please use this identifier to cite or link to this item: http://hdl.handle.net/10995/102723
Full metadata record
DC FieldValueLanguage
dc.contributor.authorGonze, F.en
dc.contributor.authorGusev, V. V.en
dc.contributor.authorJungers, R. M.en
dc.contributor.authorGerencsér, B.en
dc.contributor.authorVolkov, M. V.en
dc.date.accessioned2021-08-31T15:05:06Z-
dc.date.available2021-08-31T15:05:06Z-
dc.date.issued2019-
dc.identifier.citationOn 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.en
dc.identifier.issn1290541-
dc.identifier.otherFinal2
dc.identifier.otherAll Open Access, Green3
dc.identifier.otherhttps://www.scopus.com/inward/record.uri?eid=2-s2.0-85062518493&doi=10.1142%2fS0129054119400057&partnerID=40&md5=5b2dc76d177c6d46a5a848f8343aac91
dc.identifier.urihttp://hdl.handle.net/10995/102723-
dc.description.abstractMotivated 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.en
dc.format.mimetypeapplication/pdfen
dc.language.isoenen
dc.publisherWorld Scientific Publishing Co. Pte Ltden
dc.rightsinfo:eu-repo/semantics/openAccessen
dc.sourceInt. J. Found. Comput. Sci.2
dc.sourceInternational Journal of Foundations of Computer Scienceen
dc.subjectAERNÝ'S CONJECTUREen
dc.subjectBABAI'S CONJECTUREen
dc.subjectPERMUTATION AUTOMATAen
dc.subjectSYNCHRONIZING AUTOMATAen
dc.titleOn the Interplay between Aerný and Babai's Conjecturesen
dc.typeArticleen
dc.typeinfo:eu-repo/semantics/articleen
dc.typeinfo:eu-repo/semantics/publishedVersionen
dc.identifier.doi10.1142/S0129054119400057-
dc.identifier.scopus85062518493-
local.contributor.employeeGonze, F., ICTEAM Institute, Université Catholique de Louvain, Louvain-la-Neuve, Belgium
local.contributor.employeeGusev, V.V., ICTEAM Institute, Université Catholique de Louvain, Louvain-la-Neuve, Belgium
local.contributor.employeeJungers, R.M., ICTEAM Institute, Université Catholique de Louvain, Louvain-la-Neuve, Belgium
local.contributor.employeeGerencsér, B., Alfréd Rényi, Institute of Mathematics and ELTE Eötvös, Loránd University, Budapest, Hungary
local.contributor.employeeVolkov, M.V., Ural Federal University, Ekaterinburg, Russian Federation
local.description.firstpage93-
local.description.lastpage114-
local.issue1-
local.volume30-
local.contributor.departmentICTEAM Institute, Université Catholique de Louvain, Louvain-la-Neuve, Belgium
local.contributor.departmentAlfréd Rényi, Institute of Mathematics and ELTE Eötvös, Loránd University, Budapest, Hungary
local.contributor.departmentUral Federal University, Ekaterinburg, Russian Federation
local.identifier.pure9168414-
local.identifier.pure5007193c-d33f-48b4-af6f-73389f2f68c7uuid
local.identifier.eid2-s2.0-85062518493-
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.