{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T17:16:50Z","timestamp":1760203010006},"reference-count":14,"publisher":"World Scientific Pub Co Pte Lt","issue":"08","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2020,12]]},"abstract":"<jats:p> In this paper we address the question of synchronizing random automata in the critical settings of almost-group automata. Group automata are automata where all letters act as permutations on the set of states, and they are not synchronizing (unless they have one state). In almost-group automata, one of the letters acts as a permutation on [Formula: see text] states, and the others as permutations. <\/jats:p><jats:p> We prove that this small change is enough for automata to become synchronizing with high probability. More precisely, we establish that the probability that a strongly-connected almost-group automaton is not synchronizing is [Formula: see text], for a [Formula: see text]-letter alphabet. <\/jats:p><jats:p> We also present an efficient algorithm that decides whether a strongly-connected almost-group automaton is synchronizing. For a natural model of computation, we establish a [Formula: see text] worst-case lower bound for this problem ([Formula: see text] for the average case), which is almost matched by our algorithm. <\/jats:p>","DOI":"10.1142\/s0129054120420058","type":"journal-article","created":{"date-parts":[[2020,12,16]],"date-time":"2020-12-16T03:46:01Z","timestamp":1608090361000},"page":"1091-1112","source":"Crossref","is-referenced-by-count":2,"title":["Synchronizing Almost-Group Automata"],"prefix":"10.1142","volume":"31","author":[{"given":"Mikhail V.","family":"Berlinkov","sequence":"first","affiliation":[{"name":"Institute of Natural Sciences and Mathematics, Ural Federal University, Ekaterinburg, Russia 620062, Russia"}]},{"given":"Cyril","family":"Nicaud","sequence":"additional","affiliation":[{"name":"LIGM, Universit\u00e9 Paris-Est and CNRS, 5 bd Descartes, Champs-sur-Marne, 77454 Marne-la-Vall\u00e9ee Cedex 2, France"}]}],"member":"219","published-online":{"date-parts":[[2020,12,15]]},"reference":[{"key":"S0129054120420058BIB002","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1007\/978-3-319-29221-2_7","volume-title":"Algorithms and Discrete Applied Mathematics","author":"Berlinkov M.","year":"2016"},{"key":"S0129054120420058BIB003","doi-asserted-by":"crossref","first-page":"84","DOI":"10.1007\/978-3-319-94812-6_8","volume-title":"Implementation and Application of Automata","author":"Berlinkov M.","year":"2018"},{"key":"S0129054120420058BIB004","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1016\/j.dam.2013.12.002","volume":"169","author":"B\u00e9al M.-P.","year":"2014","journal-title":"Discr. Appl. Math."},{"issue":"3","key":"S0129054120420058BIB005","first-page":"208","volume":"14","author":"\u010cern\u00fd J.","year":"1964","journal-title":"Matem.-fyzik. \u010casopis Slovenskej Akad\u00e9mie Vied"},{"key":"S0129054120420058BIB006","doi-asserted-by":"crossref","first-page":"500","DOI":"10.1137\/0219033","volume":"19","author":"Eppstein D.","year":"1990","journal-title":"SIAM J. Comput."},{"issue":"2","key":"S0129054120420058BIB007","first-page":"270","volume":"8","author":"Kari J.","year":"2002","journal-title":"J. UCS"},{"key":"S0129054120420058BIB008","volume-title":"Algorithms and Data Structures: The Basic Toolbox","author":"Mehlhorn K.","year":"2008"},{"key":"S0129054120420058BIB009","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511814075","volume-title":"Randomized Algorithms","author":"Motwani R.","year":"1995"},{"key":"S0129054120420058BIB010","first-page":"5","volume":"2014","author":"Nicaud C.","year":"2014","journal-title":"Math. Found. Comp. Sci."},{"key":"S0129054120420058BIB011","first-page":"43:1","volume":"60","author":"Nicaud C.","year":"2016","journal-title":"APPROX\/RANDOM 2016, Leibniz Inter. Proc. in Inf. (LIPIcs)"},{"key":"S0129054120420058BIB012","first-page":"535","volume":"75","author":"Pin J.-E.","year":"1983","journal-title":"Proc. Int. Coll. Graph Theory and Comb."},{"key":"S0129054120420058BIB013","first-page":"56:1","volume":"96","author":"Szykula M.","year":"2018","journal-title":"35th Symposium on Theoretical Aspects of Computer Science (STACS 2018), LIPIcs"},{"issue":"1","key":"S0129054120420058BIB014","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1007\/s11856-009-0062-5","volume":"172","author":"Trahtman A.","year":"2009","journal-title":"Israel J. Math."},{"issue":"4","key":"S0129054120420058BIB016","volume":"12","author":"Zaks Y.","year":"2010","journal-title":"Discr. Math. Theoret. Comput. Sci."}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054120420058","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,1,21]],"date-time":"2021-01-21T03:34:08Z","timestamp":1611200048000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054120420058"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,12]]},"references-count":14,"journal-issue":{"issue":"08","published-print":{"date-parts":[[2020,12]]}},"alternative-id":["10.1142\/S0129054120420058"],"URL":"https:\/\/doi.org\/10.1142\/s0129054120420058","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,12]]}}}