{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:16:53Z","timestamp":1759637813503,"version":"3.40.3"},"publisher-location":"Cham","reference-count":23,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319587462"},{"type":"electronic","value":"9783319587479"}],"license":[{"start":{"date-parts":[[2017,1,1]],"date-time":"2017-01-01T00:00:00Z","timestamp":1483228800000},"content-version":"unspecified","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":[[2017]]},"DOI":"10.1007\/978-3-319-58747-9_23","type":"book-chapter","created":{"date-parts":[[2017,5,5]],"date-time":"2017-05-05T01:14:05Z","timestamp":1493946845000},"page":"260-272","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Edit Distance Neighbourhoods of Input-Driven Pushdown Automata"],"prefix":"10.1007","author":[{"given":"Alexander","family":"Okhotin","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kai","family":"Salomaa","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2017,5,6]]},"reference":[{"issue":"4","key":"23_CR1","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1137\/0201022","volume":"1","author":"AV Aho","year":"1972","unstructured":"Aho, A.V., Peterson, T.G.: A minimum distance error-correcting parser for context-free languages. SIAM J. Comput. 1(4), 305\u2013312 (1972). http:\/\/dx.doi.org\/doi\/10.1137\/0201022","journal-title":"SIAM J. Comput."},{"key":"23_CR2","doi-asserted-by":"crossref","unstructured":"Alur, R., Madhusudan, P.: Visibly pushdown languages. In: ACM Symposium on Theory of Computing, STOC 2004, Chicago, USA 13\u201316 June 2004, pp. 202\u2013211 (2004). http:\/\/dx.doi.org\/10.1145\/1007352.1007390","DOI":"10.1145\/1007352.1007390"},{"key":"23_CR3","doi-asserted-by":"crossref","unstructured":"Alur, R., Madhusudan, P.: Adding nesting structure to words. J. ACM 56(3) (2009). http:\/\/dx.doi.org\/10.1145\/1516512.1516518","DOI":"10.1145\/1516512.1516518"},{"key":"23_CR4","first-page":"1","volume":"24","author":"B von Braunm\u00fchl","year":"1985","unstructured":"von Braunm\u00fchl, B., Verbeek, R.: Input driven languages are recognized in log $$n$$ space. Ann. Discrete Math. 24, 1\u201320 (1985). http:\/\/dx.doi.org\/10.1016\/S0304-0208(08)73072-X","journal-title":"Ann. Discrete Math."},{"key":"23_CR5","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). doi:10.1007\/11779148_12"},{"key":"23_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1007\/978-3-662-47666-6_10","volume-title":"Automata, Languages, and Programming","author":"K Chatterjee","year":"2015","unstructured":"Chatterjee, K., Henzinger, T.A., Ibsen-Jensen, R., Otop, J.: Edit distance for pushdown automata. In: Halld\u00f3rsson, M.M., Iwama, K., Kobayashi, N., Speckmann, B. (eds.) ICALP 2015. LNCS, vol. 9135, pp. 121\u2013133. Springer, Heidelberg (2015). doi:10.1007\/978-3-662-47666-6_10"},{"key":"23_CR7","doi-asserted-by":"publisher","first-page":"278","DOI":"10.1016\/j.ic.2016.02.001","volume":"247","author":"Y-S Han","year":"2016","unstructured":"Han, Y.-S., Ko, K., Salomaa, K.: Approximate matching between a context-free grammar and a finite-state automaton. Inf. Comput. 247, 278\u2013289 (2016). http:\/\/dx.doi.org\/10.1016\/j.ic.2016.02.001","journal-title":"Inf. Comput."},{"key":"23_CR8","doi-asserted-by":"publisher","first-page":"2961","DOI":"10.1016\/j.tcs.2009.01.004","volume":"410","author":"Y-S Han","year":"2009","unstructured":"Han, Y.-S., Salomaa, K.: Nondeterministic state complexity of nested word automata. Theoret. Comput. Sci. 410, 2961\u20132971 (2009)","journal-title":"Theoret. Comput. Sci."},{"key":"23_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"94","DOI":"10.1007\/978-3-319-23111-2_7","volume-title":"Machines, Computations, and Universality","author":"M Kutrib","year":"2015","unstructured":"Kutrib, M., Malcher, A., Wendlandt, M.: Tinput-driven pushdown automata. In: Durand-Lose, J., Nagy, B. (eds.) MCU 2015. LNCS, vol. 9288, pp. 94\u2013112. Springer, Cham (2015). doi:10.1007\/978-3-319-23111-2_7"},{"key":"23_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"422","DOI":"10.1007\/3-540-10003-2_89","volume-title":"Automata, Languages and Programming","author":"K Mehlhorn","year":"1980","unstructured":"Mehlhorn, K.: Pebbling mountain ranges and its application to DCFL-recognition. In: Bakker, J., Leeuwen, J. (eds.) ICALP 1980. LNCS, vol. 85, pp. 422\u2013435. Springer, Heidelberg (1980). doi:10.1007\/3-540-10003-2_89"},{"issue":"6","key":"23_CR11","doi-asserted-by":"publisher","first-page":"957","DOI":"10.1142\/S0129054103002114","volume":"14","author":"M Mohri","year":"2003","unstructured":"Mohri, M.: Edit-distance of weighted automata: general definitions and algorithms. Int. J. Found. Comput. Sci. 14(6), 957\u2013982 (2003)","journal-title":"Int. J. Found. Comput. Sci."},{"key":"23_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"264","DOI":"10.1007\/978-3-319-21500-6_21","volume-title":"Developments in Language Theory","author":"Y-S Han","year":"2015","unstructured":"Han, Y.-S., Ko, S.-K., Salomaa, K.: Generalizations of code languages with marginal errors. In: Potapov, I. (ed.) DLT 2015. LNCS, vol. 9168, pp. 264\u2013275. Springer, Cham (2015). doi:10.1007\/978-3-319-21500-6_21"},{"key":"23_CR13","series-title":"Emergence, Complexity and Computation","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1007\/978-3-319-46376-6_6","volume-title":"Emergent Computation","author":"T Ng","year":"2017","unstructured":"Ng, T., Rappaport, D., Salomaa, K.: Descriptional complexity of error detection. In: Adamatzky, A. (ed.) Emergent Computation. ECC, vol. 24, pp. 101\u2013119. Springer, Cham (2017). doi:10.1007\/978-3-319-46376-6_6"},{"key":"23_CR14","doi-asserted-by":"publisher","first-page":"52","DOI":"10.1016\/j.tcs.2016.01.007","volume":"618","author":"A Okhotin","year":"2016","unstructured":"Okhotin, A.: Input-driven languages are linear conjunctive. Theoret. Comput. Sci. 618, 52\u201371 (2016). http:\/\/dx.doi.org\/10.1016\/j.tcs.2016.01.007","journal-title":"Theoret. Comput. Sci."},{"issue":"2","key":"23_CR15","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1145\/2636805.2636821","volume":"45","author":"A Okhotin","year":"2014","unstructured":"Okhotin, A., Salomaa, K.: Complexity of input-driven pushdown automata. SIGACT News 45(2), 47\u201367 (2014). http:\/\/doi.acm.org\/10.1145\/2636805.2636821","journal-title":"SIGACT News"},{"key":"23_CR16","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.tcs.2014.11.015","volume":"566","author":"A Okhotin","year":"2015","unstructured":"Okhotin, A., Salomaa, K.: Descriptional complexity of unambiguous input-driven pushdown automata. Theoret. Comput. Sci. 566, 1\u201311 (2015). http:\/\/dx.doi.org\/10.1016\/j.tcs.2014.11.015","journal-title":"Theoret. Comput. Sci."},{"key":"23_CR17","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1016\/j.jcss.2017.02.001","volume":"86","author":"A Okhotin","year":"2017","unstructured":"Okhotin, A., Salomaa, K.: State complexity of operations on input-driven pushdown automata. J. Comput. Syst. Sci. 86, 207\u2013228 (2017). http:\/\/dx.doi.org\/10.1016\/j.jcss.2017.02.001","journal-title":"J. Comput. Syst. Sci."},{"key":"23_CR18","doi-asserted-by":"publisher","first-page":"3290","DOI":"10.1016\/j.tcs.2009.05.002","volume":"410","author":"X Piao","year":"2009","unstructured":"Piao, X., Salomaa, K.: Operational state complexity of nested word automata. Theoret. Comput. Sci. 410, 3290\u20133302 (2009). http:\/\/dx.doi.org\/10.1016\/j.tcs.2009.05.002","journal-title":"Theoret. Comput. Sci."},{"key":"23_CR19","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1006\/inco.2000.2914","volume":"165","author":"G Pighizzini","year":"2001","unstructured":"Pighizzini, G.: How hard is computing the edit distance? Inf. Comput. 165, 1\u201313 (2001)","journal-title":"Inf. Comput."},{"key":"23_CR20","unstructured":"Povarov, G.: Descriptive complexity of the Hamming neighborhood of a regular language. In: LATA 2007, pp. 509\u2013520 (2007)"},{"issue":"6","key":"23_CR21","doi-asserted-by":"publisher","first-page":"1407","DOI":"10.1142\/S0129054107005443","volume":"18","author":"K Salomaa","year":"2007","unstructured":"Salomaa, K., Schofield, P.N.: State complexity of additive weighted finite automata. Int. J. Found. Comput. Sci. 18(6), 1407\u20131416 (2007)","journal-title":"Int. J. Found. Comput. Sci."},{"issue":"2","key":"23_CR22","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1016\/0304-3975(91)90374-B","volume":"88","author":"H Seki","year":"1991","unstructured":"Seki, H., Matsumura, T., Fujii, M., Kasami, T.: On multiple context-free grammars. Theoret. Comput. Sci. 88(2), 191\u2013229 (1991). http:\/\/dx.doi.org\/10.1016\/0304-3975(91)90374-B","journal-title":"Theoret. Comput. Sci."},{"key":"23_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1007\/978-3-662-47221-7_19","volume-title":"Cellular Automata and Discrete Complex Systems","author":"V Terrier","year":"2015","unstructured":"Terrier, V.: Recognition of linear-slender context-free languages by real time one-way cellular automata. In: Kari, J. (ed.) AUTOMATA 2015. LNCS, vol. 9099, pp. 251\u2013262. Springer, Heidelberg (2015). doi:10.1007\/978-3-662-47221-7_19"}],"container-title":["Lecture Notes in Computer Science","Computer Science \u2013 Theory and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-58747-9_23","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,12]],"date-time":"2024-03-12T17:16:19Z","timestamp":1710263779000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-58747-9_23"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017]]},"ISBN":["9783319587462","9783319587479"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-58747-9_23","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2017]]},"assertion":[{"value":"6 May 2017","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"CSR","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Computer Science Symposium in Russia","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Kazan","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Russia","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2017","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"8 June 2017","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"12 June 2017","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"12","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"csr2017","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/logic.pdmi.ras.ru\/csr2017\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}