{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,26]],"date-time":"2026-09-26T02:54:08Z","timestamp":1790391248775,"version":"4.1.0"},"reference-count":16,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2013,11,14]],"date-time":"2013-11-14T00:00:00Z","timestamp":1384387200000},"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-9516-6","type":"journal-article","created":{"date-parts":[[2013,11,12]],"date-time":"2013-11-12T20:13:22Z","timestamp":1384287202000},"page":"293-304","source":"Crossref","is-referenced-by-count":26,"title":["Computational Complexity of Certain Problems Related to Carefully Synchronizing Words for Partial Automata and Directing Words for Nondeterministic Automata"],"prefix":"10.1007","volume":"54","author":[{"given":"Pavel","family":"Martyugin","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2013,11,14]]},"reference":[{"key":"9516_CR1","first-page":"301","volume":"12","author":"H.-D. Burkhard","year":"1976","unstructured":"Burkhard, H.-D.: Zum L\u00e4ngenproblem homogener Experimente an determinierten und nicht-deterministischen Automaten. Elektron. Inf.verarb. Kybern. 12, 301\u2013306 (1976) (in German)","journal-title":"Elektron. Inf.verarb. Kybern."},{"key":"9516_CR2","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. Mat.-Fyz. Cas. Slov. Akad. Vied 14, 208\u2013216 (1964) (in Slovak)","journal-title":"Mat.-Fyz. Cas. Slov. Akad. Vied"},{"key":"9516_CR3","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":"9516_CR4","doi-asserted-by":"crossref","first-page":"986","DOI":"10.1016\/j.ipl.2009.05.007","volume":"109","author":"Z. Gazdag","year":"2009","unstructured":"Gazdag, Z., Iv\u00e1n, S., Nagy-Gy\u00f6rgy, J.: Improved upper bounds on synchronizing nondeterministic automata. Inf. Process. Lett. 109, 986\u2013990 (2009)","journal-title":"Inf. Process. Lett."},{"key":"9516_CR5","first-page":"105","volume":"14","author":"B. Imreh","year":"1999","unstructured":"Imreh, B., Steinby, M.: Directable nondeterministic automata. Acta Cybern. 14, 105\u2013115 (1999)","journal-title":"Acta Cybern."},{"key":"9516_CR6","first-page":"37","volume":"16","author":"B. Imreh","year":"2003","unstructured":"Imreh, B., Imreh, Cs., Ito, M.: On directable nondeterministic trapped automata. Acta Cybern. 16, 37\u201345 (2003)","journal-title":"Acta Cybern."},{"key":"9516_CR7","series-title":"Lect. Notes Comput. Sci.","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1007\/978-3-540-27812-2_12","volume-title":"Theory Is Forever","author":"M. Ito","year":"2004","unstructured":"Ito, M., Shikishima-Tsuji, K.: Some results on directable automata. In: Theory Is Forever. Lect. Notes Comput. Sci., vol. 3113, pp. 125\u2013133 (2004)"},{"key":"9516_CR8","doi-asserted-by":"crossref","DOI":"10.1142\/4791","volume-title":"Algebraic Theory of Automata and Languages","author":"M. Ito","year":"2004","unstructured":"Ito, M.: Algebraic Theory of Automata and Languages. World Scientific, Singapore (2004)"},{"key":"9516_CR9","first-page":"254","volume-title":"Proceedings of the 18th Annual Symposium on Foundations of Computer Science","author":"D. Kozen","year":"1977","unstructured":"Kozen, D.: Lower bounds for natural proof systems. In: Proceedings of the 18th Annual Symposium on Foundations of Computer Science, pp. 254\u2013266 (1977)"},{"issue":"4","key":"9516_CR10","first-page":"44","volume":"15","author":"P. Martyugin","year":"2008","unstructured":"Martyugin, P.: Lower bounds for the length of the shortest carefully synchronizing words for two- and three-letter partial automata. Diskretn. Anal. Issled. Oper. 15(4), 44\u201356 (2008) (in Russian)","journal-title":"Diskretn. Anal. Issled. Oper."},{"issue":"1","key":"9516_CR11","doi-asserted-by":"crossref","first-page":"46","DOI":"10.3103\/S1066369X10010056","volume":"54","author":"P. Martyugin","year":"2010","unstructured":"Martyugin, P.: A lower bound for the length of the shortest carefully synchronizing words. Russ. Math. 54(1), 46\u201354 (2010)","journal-title":"Russ. Math."},{"key":"9516_CR12","series-title":"Lect. Notes Comput. Sci.","doi-asserted-by":"crossref","first-page":"288","DOI":"10.1007\/978-3-642-13182-0_27","volume-title":"Proceedings of the 5th International Computer Science Symposium in Russia, CSR 2010","author":"P. Martyugin","year":"2010","unstructured":"Martyugin, P.: Complexity of problems concerning carefully synchronizing words for PFA and directing words for NFA. In: Proceedings of the 5th International Computer Science Symposium in Russia, CSR 2010. Lect. Notes Comput. Sci., vol. 6072, pp. 288\u2013302 (2010)"},{"key":"9516_CR13","series-title":"Lect. Notes Comput. Sci.","doi-asserted-by":"crossref","first-page":"278","DOI":"10.1007\/978-3-642-31606-7_24","volume-title":"Proceedings of the 17th International Conference on Imprelemenation and Application of Automata, CIAA 2012","author":"P. Martyugin","year":"2012","unstructured":"Martyugin, P.: Synchronization of automata with one undefined or ambiguous transition. In: Proceedings of the 17th International Conference on Imprelemenation and Application of Automata, CIAA 2012. Lect. Notes Comput. Sci., vol. 7381, pp. 278\u2013288 (2012)"},{"key":"9516_CR14","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1016\/S0022-0000(70)80006-X","volume":"4","author":"W.J. Savitch","year":"1970","unstructured":"Savitch, W.J.: Relationship between nondeterministic and deterministic tape classes. J. Comput. Syst. Sci. 4, 177\u2013192 (1970)","journal-title":"J. Comput. Syst. Sci."},{"key":"9516_CR15","series-title":"Lect. Notes Comput. Sci.","doi-asserted-by":"crossref","first-page":"173","DOI":"10.1007\/978-3-642-22953-4_15","volume-title":"Proceedings of 18th International Symposium on Fundamentals of Computation Theory, FCT 2011","author":"A.N. Trahtman","year":"2011","unstructured":"Trahtman, A.N.: Modifying the upper bound on the length of minimal synchronizing word. In: Proceedings of 18th International Symposium on Fundamentals of Computation Theory, FCT 2011. Lect. Notes Comput. Sci., vol. 6914, pp. 173\u2013180 (2011)"},{"key":"9516_CR16","series-title":"Lect. Notes Comput. Sci.","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1007\/978-3-540-88282-4_4","volume-title":"Proceedings of the 2nd International Conference on Language and Automata Theory and Applications, LATA 2008","author":"M.V. Volkov","year":"2008","unstructured":"Volkov, M.V.: Synchronizing automata and the \u010cern\u00fd conjecture. In: Proceedings of the 2nd International Conference on Language and Automata Theory and Applications, LATA 2008. Lect. Notes Comput. Sci., pp. 11\u201327 (2008)"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-013-9516-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-013-9516-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-013-9516-6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,24]],"date-time":"2019-05-24T07:54:26Z","timestamp":1558684466000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-013-9516-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,11,14]]},"references-count":16,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2014,2]]}},"alternative-id":["9516"],"URL":"https:\/\/doi.org\/10.1007\/s00224-013-9516-6","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,11,14]]}}}