{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,25]],"date-time":"2025-03-25T22:33:15Z","timestamp":1742941995793,"version":"3.40.3"},"publisher-location":"Cham","reference-count":28,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319986531"},{"type":"electronic","value":"9783319986548"}],"license":[{"start":{"date-parts":[[2018,1,1]],"date-time":"2018-01-01T00:00:00Z","timestamp":1514764800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2018]]},"DOI":"10.1007\/978-3-319-98654-8_31","type":"book-chapter","created":{"date-parts":[[2018,8,4]],"date-time":"2018-08-04T19:43:57Z","timestamp":1533411837000},"page":"379-391","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Dynamics of the Independence Number and Automata Synchronization"],"prefix":"10.1007","author":[{"given":"Vladimir V.","family":"Gusev","sequence":"first","affiliation":[]},{"given":"Rapha\u00ebl M.","family":"Jungers","sequence":"additional","affiliation":[]},{"given":"Daniel","family":"Pr\u016f\u0161a","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2018,8,5]]},"reference":[{"issue":"1","key":"31_CR1","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1007\/BF02761605","volume":"27","author":"RL Adler","year":"1977","unstructured":"Adler, R.L., Goodwyn, L.W., Weiss, B.: Equivalence of topological Markov shifts. Isr. J. Math. 27(1), 49\u201363 (1977)","journal-title":"Isr. J. Math."},{"issue":"3","key":"31_CR2","doi-asserted-by":"publisher","first-page":"221","DOI":"10.3233\/FI-2016-1357","volume":"145","author":"DS Ananichev","year":"2016","unstructured":"Ananichev, D.S., Gusev, V.V.: Approximation of reset thresholds with greedy algorithms. Fundam. Inform. 145(3), 221\u2013227 (2016)","journal-title":"Fundam. Inform."},{"issue":"2","key":"31_CR3","doi-asserted-by":"publisher","first-page":"101","DOI":"10.4171\/EMSS\/4-2-1","volume":"4","author":"J Ara\u00fajo","year":"2017","unstructured":"Ara\u00fajo, J., Cameron, P.J., Steinberg, B.: Between primitive and 2-transitive: synchronization and its friends. EMS Surv. Math. Sci. 4(2), 101\u2013184 (2017)","journal-title":"EMS Surv. Math. Sci."},{"issue":"2","key":"31_CR4","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1142\/S0129054111008039","volume":"22","author":"MP B\u00e9al","year":"2011","unstructured":"B\u00e9al, M.P., Berlinkov, M.V., Perrin, D.: A quadratic upper bound on the size of a synchronizing word in one-cluster automata. Int. J. Found. Comput. Sci. 22(2), 277\u2013288 (2011)","journal-title":"Int. J. Found. Comput. Sci."},{"unstructured":"Berlinkov, M.V., Ferens, R., Szyku\u0142a, M.: Extending word problems in deterministic finite automata. CoRR abs\/1704.08233 (2017)","key":"31_CR5"},{"key":"31_CR6","doi-asserted-by":"publisher","first-page":"718","DOI":"10.1016\/j.ins.2016.07.049","volume":"369","author":"MV Berlinkov","year":"2016","unstructured":"Berlinkov, M.V., Szyku\u0142a, M.: Algebraic synchronization criterion and computing reset words. Inf. Sci. 369, 718\u2013730 (2016)","journal-title":"Inf. Sci."},{"key":"31_CR7","volume-title":"Codes and Automata. Encyclopedia of Mathematics and its Applications","author":"J Berstel","year":"2009","unstructured":"Berstel, J., Perrin, D., Reutenauer, C.: Codes and Automata. Encyclopedia of Mathematics and its Applications. Cambridge University Press, Cambridge (2009)"},{"issue":"8","key":"31_CR8","doi-asserted-by":"publisher","first-page":"591","DOI":"10.1007\/s00236-009-0106-7","volume":"46","author":"A Carpi","year":"2009","unstructured":"Carpi, A., D\u2019Alessandro, F.: Strongly transitive automata and the \u010cern\u00fd conjecture. Acta Inform. 46(8), 591 (2009)","journal-title":"Acta Inform."},{"issue":"3","key":"31_CR9","first-page":"208","volume":"14","author":"J \u010cern\u00fd","year":"1964","unstructured":"\u010cern\u00fd, J.: Pozn\u00e1mka k homog\u00e9nnym experimentom s kone\u010dn\u00fdmi automatmi. Matematicko-fyzik\u00e1lny \u010casopis Slovenskej Akad\u00e9mie Vied 14(3), 208\u2013216 (1964)","journal-title":"Matematicko-fyzik\u00e1lny \u010casopis Slovenskej Akad\u00e9mie Vied"},{"doi-asserted-by":"crossref","unstructured":"Chevalier, P.Y., Hendrickx, J.M., Jungers, R.M.: Reachability of consensus and synchronizing automata. In: 2015 54th IEEE Conference on Decision and Control (CDC), pp. 4139\u20134144. IEEE (2015)","key":"31_CR10","DOI":"10.1109\/CDC.2015.7402864"},{"key":"31_CR11","doi-asserted-by":"publisher","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 C\u0306ern\u00fd. Inform. Th\u00e9orique Appl. 32, 21\u201334 (1998). in French","journal-title":"Inform. Th\u00e9orique Appl."},{"key":"31_CR12","doi-asserted-by":"publisher","first-page":"500","DOI":"10.1137\/0219033","volume":"19","author":"D Eppstein","year":"1990","unstructured":"Eppstein, D.: Reset sequences for monotonic automata. SIAM J. Comput. 19, 500\u2013510 (1990)","journal-title":"SIAM J. Comput."},{"key":"31_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1007\/978-3-662-48057-1_19","volume-title":"Mathematical Foundations of Computer Science 2015","author":"P Gawrychowski","year":"2015","unstructured":"Gawrychowski, P., Straszak, D.: Strong inapproximability of the shortest reset word. In: Italiano, G.F., Pighizzini, G., Sannella, D.T. (eds.) MFCS 2015. LNCS, vol. 9234, pp. 243\u2013255. Springer, Heidelberg (2015). \n                    https:\/\/doi.org\/10.1007\/978-3-662-48057-1_19"},{"key":"31_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"154","DOI":"10.1007\/978-3-642-18098-9_17","volume-title":"Implementation and Application of Automata","author":"M Gerbush","year":"2011","unstructured":"Gerbush, M., Heeringa, B.: Approximating minimum reset sequences. In: Domaratzki, M., Salomaa, K. (eds.) CIAA 2010. LNCS, vol. 6482, pp. 154\u2013162. Springer, Heidelberg (2011). \n                    https:\/\/doi.org\/10.1007\/978-3-642-18098-9_17"},{"issue":"1","key":"31_CR15","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1137\/16M1094099","volume":"39","author":"B Gerencs\u00e9r","year":"2018","unstructured":"Gerencs\u00e9r, B., Gusev, V.V., Jungers, R.M.: Primitive sets of nonnegative matrices and synchronizing automata. SIAM J. Matrix Anal. Appl. 39(1), 83\u201398 (2018)","journal-title":"SIAM J. Matrix Anal. Appl."},{"key":"31_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1007\/978-3-319-62809-7_13","volume-title":"Developments in Language Theory","author":"F Gonze","year":"2017","unstructured":"Gonze, F., Gusev, V.V., Gerencs\u00e9r, B., Jungers, R.M., Volkov, M.V.: On the interplay between Babai and \u010cern\u00fd\u2019s conjectures. In: Charlier, \u00c9., Leroy, J., Rigo, M. (eds.) DLT 2017. LNCS, vol. 10396, pp. 185\u2013197. Springer, Cham (2017). \n                    https:\/\/doi.org\/10.1007\/978-3-319-62809-7_13"},{"volume-title":"Handbook of Combinatorics","year":"1995","unstructured":"Graham, R.L., Gr\u00f6tschel, M., Lov\u00e1sz, L. (eds.): Handbook of Combinatorics, vol. 2. MIT Press, Cambridge (1995)","key":"31_CR17"},{"issue":"1\u20133","key":"31_CR18","doi-asserted-by":"publisher","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. Theor. Comput. Sci. 295(1\u20133), 223\u2013232 (2003)","journal-title":"Theor. Comput. Sci."},{"key":"31_CR19","first-page":"16","volume":"2","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. Kibernetika 2, 16\u201320 (1987)","journal-title":"Kibernetika"},{"doi-asserted-by":"crossref","unstructured":"Pin, J.E.: On two combinatorial problems arising from automata theory. In: Proceedings of the International Colloquium on Graph Theory and Combinatorics, vol. 75, pp. 535\u2013548. North-Holland Mathematics Studies (1983)","key":"31_CR20","DOI":"10.1016\/S0304-0208(08)73432-7"},{"issue":"24","key":"31_CR21","doi-asserted-by":"publisher","first-page":"9512","DOI":"10.1016\/j.eswa.2015.07.071","volume":"42","author":"A Roman","year":"2015","unstructured":"Roman, A., Szyku\u0142a, M.: Forward and backward synchronizing algorithms. Expert Syst. Appl. 42(24), 9512\u20139527 (2015)","journal-title":"Expert Syst. Appl."},{"issue":"5","key":"31_CR22","doi-asserted-by":"publisher","first-page":"669","DOI":"10.1007\/BF02366314","volume":"31","author":"IK Rystsov","year":"1995","unstructured":"Rystsov, I.K.: Almost optimal bound of recurrent word length for regular automata. Cybern. Syst. Anal. 31(5), 669\u2013674 (1995)","journal-title":"Cybern. Syst. Anal."},{"issue":"3","key":"31_CR23","first-page":"32","volume":"187","author":"IK Rystsov","year":"2000","unstructured":"Rystsov, I.K.: On the length of reset words for automata with simple idempotents. Kibernet. Sistem. Anal. 187(3), 32\u201339 (2000)","journal-title":"Kibernet. Sistem. Anal."},{"issue":"1","key":"31_CR24","doi-asserted-by":"publisher","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. Theor. Comput. Sci. 292(1), 263\u2013281 (2003). Selected papers in honor of Jean Berstel","journal-title":"Theor. Comput. Sci."},{"issue":"7","key":"31_CR25","doi-asserted-by":"publisher","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."},{"unstructured":"Szyku\u0142a, M.: Improving the upper bound on the length of the shortest reset word. In: Niedermeier, R., Vall\u00e9e, B. (eds.) Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics, vol. 96, pp. 56:1\u201356:13. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Germany (2018)","key":"31_CR26"},{"issue":"1","key":"31_CR27","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1007\/s11856-009-0062-5","volume":"172","author":"AN Trahtman","year":"2009","unstructured":"Trahtman, A.N.: The road coloring problem. Isr. J. Math. 172(1), 51\u201360 (2009)","journal-title":"Isr. J. Math."},{"key":"31_CR28","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). \n                    https:\/\/doi.org\/10.1007\/978-3-540-88282-4_4"}],"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-98654-8_31","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2018,9,2]],"date-time":"2018-09-02T19:17:37Z","timestamp":1535915857000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-98654-8_31"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018]]},"ISBN":["9783319986531","9783319986548"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-98654-8_31","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2018]]}}}