{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,9]],"date-time":"2024-09-09T18:10:44Z","timestamp":1725905444895},"publisher-location":"Cham","reference-count":40,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319628080"},{"type":"electronic","value":"9783319628097"}],"license":[{"start":{"date-parts":[[2017,1,1]],"date-time":"2017-01-01T00:00:00Z","timestamp":1483228800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2017]]},"DOI":"10.1007\/978-3-319-62809-7_13","type":"book-chapter","created":{"date-parts":[[2017,7,20]],"date-time":"2017-07-20T04:37:57Z","timestamp":1500525477000},"page":"185-197","source":"Crossref","is-referenced-by-count":8,"title":["On the Interplay Between Babai and \u010cern\u00fd\u2019s Conjectures"],"prefix":"10.1007","author":[{"given":"Fran\u00e7ois","family":"Gonze","sequence":"first","affiliation":[]},{"given":"Vladimir V.","family":"Gusev","sequence":"additional","affiliation":[]},{"given":"Bal\u00e1zs","family":"Gerencs\u00e9r","sequence":"additional","affiliation":[]},{"given":"Rapha\u00ebl M.","family":"Jungers","sequence":"additional","affiliation":[]},{"given":"Mikhail V.","family":"Volkov","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2017,7,21]]},"reference":[{"issue":"3","key":"13_CR1","doi-asserted-by":"crossref","first-page":"263","DOI":"10.1007\/s10958-013-1392-8","volume":"192","author":"DS Ananichev","year":"2013","unstructured":"Ananichev, D.S., Gusev, V.V., Volkov, M.V.: Primitive digraphs with large exponents and slowly synchronizing automata. J. Math. Sci. 192(3), 263\u2013278 (2013)","journal-title":"J. Math. Sci."},{"key":"13_CR2","doi-asserted-by":"crossref","unstructured":"Ananichev, D.S., Volkov, M.V.: Some results on \u010cerny type problems for transformation semigroups. In: Ara\u00fajo, I.M., Branco, M.J.J., Fernandes, V.H., Gomes, G.M.S. (eds.) Semigroups and Languages, pp. 23\u201342. World Scientific (2004)","DOI":"10.1142\/9789812702616_0002"},{"key":"13_CR3","unstructured":"Ara\u00fajo, J., Cameron, P.J., Steinberg, B.: Between primitive and 2-transitive: Synchronization and its friends. CoRR abs\/1511.03184 (2015)"},{"issue":"4","key":"13_CR4","doi-asserted-by":"crossref","first-page":"231","DOI":"10.1016\/S0195-6698(05)80029-0","volume":"13","author":"L Babai","year":"1992","unstructured":"Babai, L., Seress, A.: On the diameter of permutation groups. Eur. J. Combin. 13(4), 231\u2013243 (1992)","journal-title":"Eur. J. Combin."},{"key":"13_CR5","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9781139195768","volume-title":"Codes and Automata","author":"J Berstel","year":"2009","unstructured":"Berstel, J., Perrin, D., Reutenauer, C.: Codes and Automata. CUP, Cambridge (2009)"},{"key":"13_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-319-41114-9_1","volume-title":"Descriptional Complexity of Formal Systems","author":"EA Bondar","year":"2016","unstructured":"Bondar, E.A., Volkov, M.V.: Completely reachable automata. In: C\u00e2mpeanu, C., Manea, F., Shallit, J. (eds.) DCFS 2016. LNCS, vol. 9777, pp. 1\u201317. Springer, Cham (2016). doi: 10.1007\/978-3-319-41114-9_1"},{"issue":"6","key":"13_CR7","doi-asserted-by":"crossref","first-page":"691","DOI":"10.1142\/S0129054113400133","volume":"24","author":"JA Brzozowski","year":"2013","unstructured":"Brzozowski, J.A.: In search of most complex regular languages. Int. J. Found. Comput. Sci. 24(6), 691\u2013708 (2013)","journal-title":"Int. J. Found. Comput. Sci."},{"issue":"11","key":"13_CR8","doi-asserted-by":"crossref","first-page":"1233","DOI":"10.1016\/j.disc.2012.06.002","volume":"313","author":"PJ Cameron","year":"2013","unstructured":"Cameron, P.J.: Dixon\u2019s theorem and random synchronization. Discrete Math. 313(11), 1233\u20131236 (2013)","journal-title":"Discrete Math."},{"key":"13_CR9","unstructured":"\u010cern\u00fd, J.: Pozn\u00e1mka k homog\u00e9nnym experimentom s kone\u010dn\u00fdmi automatami. Mat.-fyz. \u010casopis Slovenskej Akad\u00e9mie Vied 14(3), 208\u2013216 (1964). in Slovak"},{"key":"13_CR10","first-page":"289","volume":"7","author":"J \u010cern\u00fd","year":"1971","unstructured":"\u010cern\u00fd, J., Pirick\u00e1, A., Rosenauerov\u00e1, B.: On directable automata. Kybernetica 7, 289\u2013298 (1971)","journal-title":"Kybernetica"},{"key":"13_CR11","doi-asserted-by":"crossref","unstructured":"Chevalier, P.Y., Hendrickx, J.M., Jungers, R.M.: Reachability of consensus and synchronizing automata. In: 54th IEEE Conference on Decision and Control (CDC), pp. 4139\u20134144. IEEE (2015)","DOI":"10.1109\/CDC.2015.7402864"},{"key":"13_CR12","doi-asserted-by":"crossref","first-page":"199","DOI":"10.1007\/BF01110210","volume":"110","author":"JD Dixon","year":"1969","unstructured":"Dixon, J.D.: The probability of generating the symmetric group. Math. Z. 110, 199\u2013205 (1969)","journal-title":"Math. Z."},{"key":"13_CR13","doi-asserted-by":"crossref","unstructured":"Don, H.: The \u010cern\u00fd conjecture and 1-contracting automata. Electr. J. Comb. 23(3), P3.12 (2016)","DOI":"10.37236\/5616"},{"key":"13_CR14","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1051\/ita\/1998321-300211","volume":"32","author":"L Dubuc","year":"1998","unstructured":"Dubuc, L.: Sur les automates circulaires et la conjecture de \u010cern\u00fd. RAIRO Informatique Th\u00e9orique et Applications 32, 21\u201334 (1998). in French","journal-title":"RAIRO Informatique Th\u00e9orique et Applications"},{"key":"13_CR15","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1016\/S0195-6698(82)80025-5","volume":"3","author":"P Frankl","year":"1982","unstructured":"Frankl, P.: An extremal problem for two families of sets. Eur. J. Combin. 3, 125\u2013127 (1982)","journal-title":"Eur. J. Combin."},{"key":"13_CR16","doi-asserted-by":"crossref","first-page":"381","DOI":"10.1007\/s00454-006-1280-9","volume":"37","author":"D Frettl\u00f6h","year":"2007","unstructured":"Frettl\u00f6h, D., Sing, B.: Computing modular coincidences for substitution tilings and point sets. Discrete Comput. Geom. 37, 381\u2013407 (2007)","journal-title":"Discrete Comput. Geom."},{"issue":"4","key":"13_CR17","doi-asserted-by":"crossref","first-page":"335","DOI":"10.1002\/(SICI)1098-2418(199807)12:4<335::AID-RSA2>3.0.CO;2-U","volume":"12","author":"J Friedman","year":"1998","unstructured":"Friedman, J., Joux, A., Roichman, Y., Stern, J., Tillich, J.P.: The action of a few permutations on $$r$$ -tuples is quickly transitive. Random Struct. Algorithms 12(4), 335\u2013350 (1998)","journal-title":"Random Struct. Algorithms"},{"key":"13_CR18","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-84800-281-4","volume-title":"Classical Finite Transformation Semigroups: An Introduction","author":"O Ganyushkin","year":"2009","unstructured":"Ganyushkin, O., Mazorchuk, V.: Classical Finite Transformation Semigroups: An Introduction. Springer, London (2009)"},{"key":"13_CR19","unstructured":"Gerencs\u00e9r, B., Gusev, V.V., Jungers, R.M.: Primitive sets of nonnegative matrices and synchronizing automata. CoRR abs\/1602.07556 (2016)"},{"issue":"2","key":"13_CR20","doi-asserted-by":"crossref","first-page":"995","DOI":"10.1137\/15M1024603","volume":"30","author":"F Gonze","year":"2016","unstructured":"Gonze, F., Jungers, R.M.: On the synchronizing probability function and the triple rendezvous time for synchronizing automata. SIAM J. Discrete Math. 30(2), 995\u20131014 (2016)","journal-title":"SIAM J. Discrete Math."},{"issue":"3","key":"13_CR21","first-page":"61","volume":"15","author":"M Grech","year":"2013","unstructured":"Grech, M., Kisielewicz, A.: The \u010cern\u00fd conjecture for automata respecting intervals of a directed graph. Discrete Math. Theoret. Comput. Sci. 15(3), 61\u201372 (2013)","journal-title":"Discrete Math. Theoret. Comput. Sci."},{"issue":"2","key":"13_CR22","doi-asserted-by":"crossref","first-page":"611","DOI":"10.4007\/annals.2014.179.2.4","volume":"179","author":"HA Helfgott","year":"2014","unstructured":"Helfgott, H.A., Seress, A.: On the diameter of permutation groups. Ann. Math. 179(2), 611\u2013658 (2014)","journal-title":"Ann. Math."},{"issue":"3","key":"13_CR23","doi-asserted-by":"crossref","first-page":"357","DOI":"10.1090\/S0273-0979-2015-01475-8","volume":"52","author":"HA Helfgott","year":"2015","unstructured":"Helfgott, H.A.: Growth in groups: ideas and perspectives. Bull. Amer. Math. Soc. 52(3), 357\u2013413 (2015)","journal-title":"Bull. Amer. Math. Soc."},{"key":"13_CR24","doi-asserted-by":"crossref","first-page":"223","DOI":"10.1016\/S0304-3975(02)00405-X","volume":"295","author":"J Kari","year":"2003","unstructured":"Kari, J.: Synchronizing finite automata on Eulerian digraphs. Theoret. Comput. Sci. 295, 223\u2013232 (2003)","journal-title":"Theoret. Comput. Sci."},{"issue":"2","key":"13_CR25","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1007\/BF01071771","volume":"23","author":"AA Klyachko","year":"1987","unstructured":"Klyachko, A.A., Rystsov, I.K., Spivak, M.A.: An extremal combinatorial problem associated with the bound on the length of a synchronizing word in an automaton. Cybern. Syst. Anal. 23(2), 165\u2013171 (1987)","journal-title":"Cybern. Syst. Anal."},{"key":"13_CR26","unstructured":"Maslennikova, M.: Reset complexity of ideal languages. In: Bielikov\u00e1, M. (ed.) SOFSEM 2012. Proceedings of the Institute of Computer Science Academy of Sciences of the Czech Republic, vol. II, pp. 33\u201344 (2012)"},{"key":"13_CR27","doi-asserted-by":"crossref","unstructured":"Natarajan, B.K.: An algorithmic approach to the automated design of parts orienters. In: 27th FOCS, pp. 132\u2013142. IEEE (1986)","DOI":"10.1109\/SFCS.1986.5"},{"issue":"6","key":"13_CR28","doi-asserted-by":"crossref","first-page":"89","DOI":"10.1177\/027836498900800607","volume":"8","author":"BK Natarajan","year":"1989","unstructured":"Natarajan, B.K.: Some paradigms for the automated design of parts feeders. Int. J. Robot. Res. 8(6), 89\u2013109 (1989)","journal-title":"Int. J. Robot. Res."},{"key":"13_CR29","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"353","DOI":"10.1007\/978-3-319-15579-1_27","volume-title":"Language and Automata Theory and Applications","author":"P Panteleev","year":"2015","unstructured":"Panteleev, P.: Preset distinguishing sequences and diameter of transformation semigroups. In: Dediu, A.-H., Formenti, E., Mart\u00edn-Vide, C., Truthe, B. (eds.) LATA 2015. LNCS, vol. 8977, pp. 353\u2013364. Springer, Cham (2015). doi: 10.1007\/978-3-319-15579-1_27"},{"key":"13_CR30","first-page":"535","volume":"17","author":"JE Pin","year":"1983","unstructured":"Pin, J.E.: On two combinatorial problems arising from automata theory. Ann. Discrete Math. 17, 535\u2013548 (1983)","journal-title":"Ann. Discrete Math."},{"issue":"1","key":"13_CR31","doi-asserted-by":"crossref","first-page":"273","DOI":"10.1016\/S0304-3975(96)00136-3","volume":"172","author":"IK Rystsov","year":"1997","unstructured":"Rystsov, I.K.: Reset words for commutative and solvable automata. Theoret. Comput. Sci. 172(1), 273\u2013279 (1997)","journal-title":"Theoret. Comput. Sci."},{"issue":"3","key":"13_CR32","doi-asserted-by":"crossref","first-page":"339","DOI":"10.1007\/BF02732984","volume":"36","author":"IK Rystsov","year":"2000","unstructured":"Rystsov, I.K.: Estimation of the length of reset words for automata with simple idempotents. Cybern. Syst. Anal. 36(3), 339\u2013344 (2000)","journal-title":"Cybern. Syst. Anal."},{"key":"13_CR33","doi-asserted-by":"crossref","unstructured":"Saloff-Coste, L.: Random walks on finite groups. In: Kesten, H. (ed.) Probability on Discrete Structures, pp. 263\u2013346. Springer, Heidelberg (2004)","DOI":"10.1007\/978-3-662-09444-0_5"},{"issue":"1","key":"13_CR34","doi-asserted-by":"crossref","first-page":"263","DOI":"10.1016\/S0304-3975(01)00227-4","volume":"292","author":"A Salomaa","year":"2003","unstructured":"Salomaa, A.: Composition sequences for functions over a finite domain. Theoret. Comput. Sci. 292(1), 263\u2013281 (2003)","journal-title":"Theoret. Comput. Sci."},{"issue":"7","key":"13_CR35","doi-asserted-by":"crossref","first-page":"1697","DOI":"10.1142\/S0129054111008970","volume":"22","author":"B Steinberg","year":"2011","unstructured":"Steinberg, B.: The averaging trick and the \u010cern\u00fd conjecture. Int. J. Found. Comput. Sci. 22(7), 1697\u20131706 (2011)","journal-title":"Int. J. Found. Comput. Sci."},{"issue":"39","key":"13_CR36","doi-asserted-by":"crossref","first-page":"5487","DOI":"10.1016\/j.tcs.2011.06.012","volume":"412","author":"B Steinberg","year":"2011","unstructured":"Steinberg, B.: The \u010cern\u00fd conjecture for one-cluster automata with prime length cycle. Theoret. Comput. Sci. 412(39), 5487\u20135491 (2011)","journal-title":"Theoret. Comput. Sci."},{"key":"13_CR37","unstructured":"Szyku\u0142a, M.: Improving the upper bound the length of the shortest reset words. CoRR abs\/1702.05455 (2017)"},{"key":"13_CR38","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1007\/978-3-540-88282-4_4","volume-title":"Language and Automata Theory and Applications","author":"MV Volkov","year":"2008","unstructured":"Volkov, M.V.: Synchronizing automata and the \u010cern\u00fd conjecture. In: Mart\u00edn-Vide, C., Otto, F., Fernau, H. (eds.) LATA 2008. LNCS, vol. 5196, pp. 11\u201327. Springer, Heidelberg (2008). doi: 10.1007\/978-3-540-88282-4_4"},{"key":"13_CR39","doi-asserted-by":"crossref","unstructured":"Vorel, V.: Subset synchronization of transitive automata. In: \u00c9sik, Z., F\u00fcl\u00f6p, Z. (eds.) AFL 2014. EPTCS, vol. 151, pp. 370\u2013381 (2014)","DOI":"10.4204\/EPTCS.151.26"},{"key":"13_CR40","first-page":"112","volume":"2","author":"AY Zubov","year":"1998","unstructured":"Zubov, A.Y.: On the diameter of the group $$S_N$$ with respect to a system of generators consisting of a complete cycle and a transposition. Tr. Diskretn. Mat. 2, 112\u2013150 (1998). in Russian","journal-title":"Tr. Diskretn. Mat."}],"container-title":["Lecture Notes in Computer Science","Developments in Language Theory"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-62809-7_13","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,10,12]],"date-time":"2020-10-12T21:19:34Z","timestamp":1602537574000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-62809-7_13"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017]]},"ISBN":["9783319628080","9783319628097"],"references-count":40,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-62809-7_13","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2017]]}}}