{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,12,20]],"date-time":"2023-12-20T16:23:05Z","timestamp":1703089385939},"reference-count":32,"publisher":"World Scientific Pub Co Pte Lt","issue":"01","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2019,1]]},"abstract":"<jats:p> Motivated by the Babai conjecture and the \u010cern\u00fd 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 [Formula: see text] states in this class, we prove that the reset threshold is upper-bounded by [Formula: see text] and can attain the value [Formula: see text]. In addition, we study diameters of the pair digraphs of permutation automata and construct [Formula: see text]-state permutation automata with diameter [Formula: see text]. <\/jats:p>","DOI":"10.1142\/s0129054119400057","type":"journal-article","created":{"date-parts":[[2019,3,5]],"date-time":"2019-03-05T09:13:14Z","timestamp":1551777194000},"page":"93-114","source":"Crossref","is-referenced-by-count":3,"title":["On the Interplay Between \u010cern\u00fd and Babai\u2019s Conjectures"],"prefix":"10.1142","volume":"30","author":[{"given":"Fran\u00e7ois","family":"Gonze","sequence":"first","affiliation":[{"name":"ICTEAM Institute, Universit\u00e9 Catholique de Louvain, Louvain-la-Neuve, Belgium"}]},{"given":"Vladimir V.","family":"Gusev","sequence":"additional","affiliation":[{"name":"ICTEAM Institute, Universit\u00e9 Catholique de Louvain, Louvain-la-Neuve, Belgium"}]},{"given":"Rapha\u00ebl M.","family":"Jungers","sequence":"additional","affiliation":[{"name":"ICTEAM Institute, Universit\u00e9 Catholique de Louvain, Louvain-la-Neuve, Belgium"}]},{"given":"Bal\u00e1zs","family":"Gerencs\u00e9r","sequence":"additional","affiliation":[{"name":"Alfr\u00e9d R\u00e9nyi Institute of Mathematics and ELTE E\u00f6tv\u00f6s Lor\u00e1nd University, Budapest, Hungary"}]},{"given":"Mikhail V.","family":"Volkov","sequence":"additional","affiliation":[{"name":"Ural Federal University, Ekaterinburg, Russia"}]}],"member":"219","published-online":{"date-parts":[[2019,3,5]]},"reference":[{"key":"S0129054119400057BIB001","doi-asserted-by":"publisher","DOI":"10.1007\/s10958-013-1392-8"},{"key":"S0129054119400057BIB002","doi-asserted-by":"publisher","DOI":"10.1142\/9789812702616_0002"},{"key":"S0129054119400057BIB003","doi-asserted-by":"publisher","DOI":"10.4171\/EMSS\/4-2-1"},{"key":"S0129054119400057BIB004","doi-asserted-by":"publisher","DOI":"10.1016\/S0195-6698(05)80029-0"},{"key":"S0129054119400057BIB005","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139195768"},{"key":"S0129054119400057BIB007","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054113400133"},{"key":"S0129054119400057BIB008","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2012.06.002"},{"issue":"3","key":"S0129054119400057BIB009","first-page":"208","volume":"14","author":"\u010cern\u00fd J.","year":"1964","journal-title":"Mat.-fyz. \u010casopis Slovenskej Akad\u00e9mie Vied"},{"key":"S0129054119400057BIB010","first-page":"289","volume":"7","author":"\u010cern\u00fd J.","year":"1971","journal-title":"Kybernetica"},{"key":"S0129054119400057BIB012","doi-asserted-by":"publisher","DOI":"10.1007\/BF01110210"},{"issue":"3","key":"S0129054119400057BIB013","first-page":"3","volume":"23","author":"Don H.","year":"2016","journal-title":"Electr. J. Combinatorics"},{"key":"S0129054119400057BIB014","doi-asserted-by":"publisher","DOI":"10.1051\/ita\/1998321-300211"},{"key":"S0129054119400057BIB015","doi-asserted-by":"publisher","DOI":"10.1016\/S0195-6698(82)80025-5"},{"key":"S0129054119400057BIB016","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-006-1280-9"},{"key":"S0129054119400057BIB017","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1098-2418(199807)12:4<335::AID-RSA2>3.0.CO;2-U"},{"key":"S0129054119400057BIB018","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-84800-281-4"},{"key":"S0129054119400057BIB019","doi-asserted-by":"publisher","DOI":"10.1137\/16M1094099"},{"key":"S0129054119400057BIB020","doi-asserted-by":"publisher","DOI":"10.1137\/15M1024603"},{"issue":"3","key":"S0129054119400057BIB022","first-page":"61","volume":"15","author":"Grech M.","year":"2013","journal-title":"Discrete Math. & Theoret. Comput. Sci."},{"key":"S0129054119400057BIB023","doi-asserted-by":"publisher","DOI":"10.4007\/annals.2014.179.2.4"},{"key":"S0129054119400057BIB024","doi-asserted-by":"publisher","DOI":"10.1090\/S0273-0979-2015-01475-8"},{"key":"S0129054119400057BIB025","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(02)00405-X"},{"issue":"2","key":"S0129054119400057BIB026","first-page":"165","volume":"23","author":"Klyachko A. A.","year":"1987","journal-title":"Cybernetics and System Analysis"},{"key":"S0129054119400057BIB029","doi-asserted-by":"publisher","DOI":"10.1177\/027836498900800607"},{"key":"S0129054119400057BIB031","first-page":"535","volume":"17","author":"Pin J.-E.","year":"1983","journal-title":"Ann. Discrete Math."},{"key":"S0129054119400057BIB032","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(96)00136-3"},{"key":"S0129054119400057BIB033","doi-asserted-by":"publisher","DOI":"10.1007\/BF02732984"},{"key":"S0129054119400057BIB034","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-09444-0_5"},{"key":"S0129054119400057BIB035","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(01)00227-4"},{"key":"S0129054119400057BIB036","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054111008970"},{"key":"S0129054119400057BIB037","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2011.06.012"},{"key":"S0129054119400057BIB041","first-page":"112","volume":"2","author":"Zubov A. Y.","year":"1998","journal-title":"Tr. Diskretn. Mat."}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054119400057","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T18:35:35Z","timestamp":1565116535000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054119400057"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,1]]},"references-count":32,"journal-issue":{"issue":"01","published-online":{"date-parts":[[2019,3,5]]},"published-print":{"date-parts":[[2019,1]]}},"alternative-id":["10.1142\/S0129054119400057"],"URL":"https:\/\/doi.org\/10.1142\/s0129054119400057","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,1]]}}}