{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,15]],"date-time":"2024-09-15T14:33:48Z","timestamp":1726410828874},"publisher-location":"Berlin, Heidelberg","reference-count":26,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662496299"},{"type":"electronic","value":"9783662496305"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-3-662-49630-5_15","type":"book-chapter","created":{"date-parts":[[2016,3,21]],"date-time":"2016-03-21T09:04:32Z","timestamp":1458551072000},"page":"252-268","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Synchronizing Automata over Nested Words"],"prefix":"10.1007","author":[{"given":"Dmitry","family":"Chistikov","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pavel","family":"Martyugin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mahsa","family":"Shirmohammadi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"3","key":"15_CR1","doi-asserted-by":"publisher","first-page":"16","DOI":"10.1145\/1516512.1516518","volume":"56","author":"R Alur","year":"2009","unstructured":"Alur, R., Madhusudan, P.: Adding nesting structure to words. J. ACM 56(3), 16 (2009)","journal-title":"J. ACM"},{"key":"15_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"120","DOI":"10.1007\/11779148_12","volume-title":"Developments in Language Theory","author":"D Caucal","year":"2006","unstructured":"Caucal, D.: Synchronization of pushdown automata. In: Ibarra, O.H., Dang, Z. (eds.) DLT 2006. LNCS, vol. 4036, pp. 120\u2013132. Springer, Heidelberg (2006)"},{"key":"15_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"70","DOI":"10.1007\/3-540-52282-4_33","volume-title":"STACS 90","author":"MP Chytil","year":"1990","unstructured":"Chytil, M.P., Monien, B.: Caterpillars and context-free languages. In: Choffrut, C., Lengauer, T. (eds.) STACS 90. LNCS, vol. 415, pp. 70\u201381. Springer, Heidelberg (1990)"},{"key":"15_CR4","unstructured":"Comon, H., Dauchet, M., Gilleron, R., L\u00f6ding, C., Jacquemard, F., Lugiez, D., Tison, S., Tommasi, M.: Tree Automata Techniques and Applications, 12 October 2007. \n                      http:\/\/www.grappa.univ-lille3.fr\/tata"},{"key":"15_CR5","unstructured":"Doyen, L., Juhl, L., Larsen, K.G., Markey, N., Shirmohammadi, M.: Synchronizing words for weighted and timed automata. In: 34th International Conference on Foundation of Software Technology and Theoretical Computer Science, FSTTCS, 15\u201317 December 2014, New Delhi, India, pp. 121\u2013132 (2014)"},{"key":"15_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"665","DOI":"10.1007\/978-3-642-31424-7_47","volume-title":"Computer Aided Verification","author":"E Driscoll","year":"2012","unstructured":"Driscoll, E., Thakur, A., Reps, T.: OpenNWA: a nested-word automaton library. In: Madhusudan, P., Seshia, S.A. (eds.) CAV 2012. LNCS, vol. 7358, pp. 665\u2013671. Springer, Heidelberg (2012)"},{"issue":"3","key":"15_CR7","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(3), 500\u2013510 (1990)","journal-title":"SIAM J. Comput."},{"issue":"8","key":"15_CR8","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1145\/368892.368907","volume":"1","author":"AP Ershov","year":"1958","unstructured":"Ershov, A.P.: On programming of arithmetic operations. Commun. ACM 1(8), 3\u20139 (1958)","journal-title":"Commun. ACM"},{"issue":"12","key":"15_CR9","doi-asserted-by":"publisher","first-page":"614","DOI":"10.1016\/j.ipl.2011.03.019","volume":"111","author":"J Esparza","year":"2011","unstructured":"Esparza, J., Ganty, P., Kiefer, S., Luttenberger, M.: Parikh\u2019s theorem: a simple and direct automaton construction. Inf. Process. Lett. 111(12), 614\u2013619 (2011)","journal-title":"Inf. Process. Lett."},{"key":"15_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"124","DOI":"10.1007\/978-3-642-39799-8_8","volume-title":"Computer Aided Verification","author":"J Esparza","year":"2013","unstructured":"Esparza, J., Ganty, P., Majumdar, R.: Parameterized verification of asynchronous shared-memory systems. In: Sharygina, N., Veith, H. (eds.) CAV 2013. LNCS, vol. 8044, pp. 124\u2013140. Springer, Heidelberg (2013)"},{"key":"15_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-319-04921-2_1","volume-title":"Language and Automata Theory and Applications","author":"J Esparza","year":"2014","unstructured":"Esparza, J., Luttenberger, M., Schlund, M.: A brief history of Strahler numbers. In: Dediu, A.-H., Mart\u00edn-Vide, C., Sierra-Rodr\u00edguez, J.-L., Truthe, B. (eds.) LATA 2014. LNCS, vol. 8370, pp. 1\u201313. Springer, Heidelberg (2014)"},{"issue":"6","key":"15_CR12","doi-asserted-by":"publisher","first-page":"765","DOI":"10.1142\/S0129054113400170","volume":"24","author":"FM Fominykh","year":"2013","unstructured":"Fominykh, F.M., Martyugin, P.V., Volkov, M.V.: P(l)aying for synchronization. Int. J. Found. Comput. Sci. 24(6), 765\u2013780 (2013)","journal-title":"Int. J. Found. Comput. Sci."},{"issue":"2","key":"15_CR13","doi-asserted-by":"publisher","first-page":"332","DOI":"10.1145\/322003.322015","volume":"24","author":"JE Hopcroft","year":"1977","unstructured":"Hopcroft, J.E., Paul, W.J., Valiant, L.G.: On time versus space. J. ACM 24(2), 332\u2013337 (1977)","journal-title":"J. ACM"},{"key":"15_CR14","doi-asserted-by":"crossref","unstructured":"Kozen, D.: Lower bounds for natural proof systems. In: 18th Annual Symposium on Foundations of Computer Science, Providence, Rhode Island, USA, 31 October\u20131 November, pp. 254\u2013266 (1977)","DOI":"10.1109\/SFCS.1977.16"},{"issue":"4\/5","key":"15_CR15","doi-asserted-by":"publisher","first-page":"184","DOI":"10.1016\/0020-0190(80)90136-2","volume":"10","author":"T Lengauer","year":"1980","unstructured":"Lengauer, T., Tarjan, R.E.: The space complexity of pebble games on trees. Inf. Process. Lett. 10(4\/5), 184\u2013188 (1980)","journal-title":"Inf. Process. Lett."},{"issue":"2","key":"15_CR16","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. Theor. Comput. Syst. 54(2), 293\u2013304 (2014)","journal-title":"Theor. Comput. Syst."},{"key":"15_CR17","doi-asserted-by":"crossref","first-page":"422","DOI":"10.1007\/3-540-10003-2_89","volume-title":"Automata, Languages and Programming","author":"Kurt Mehlhorn","year":"1980","unstructured":"Mehlhorn, K.: Pebbling moutain ranges and its application of DCFL-recognition. In: Proceedings Automata, Languages and Programming, 7th Colloquium, Noordweijkerhout, The Netherland, July 14\u201318, pp. 422\u2013435 (1980)"},{"key":"15_CR18","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. 6281, pp. 568\u2013579. Springer, Heidelberg (2010)"},{"key":"15_CR19","unstructured":"Paterson, M.S., Hewitt, C.E.: Comparative schematology. In: Record of the Project MAC Conference on Concurrent Systems and Parallel Computation, pp. 119\u2013127. ACM, MIT AI Memo AIM-201 (1970). \n                      http:\/\/hdl.handle.net\/1721.1\/5851"},{"key":"15_CR20","doi-asserted-by":"publisher","first-page":"535","DOI":"10.1016\/S0304-0208(08)73432-7","volume":"75","author":"J-\u00c9 Pin","year":"1983","unstructured":"Pin, J.-\u00c9.: On two combinatorial problems arising from automata theory. North-Holland Math. Stud. 75, 535\u2013548 (1983)","journal-title":"North-Holland Math. Stud."},{"issue":"3","key":"15_CR21","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1016\/0020-0190(83)90067-4","volume":"16","author":"IK Rystsov","year":"1983","unstructured":"Rystsov, I.K.: Polynomial complete problems in automata theory. Inf. Process. Lett. 16(3), 147\u2013151 (1983)","journal-title":"Inf. Process. Lett."},{"key":"15_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1007\/11498490_2","volume-title":"Model-Based Testing of Reactive Systems","author":"S Sandberg","year":"2005","unstructured":"Sandberg, S.: Homing and synchronizing sequences. In: Broy, M., Jonsson, B., Katoen, J.-P., Leucker, M., Pretschner, A. (eds.) Model-Based Testing of Reactive Systems. LNCS, vol. 3472, pp. 5\u201333. Springer, Heidelberg (2005)"},{"key":"15_CR23","volume-title":"Models of Computation - Exploring the Power of Computing","author":"JE Savage","year":"1998","unstructured":"Savage, J.E.: Models of Computation - Exploring the Power of Computing. Addison-Wesley, Boston (1998)"},{"issue":"4","key":"15_CR24","first-page":"289","volume":"7","author":"J \u010cern\u00fd","year":"1971","unstructured":"\u010cern\u00fd, J., Pirick\u00e1, A., Rosenauerov\u00e1, B.: On directable automata. Kybernetika 7(4), 289\u2013298 (1971)","journal-title":"Kybernetika"},{"key":"15_CR25","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 \u010cern\u00fd conjecture. In: Mart\u00edn-Vide, C., Otto, F., Fernau, H. (eds.) LATA 2008. LNCS, vol. 5196, pp. 11\u201327. Springer, Heidelberg (2008)"},{"key":"15_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"354","DOI":"10.1007\/978-3-662-43951-7_30","volume-title":"Automata, Languages, and Programming","author":"M Wehar","year":"2014","unstructured":"Wehar, M.: Hardness results for intersection non-emptiness. In: Esparza, J., Fraigniaud, P., Husfeldt, T., Koutsoupias, E. (eds.) ICALP 2014, Part II. LNCS, vol. 8573, pp. 354\u2013362. Springer, Heidelberg (2014)"}],"container-title":["Lecture Notes in Computer Science","Foundations of Software Science and Computation Structures"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-49630-5_15","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,3,24]],"date-time":"2020-03-24T01:07:17Z","timestamp":1585012037000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-49630-5_15"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783662496299","9783662496305"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-49630-5_15","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2016]]},"assertion":[{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}