{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,9]],"date-time":"2024-09-09T18:10:51Z","timestamp":1725905451952},"publisher-location":"Cham","reference-count":20,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319628080"},{"type":"electronic","value":"9783319628097"}],"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-62809-7_21","type":"book-chapter","created":{"date-parts":[[2017,7,20]],"date-time":"2017-07-20T04:37:57Z","timestamp":1500525477000},"page":"284-295","source":"Crossref","is-referenced-by-count":0,"title":["Relative Prefix Distance Between Languages"],"prefix":"10.1007","author":[{"given":"Timothy","family":"Ng","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"David","family":"Rappaport","sequence":"additional","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,7,21]]},"reference":[{"key":"21_CR1","doi-asserted-by":"crossref","unstructured":"Alur, R., Madhusudan, P.: Adding nesting structure to words. J. ACM 56(3) (2009)","DOI":"10.1145\/1516512.1516518"},{"issue":"1","key":"21_CR2","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1016\/S0304-3975(01)00214-6","volume":"292","author":"MP B\u00e9al","year":"2003","unstructured":"B\u00e9al, M.P., Carton, O., Prieur, C., Sakarovitch, J.: Squaring transducers: an efficient procedure for deciding functionality and sequentiality. Theor. Comput. Sci. 292(1), 45\u201363 (2003)","journal-title":"Theor. Comput. Sci."},{"issue":"8","key":"21_CR3","doi-asserted-by":"crossref","first-page":"1302","DOI":"10.1016\/j.jcss.2013.06.001","volume":"79","author":"M Benedikt","year":"2013","unstructured":"Benedikt, M., Puppis, G., Riveros, C.: Bounded repairability of word languages. J. Comput. Syst. Sci. 79(8), 1302\u20131321 (2013)","journal-title":"J. Comput. Syst. Sci."},{"key":"21_CR4","doi-asserted-by":"crossref","first-page":"38","DOI":"10.1016\/j.tcs.2014.04.021","volume":"539","author":"M Benedikt","year":"2014","unstructured":"Benedikt, M., Puppis, G., Riveros, C.: The per-character cost of repairing word languages. Theor. Comput. Sci. 539, 38\u201367 (2014)","journal-title":"Theor. Comput. Sci."},{"key":"21_CR5","doi-asserted-by":"crossref","first-page":"303","DOI":"10.1051\/ita:2006010","volume":"40","author":"D Bruschi","year":"2006","unstructured":"Bruschi, D., Pighizzini, G.: String distances and intrusion detection: bridging the gap between formal languages and computer security. RAIRO Inform. Th\u00e9or. et Appl. 40, 303\u2013313 (2006)","journal-title":"RAIRO Inform. Th\u00e9or. et Appl."},{"issue":"2","key":"21_CR6","first-page":"141","volume":"8","author":"CS Calude","year":"2002","unstructured":"Calude, C.S., Salomaa, K., Yu, S.: Additive distances and quasi-distances between words. J. Univ. Comput. Sci. 8(2), 141\u2013152 (2002)","journal-title":"J. Univ. Comput. Sci."},{"key":"21_CR7","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:\n10.1007\/978-3-662-47666-6_10"},{"issue":"1","key":"21_CR8","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."},{"key":"21_CR9","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-00234-2","volume-title":"Encyclopedia of Distances","author":"MM Deza","year":"2009","unstructured":"Deza, M.M., Deza, E.: Encyclopedia of Distances. Springer, Heidelberg (2009)"},{"key":"21_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"387","DOI":"10.1007\/978-3-319-51963-0_30","volume-title":"SOFSEM 2017: Theory and Practice of Computer Science","author":"Y-S Han","year":"2017","unstructured":"Han, Y.-S., Ko, S.-K.: Edit-distance between visibly pushdown languages. In: Steffen, B., Baier, C., Brand, M., Eder, J., Hinchey, M., Margaria, T. (eds.) SOFSEM 2017. LNCS, vol. 10139, pp. 387\u2013401. Springer, Cham (2017). doi:\n10.1007\/978-3-319-51963-0_30"},{"issue":"07","key":"21_CR11","doi-asserted-by":"crossref","first-page":"1067","DOI":"10.1142\/S0129054113400315","volume":"24","author":"YS 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(07), 1067\u20131082 (2013)","journal-title":"Int. J. Found. Comput. Sci."},{"key":"21_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"419","DOI":"10.1007\/978-3-319-04298-5_37","volume-title":"SOFSEM 2014: Theory and Practice of Computer Science","author":"M Kutrib","year":"2014","unstructured":"Kutrib, M., Meckel, K., Wendlandt, M.: Parameterized prefix distance between regular languages. In: Geffert, V., Preneel, B., Rovan, B., \u0160tuller, J., Tjoa, A.M. (eds.) SOFSEM 2014. LNCS, vol. 8327, pp. 419\u2013430. Springer, Cham (2014). doi:\n10.1007\/978-3-319-04298-5_37"},{"issue":"6","key":"21_CR13","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."},{"key":"21_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"224","DOI":"10.1007\/978-3-319-40946-7_19","volume-title":"Implementation and Application of Automata","author":"T Ng","year":"2016","unstructured":"Ng, T.: Prefix distance between regular languages. In: Han, Y.-S., Salomaa, K. (eds.) CIAA 2016. LNCS, vol. 9705, pp. 224\u2013235. Springer, Cham (2016). doi:\n10.1007\/978-3-319-40946-7_19"},{"key":"21_CR15","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: A Festschrift for Selim G. Akl","author":"T Ng","year":"2017","unstructured":"Ng, T., Rappaport, D., Salomaa, K.: Descriptional complexity of error detection. In: Adamatzky, A. (ed.) Emergent Computation: A Festschrift for Selim G. Akl. ECC, vol. 24, pp. 101\u2013119. Springer, Cham (2017). doi:\n10.1007\/978-3-319-46376-6_6"},{"key":"21_CR16","doi-asserted-by":"crossref","first-page":"107","DOI":"10.1016\/j.tcs.2016.05.018","volume":"679","author":"T Ng","year":"2017","unstructured":"Ng, T., Rappaport, D., Salomaa, K.: State complexity of prefix distance. Theor. Comput. Sci. 679, 107\u2013117 (2017)","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"21_CR17","doi-asserted-by":"crossref","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), 1\u201313 (2001)","journal-title":"Inf. Comput."},{"key":"21_CR18","volume-title":"A Second Course in Formal Languages and Automata Theory","author":"J Shallit","year":"2009","unstructured":"Shallit, J.: A Second Course in Formal Languages and Automata Theory. Cambridge University Press, Cambridge (2009)"},{"issue":"1","key":"21_CR19","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1016\/j.jda.2008.09.011","volume":"7","author":"M Skala","year":"2009","unstructured":"Skala, M.: Counting distance permutations. J. Discrete Algorithms 7(1), 49\u201361 (2009)","journal-title":"J. Discrete Algorithms"},{"key":"21_CR20","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1007\/978-3-642-59136-5_2","volume-title":"Handbook of Formal Languages","author":"S Yu","year":"1997","unstructured":"Yu, S.: Regular languages. In: Rozenberg, G., Salomaa, A. (eds.) Handbook of Formal Languages, pp. 41\u2013110. Springer, Heidelberg (1997). doi:\n10.1007\/978-3-642-59136-5_2"}],"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-62809-7_21","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2017,7,20]],"date-time":"2017-07-20T04:42:55Z","timestamp":1500525775000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-62809-7_21"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017]]},"ISBN":["9783319628080","9783319628097"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-62809-7_21","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2017]]}}}