{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:20:21Z","timestamp":1759638021923},"publisher-location":"Cham","reference-count":12,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319096971"},{"type":"electronic","value":"9783319096988"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-319-09698-8_6","type":"book-chapter","created":{"date-parts":[[2014,8,18]],"date-time":"2014-08-18T00:52:51Z","timestamp":1408323171000},"page":"61-67","source":"Crossref","is-referenced-by-count":11,"title":["On Two Algorithmic Problems about Synchronizing Automata"],"prefix":"10.1007","author":[{"given":"Mikhail V.","family":"Berlinkov","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"2","key":"6_CR1","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1145\/1150334.1150336","volume":"2","author":"N. Alon","year":"2006","unstructured":"Alon, N., Moshkovitz, D., Safra, S.: Algorithmic construction of sets for k-restrictions. ACM Trans. Algorithms\u00a02(2), 153\u2013177 (2006)","journal-title":"ACM Trans. Algorithms"},{"issue":"2","key":"6_CR2","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1007\/s00224-013-9511-y","volume":"54","author":"M. Berlinkov","year":"2014","unstructured":"Berlinkov, M.: Approximating the minimum length of synchronizing words is hard. Theory Comput. Syst.\u00a054(2), 211\u2013223 (2014)","journal-title":"Theory Comput. Syst."},{"key":"6_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"82","DOI":"10.1007\/978-3-642-22321-1_8","volume-title":"Developments in Language Theory","author":"P. Bonizzoni","year":"2011","unstructured":"Bonizzoni, P., Jonoska, N.: Regular splicing languages must have a constant. In: Mauri, G., Leporati, A. (eds.) DLT 2011. LNCS, vol.\u00a06795, pp. 82\u201392. Springer, Heidelberg (2011)"},{"key":"6_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. Comput.\u00a019, 500\u2013510 (1990)","journal-title":"SIAM J. Comput."},{"key":"6_CR5","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.\u00a06482, pp. 154\u2013162. Springer, Heidelberg (2011)"},{"key":"6_CR6","doi-asserted-by":"publisher","first-page":"383","DOI":"10.1016\/0012-365X(75)90058-8","volume":"13","author":"L. Lov\u00e1sz","year":"1975","unstructured":"Lov\u00e1sz, L.: On the ratio of optimal integral and fractional covers. Discr. Math.\u00a013, 383\u2013390 (1975)","journal-title":"Discr. Math."},{"issue":"2","key":"6_CR7","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1007\/s00224-013-9516-6","volume":"54","author":"P. Martyugin","year":"2014","unstructured":"Martyugin, P.: Computational complexity of certain problems related to carefully synchronizing words for partial automata and directing words for nondeterministic automata. Theory Comput. Syst.\u00a054(2), 293\u2013304 (2014)","journal-title":"Theory Comput. Syst."},{"key":"6_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"568","DOI":"10.1007\/978-3-642-15155-2_50","volume-title":"Mathematical Foundations of Computer Science 2010","author":"J. Olschewski","year":"2010","unstructured":"Olschewski, J., Ummels, M.: The complexity of finding reset words in finite automata. In: Hlin\u011bn\u00fd, P., Ku\u010dera, A. (eds.) MFCS 2010. LNCS, vol.\u00a06281, pp. 568\u2013579. Springer, Heidelberg (2010)"},{"issue":"2","key":"6_CR9","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1016\/S0022-0000(70)80006-X","volume":"4","author":"W. Savitch","year":"1970","unstructured":"Savitch, W.: Relationships between nondeterministic and deterministic tape complexities, J. Comp. System Sci.\u00a04(2), 177\u2013192 (1970)","journal-title":"Comp. System Sci."},{"key":"6_CR10","doi-asserted-by":"crossref","unstructured":"Slavik, P.: A tight analysis of the greedy algorithm for set cover. In: Proc. 28th ACM Symp. on Theory of Computing, pp. 435\u2013441 (1996)","DOI":"10.1145\/237814.237991"},{"issue":"5","key":"6_CR11","doi-asserted-by":"publisher","first-page":"1181","DOI":"10.1007\/s10955-011-0342-4","volume":"145","author":"N. Travers","year":"2011","unstructured":"Travers, N., Crutchfield, J.: Exact synchronization for finite-state sources. J. Stat. Phys.\u00a0145(5), 1181\u20131201 (2011)","journal-title":"J. Stat. Phys."},{"key":"6_CR12","unstructured":"Vojt\u011bch, V.: Subset synchronization of transitive automata, arXiv:1403.3972 (accepted to AFL 2014)"}],"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-09698-8_6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,27]],"date-time":"2019-05-27T16:24:22Z","timestamp":1558974262000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-09698-8_6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783319096971","9783319096988"],"references-count":12,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-09698-8_6","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]}}}