{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T21:35:48Z","timestamp":1743024948158,"version":"3.40.3"},"publisher-location":"Cham","reference-count":21,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319223599"},{"type":"electronic","value":"9783319223605"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-319-22360-5_11","type":"book-chapter","created":{"date-parts":[[2015,7,27]],"date-time":"2015-07-27T08:24:42Z","timestamp":1437985482000},"page":"127-139","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["On the Number of Synchronizing Colorings of Digraphs"],"prefix":"10.1007","author":[{"given":"Vladimir V.","family":"Gusev","sequence":"first","affiliation":[]},{"given":"Marek","family":"Szyku\u0142a","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2015,7,28]]},"reference":[{"issue":"1","key":"11_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. Israel J. Math. 27(1), 49\u201363 (1977)","journal-title":"Israel J. Math."},{"issue":"3","key":"11_CR2","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1007\/s10958-013-1392-8","volume":"192","author":"DS Ananichev","year":"2013","unstructured":"Ananichev, D.S., Volkov, M.V., Gusev, V.V.: Primitive digraphs with large exponents and slowly synchronizing automata. J. Math. Sci. 192(3), 263\u2013278 (2013)","journal-title":"J. Math. Sci."},{"key":"11_CR3","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1016\/j.dam.2013.12.002","volume":"169","author":"M-P B\u00e9al","year":"2014","unstructured":"B\u00e9al, M.-P., Perrin, D.: A quadratic algorithm for road coloring. Discrete Appl. Math. 169, 15\u201329 (2014)","journal-title":"Discrete Appl. Math."},{"key":"11_CR4","unstructured":"Berlinkov, M.V.: On the probability of being synchronizable (2013). http:\/\/arxiv.org\/abs\/1304.5774"},{"key":"11_CR5","unstructured":"Cardoso, \u00c2.: The \u010cern\u00fd Conjecture and Other Synchronization Problems. Ph.D. thesis, University of Porto, Portugal (2014). http:\/\/hdl.handle.net\/10216\/73496"},{"issue":"3","key":"11_CR6","first-page":"208","volume":"14","author":"J \u010cern\u00fd","year":"1964","unstructured":"\u010cern\u00fd, J.: Pozn\u00e1mka k homog\u00e9nnym eksperimentom s kone\u010dn\u00fdmi automatami. Matematicko-fyzik\u00e1lny \u010casopis Slovenskej Akad\u00e9mie Vied 14(3), 208\u2013216 (1964). In Slovak","journal-title":"Matematicko-fyzik\u00e1lny \u010casopis Slovenskej Akad\u00e9mie Vied"},{"issue":"1","key":"11_CR7","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1007\/s00032-007-0070-z","volume":"75","author":"A Cherubini","year":"2007","unstructured":"Cherubini, A.: Synchronizing and collapsing words. Milan J. Math. 75(1), 305\u2013321 (2007)","journal-title":"Milan J. Math."},{"key":"11_CR8","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":"11_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"200","DOI":"10.1007\/978-3-319-08846-4_15","volume-title":"Implementation and Application of Automata","author":"VV Gusev","year":"2014","unstructured":"Gusev, V.V., Pribavkina, E.V.: Reset thresholds of automata with two cycle lengths. In: Holzer, M., Kutrib, M. (eds.) CIAA 2014. LNCS, vol. 8587, pp. 200\u2013210. Springer, Heidelberg (2014)"},{"key":"11_CR10","series-title":"Graph-theoretic analysis of finite Markov chains","volume-title":"Applied Mathematical Modeling: A Multidisciplinary Approach","author":"JP Jarvis","year":"1996","unstructured":"Jarvis, J.P., Shier, D.R.: Applied Mathematical Modeling: A Multidisciplinary Approach. Graph-theoretic analysis of finite Markov chains. CRC Press, Boca Raton (1996)"},{"key":"11_CR11","unstructured":"Kari, J., Volkov, M.V.: \u010cern\u00fd\u2019s conjecture and the road coloring problem. In: Handbook of Automata. European Science Foundation, to appear"},{"key":"11_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"340","DOI":"10.1007\/978-3-642-39274-0_30","volume-title":"implementation and application of automata","author":"A Kisielewicz","year":"2013","unstructured":"Kisielewicz, A., Szyku\u0142a, M.: Generating small automata and the \u010cern\u00fd conjecture. In: Konstantinidis, S. (ed.) CIAA 2013. LNCS, vol. 7982, pp. 340\u2013348. Springer, Heidelberg (2013)"},{"key":"11_CR13","unstructured":"Kisielewicz, A., Szyku\u0142a, M.: Synchronizing Automata with Large Reset Lengths (2014). http:\/\/arxiv.org\/abs\/1404.3311"},{"key":"11_CR14","doi-asserted-by":"publisher","first-page":"94","DOI":"10.1016\/j.jsc.2013.09.003","volume":"60","author":"BD McKay","year":"2014","unstructured":"McKay, B.D., Piperno, A.: Practical graph isomorphism II. J. Symbolic Comput. 60, 94\u2013112 (2014)","journal-title":"J. Symbolic Comput."},{"key":"11_CR15","unstructured":"Nicaud, C.: Fast synchronization of random automata (2014). http:\/\/arxiv.org\/abs\/1404.6962"},{"key":"11_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"480","DOI":"10.1007\/978-3-642-28332-1_41","volume-title":"Language and Automata Theory and Applications","author":"A Roman","year":"2012","unstructured":"Roman, A.: P\u2013NP threshold for synchronizing road coloring. In: Dediu, A.-H., Mart\u00edn-Vide, C. (eds.) LATA 2012. LNCS, vol. 7183, pp. 480\u2013489. Springer, Heidelberg (2012)"},{"issue":"2","key":"11_CR17","doi-asserted-by":"publisher","first-page":"146","DOI":"10.1137\/0201010","volume":"1","author":"R Tarjan","year":"1972","unstructured":"Tarjan, R.: Depth-first search and linear graph algorithms. SIAM J. Comput. 1(2), 146\u2013160 (1972)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"11_CR18","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":"11_CR19","unstructured":"Volkov, M.V.: Open problems on synchronizing automata. Workshop \u201cAround the \u010cern\u00fd conjecture\u201d, Wroc\u0142aw (2008). http:\/\/csseminar.kadm.usu.ru\/SLIDES\/WroclawABCD2008\/volkov_abcd_problems.pdf"},{"key":"11_CR20","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 \u010dern\u00fd conjecture. In: Mart\u00edn-Vide, C., Otto, F., Fernau, H. (eds.) LATA 2008. LNCS, vol. 5196, pp. 11\u201327. Springer, Heidelberg (2008)"},{"key":"11_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1007\/978-3-319-15579-1_12","volume-title":"Language and Automata Theory and Applications","author":"V Vorel","year":"2015","unstructured":"Vorel, V., Roman, A.: Complexity of road coloring with prescribed reset words. In: Dediu, A.-H., Formenti, E., Mart\u00edn-Vide, C., Truthe, B. (eds.) LATA 2015. LNCS, vol. 8977, pp. 161\u2013172. Springer, Heidelberg (2015)"}],"container-title":["Lecture Notes in Computer Science","Implementation and Application of Automata"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-22360-5_11","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,20]],"date-time":"2023-01-20T20:25:13Z","timestamp":1674246313000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-22360-5_11"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783319223599","9783319223605"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-22360-5_11","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"28 July 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}