{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:36:34Z","timestamp":1725665794515},"publisher-location":"Berlin, Heidelberg","reference-count":9,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642283314"},{"type":"electronic","value":"9783642283321"}],"license":[{"start":{"date-parts":[[2012,1,1]],"date-time":"2012-01-01T00:00:00Z","timestamp":1325376000000},"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":[[2012]]},"DOI":"10.1007\/978-3-642-28332-1_41","type":"book-chapter","created":{"date-parts":[[2012,2,29]],"date-time":"2012-02-29T09:45:36Z","timestamp":1330508736000},"page":"480-489","source":"Crossref","is-referenced-by-count":2,"title":["P\u2013NP Threshold for Synchronizing Road Coloring"],"prefix":"10.1007","author":[{"given":"Adam","family":"Roman","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"41_CR1","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1007\/BF02761605","volume":"27","author":"R.L. Adler","year":"1977","unstructured":"Adler, R.L., Goodwyn, L.W., Weiss, B.: Equivalence of topological Markov shifts. Israel J. of Math.\u00a027, 49\u201363 (1977)","journal-title":"Israel J. of Math."},{"key":"41_CR2","doi-asserted-by":"crossref","unstructured":"Adler, R.L., Weiss, B.: Similarity of automorphisms of the torus. Memoirs of the Amer. Math. Soc.\u00a098 (1970)","DOI":"10.1090\/memo\/0098"},{"key":"41_CR3","unstructured":"B\u00e9al, M.P., Perrin, D.: A quadratic algorithm for road coloring, arXiv:0803.0726v6 (2008)"},{"key":"41_CR4","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. of Computing\u00a019, 500\u2013510 (1990)","journal-title":"SIAM J. of Computing"},{"key":"41_CR5","doi-asserted-by":"publisher","first-page":"342","DOI":"10.1016\/j.ipl.2010.12.016","volume":"111","author":"A. Roman","year":"2011","unstructured":"Roman, A.: NP-completeness of the road coloring problem. Information Processing Letters\u00a0111, 342\u2013347 (2011)","journal-title":"Information Processing Letters"},{"key":"41_CR6","unstructured":"Trahtman, A.: A subquadratic algorithm for road coloring, arXiv:0801.2838v1 (2008)"},{"key":"41_CR7","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1007\/s11856-009-0062-5","volume":"172","author":"A.N. Trahtman","year":"2009","unstructured":"Trahtman, A.N.: Road coloring problem. Israel J. of Mathematics\u00a0172, 51\u201360 (2009)","journal-title":"Israel J. of Mathematics"},{"key":"41_CR8","unstructured":"Volkov, M.: Open problems on synchronizing automata. In: Conference \u2019Around the \u010cern\u00fd Conjecture\u2019 (2008)"},{"key":"41_CR9","unstructured":"Volkov, M.: Synchronizing automata and the road coloring theorem. In: Tutorial on Workshop on Algebra, Combinatorics and Complexity (2008)"}],"container-title":["Lecture Notes in Computer Science","Language and Automata Theory and Applications"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-28332-1_41","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,28]],"date-time":"2019-04-28T04:31:53Z","timestamp":1556425913000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-28332-1_41"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642283314","9783642283321"],"references-count":9,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-28332-1_41","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}