{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,22]],"date-time":"2026-09-22T04:02:04Z","timestamp":1790049724126,"version":"4.0.1"},"reference-count":21,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2013,11,13]],"date-time":"2013-11-13T00:00:00Z","timestamp":1384300800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2014,2]]},"DOI":"10.1007\/s00224-013-9511-y","type":"journal-article","created":{"date-parts":[[2013,11,12]],"date-time":"2013-11-12T00:57:26Z","timestamp":1384217846000},"page":"211-223","source":"Crossref","is-referenced-by-count":13,"title":["Approximating the Minimum Length of Synchronizing Words Is Hard"],"prefix":"10.1007","volume":"54","author":[{"given":"Mikhail V.","family":"Berlinkov","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2013,11,13]]},"reference":[{"key":"9511_CR1","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1007\/BF02761605","volume":"27","author":"R. Adler","year":"1977","unstructured":"Adler, R., Goodwyn, L., Weiss, B.: Equivalence of topological Markov shifts. Isr. J. Math. 27, 49\u201363 (1977)","journal-title":"Isr. J. Math."},{"key":"9511_CR2","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1007\/978-3-642-13182-0_4","volume":"6072","author":"M. Berlinkov","year":"2010","unstructured":"Berlinkov, M.: Approximating the minimum length of synchronizing words is hard. Lect. Notes Comput. Sci. 6072, 37\u201347 (2010)","journal-title":"Lect. Notes Comput. Sci."},{"issue":"2","key":"9511_CR3","doi-asserted-by":"crossref","first-page":"49","DOI":"10.17223\/20710410\/12\/4","volume":"2011","author":"M. Berlinkov","year":"2011","unstructured":"Berlinkov, M.: On the error of polynomial time computation for the optimal coloring of a graph into a synchronizing automaton. Discrete Appl. Math. 2011(2), 49\u201372 (2011) (in Russian)","journal-title":"Discrete Appl. Math."},{"issue":"3","key":"9511_CR4","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. Mat.-Fyz. Cas. Slov. Akad. Vied 14(3), 208\u2013216 (1964) (in Slovak)","journal-title":"Mat.-Fyz. Cas. Slov. Akad. Vied"},{"key":"9511_CR5","doi-asserted-by":"crossref","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":"9511_CR6","volume-title":"Computers and Intractability: a Guide to the Theory of NP-Completeness","author":"M. Garey","year":"1979","unstructured":"Garey, M., Johnson, D.: Computers and Intractability: a Guide to the Theory of NP-Completeness. Freeman, San Francisco (1979)"},{"key":"9511_CR7","series-title":"Talk in the Workshop \u201cAround the \u010cern\u00fd Conjecture\u201d","volume-title":"Complexity of the Approximation of the Shortest Synchronizing Word","author":"P. Gawrychowski","year":"2008","unstructured":"Gawrychowski, P.: Complexity of the Approximation of the Shortest Synchronizing Word. Talk in the Workshop \u201cAround the \u010cern\u00fd Conjecture\u201d. Univ. Wroc\u0142aw, Wroc\u0142aw (2008) (unpublished)"},{"key":"9511_CR8","doi-asserted-by":"crossref","first-page":"154","DOI":"10.1007\/978-3-642-18098-9_17","volume":"6482","author":"M. Gerbush","year":"2011","unstructured":"Gerbush, M., Heeringa, B.: Approximating minimum reset sequences. Lect. Notes Comput. Sci. 6482, 154\u2013162 (2011)","journal-title":"Lect. Notes Comput. Sci."},{"key":"9511_CR9","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1142\/S0218196795000185","volume":"5","author":"P. Goral\u010dik","year":"1995","unstructured":"Goral\u010dik, P., Koubek, V.: Rank problems for composite transformations. Int. J. Algebra Comput. 5, 309\u2013316 (1995)","journal-title":"Int. J. Algebra Comput."},{"key":"9511_CR10","first-page":"517","volume":"19","author":"P. Martyugin","year":"2009","unstructured":"Martyugin, P.: Complexity of problems concerning reset words for some partial cases of automata. Acta Cybern. 19, 517\u2013536 (2009)","journal-title":"Acta Cybern."},{"key":"9511_CR11","doi-asserted-by":"crossref","first-page":"288","DOI":"10.1007\/978-3-642-13182-0_27","volume":"6072","author":"P. Martyugin","year":"2010","unstructured":"Martyugin, P.: Complexity of problems concerning carefully synchronizing words for PFA and directing words for NFA. Lect. Notes Comput. Sci. 6072, 288\u2013302 (2010)","journal-title":"Lect. Notes Comput. Sci."},{"key":"9511_CR12","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1016\/j.tcs.2012.04.022","volume":"450","author":"P. Martyugin","year":"2012","unstructured":"Martyugin, P.: Complexity of problems concerning reset words for cyclic and Eulerian automata. Theor. Comput. Sci. 450, 3\u20139 (2012)","journal-title":"Theor. Comput. Sci."},{"key":"9511_CR13","doi-asserted-by":"crossref","first-page":"278","DOI":"10.1007\/978-3-642-31606-7_24","volume":"7381","author":"P. Martyugin","year":"2012","unstructured":"Martyugin, P.: Synchronization of automata with one undefined or ambiguous transition. Lect. Notes Comput. Sci. 7381, 278\u2013288 (2012)","journal-title":"Lect. Notes Comput. Sci."},{"key":"9511_CR14","doi-asserted-by":"crossref","first-page":"568","DOI":"10.1007\/978-3-642-15155-2_50","volume":"6281","author":"J. Olschewski","year":"2010","unstructured":"Olschewski, J., Ummels, M.: The complexity of finding reset words in finite automata. Lect. Notes Comput. Sci. 6281, 568\u2013579 (2010)","journal-title":"Lect. Notes Comput. Sci."},{"key":"9511_CR15","volume-title":"Computational Complexity","author":"C. Papadimitriou","year":"1994","unstructured":"Papadimitriou, C.: Computational Complexity. Addison-Wesley, Reading (1994)"},{"key":"9511_CR16","doi-asserted-by":"crossref","first-page":"342","DOI":"10.1016\/j.ipl.2010.12.016","volume":"111","author":"A. Roman","year":"2011","unstructured":"Roman, A.: The NP-completeness of the road coloring problem. Inf. Process. Lett. 111, 342\u2013347 (2011)","journal-title":"Inf. Process. Lett."},{"key":"9511_CR17","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1016\/j.amc.2008.06.019","volume":"209","author":"A. Roman","year":"2009","unstructured":"Roman, A.: Synchronizing finite automata with short reset words. Appl. Math. Comput. 209, 125\u2013136 (2009)","journal-title":"Appl. Math. Comput."},{"key":"9511_CR18","volume-title":"AutoMathA 2007. Automata: from Mathematics to Applications","author":"W. Samotij","year":"2007","unstructured":"Samotij, W.: A note on the complexity of the problem of finding shortest synchronizing words. In: AutoMathA 2007. Automata: from Mathematics to Applications. Univ. Palermo, Palermo (2007) (electronic)"},{"key":"9511_CR19","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. Theor. Comput. Sci. 292, 263\u2013281 (2003)","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"9511_CR20","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1007\/s11856-009-0062-5","volume":"172","author":"A. Trahtman","year":"2009","unstructured":"Trahtman, A.: The road coloring problem. Isr. J. Math. 172(1), 51\u201360 (2009)","journal-title":"Isr. J. Math."},{"key":"9511_CR21","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1007\/978-3-540-88282-4_4","volume":"5196","author":"M. Volkov","year":"2008","unstructured":"Volkov, M.: Synchronizing automata and the \u010cern\u00fd conjecture. Lect. Notes Comput. Sci. 5196, 11\u201327 (2008)","journal-title":"Lect. Notes Comput. Sci."}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-013-9511-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-013-9511-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-013-9511-y","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,8,7]],"date-time":"2020-08-07T18:58:12Z","timestamp":1596826692000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-013-9511-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,11,13]]},"references-count":21,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2014,2]]}},"alternative-id":["9511"],"URL":"https:\/\/doi.org\/10.1007\/s00224-013-9511-y","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,11,13]]}}}