{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,28]],"date-time":"2026-09-28T16:10:12Z","timestamp":1790611812850,"version":"4.1.0"},"publisher-location":"Cham","reference-count":16,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783319519623","type":"print"},{"value":"9783319519630","type":"electronic"}],"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":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2017]]},"DOI":"10.1007\/978-3-319-51963-0_30","type":"book-chapter","created":{"date-parts":[[2017,1,10]],"date-time":"2017-01-10T06:17:39Z","timestamp":1484029059000},"page":"387-401","source":"Crossref","is-referenced-by-count":5,"title":["Edit-Distance Between Visibly Pushdown Languages"],"prefix":"10.1007","author":[{"given":"Yo-Sub","family":"Han","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sang-Ki","family":"Ko","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2017,1,11]]},"reference":[{"key":"30_CR1","doi-asserted-by":"crossref","unstructured":"Alur, R.: Marrying words and trees. In: Proceedings of the 26th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS 2007, pp. 233\u2013242 (2007)","DOI":"10.1145\/1265530.1265564"},{"key":"30_CR2","doi-asserted-by":"crossref","unstructured":"Alur, R., Madhusudan, P.: Visibly pushdown languages. In: Proceedings of the 36th Annual ACM Symposium on Theory of Computing, pp. 202\u2013211 (2004)","DOI":"10.1145\/1007352.1007390"},{"key":"30_CR3","doi-asserted-by":"crossref","unstructured":"B\u00e1r\u00e1ny, V., L\u00f6ding, C., Serre, O.: Regularity problems for visibly pushdown languages. In: Proceedings of the 23rd Annual Symposium on Theoretical Aspects of Computer Science, pp. 420\u2013431 (2006)","DOI":"10.1007\/11672142_34"},{"issue":"1","key":"30_CR4","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1016\/S0304-3975(01)00238-9","volume":"286","author":"C Choffrut","year":"2002","unstructured":"Choffrut, C., Pighizzini, G.: Distances between languages and reflexivity of relations. Theor. Comput. Sci. 286(1), 117\u2013138 (2002)","journal-title":"Theor. Comput. Sci."},{"issue":"7","key":"30_CR5","doi-asserted-by":"crossref","first-page":"1067","DOI":"10.1142\/S0129054113400315","volume":"24","author":"Y-S Han","year":"2013","unstructured":"Han, Y.-S., Ko, S.-K., Salomaa, K.: The edit-distance between a regular language and a context-free language. Int. J. Found. Comput. Sci. 24(7), 1067\u20131082 (2013)","journal-title":"Int. J. Found. Comput. Sci."},{"key":"30_CR6","volume-title":"Introduction to Automata Theory, Languages, and Computation","author":"J Hopcroft","year":"1979","unstructured":"Hopcroft, J., Ullman, J.: Introduction to Automata Theory, Languages, and Computation, 2nd edn. Addison-Wesley, Reading (1979)","edition":"2"},{"key":"30_CR7","first-page":"293","volume":"9","author":"L Kari","year":"2004","unstructured":"Kari, L., Konstantinidis, S.: Descriptional complexity of error\/edit systems. J. Automata, Lang. Comb. 9, 293\u2013309 (2004)","journal-title":"J. Automata, Lang. Comb."},{"key":"30_CR8","unstructured":"Leike, J.: VPL intersection emptiness. Bachelor\u2019s Thesis, University of Freiburg (2010)"},{"issue":"8","key":"30_CR9","first-page":"707","volume":"10","author":"VI Levenshtein","year":"1966","unstructured":"Levenshtein, V.I.: Binary codes capable of correcting deletions, insertions, and reversals. Sov. Phys. Dokl. 10(8), 707\u2013710 (1966)","journal-title":"Sov. Phys. Dokl."},{"key":"30_CR10","doi-asserted-by":"crossref","unstructured":"Mehlhorn, K.: Pebbling mountain ranges and its application to DCFL-recognition. In: Automata, Languages and Programming, vol. 85, pp. 422\u2013435 (1980)","DOI":"10.1007\/3-540-10003-2_89"},{"issue":"6","key":"30_CR11","doi-asserted-by":"crossref","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."},{"issue":"1\u20132","key":"30_CR12","doi-asserted-by":"crossref","first-page":"150","DOI":"10.14778\/1920841.1920865","volume":"3","author":"B Mozafari","year":"2010","unstructured":"Mozafari, B., Zeng, K., Zaniolo, C.: From regular expressions to nested words: unifying languages and query execution for relational and XML sequences. Proc. VLDB Endowment 3(1\u20132), 150\u2013161 (2010)","journal-title":"Proc. VLDB Endowment"},{"key":"30_CR13","doi-asserted-by":"crossref","DOI":"10.7551\/mitpress\/2022.001.0001","volume-title":"Computational Molecular Biology - An Algorithmic Approach","author":"PA Pevzner","year":"2000","unstructured":"Pevzner, P.A.: Computational Molecular Biology - An Algorithmic Approach. MIT Press, Cambridge (2000)"},{"issue":"6","key":"30_CR14","doi-asserted-by":"crossref","first-page":"419","DOI":"10.1145\/363347.363387","volume":"11","author":"K Thompson","year":"1968","unstructured":"Thompson, K.: Regular expression search algorithm. Commun. ACM 11(6), 419\u2013422 (1968)","journal-title":"Commun. ACM"},{"key":"30_CR15","doi-asserted-by":"crossref","first-page":"168","DOI":"10.1145\/321796.321811","volume":"21","author":"RA Wagner","year":"1974","unstructured":"Wagner, R.A., Fischer, M.J.: The string-to-string correction problem. J. ACM 21, 168\u2013173 (1974)","journal-title":"J. ACM"},{"key":"30_CR16","volume-title":"Theory of Computation","author":"D Wood","year":"1987","unstructured":"Wood, D.: Theory of Computation. Harper & Row, New York (1987)"}],"container-title":["Lecture Notes in Computer Science","SOFSEM 2017: Theory and Practice of Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-51963-0_30","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,17]],"date-time":"2019-09-17T10:03:52Z","timestamp":1568714632000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-51963-0_30"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017]]},"ISBN":["9783319519623","9783319519630"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-51963-0_30","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017]]}}}