{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,25]],"date-time":"2025-03-25T14:13:57Z","timestamp":1742912037005,"version":"3.40.3"},"publisher-location":"Cham","reference-count":20,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319192246"},{"type":"electronic","value":"9783319192253"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-319-19225-3_18","type":"book-chapter","created":{"date-parts":[[2015,6,15]],"date-time":"2015-06-15T15:51:06Z","timestamp":1434383466000},"page":"209-219","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Quasi-Distances and Weighted Finite Automata"],"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":[[2015,6,16]]},"reference":[{"key":"18_CR1","doi-asserted-by":"publisher","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, 1302\u20131321 (2013)","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"18_CR2","first-page":"141","volume":"8","author":"CS Calude","year":"2002","unstructured":"Calude, C.S., Salomaa, K., Yu, S.: Distances and quasi-distances between words. J. Univ. Comput. Sci. 8(2), 141\u2013152 (2002)","journal-title":"J. Univ. Comput. Sci."},{"key":"18_CR3","doi-asserted-by":"publisher","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. Theoret. Comput. Sci. 286, 117\u2013138 (2002)","journal-title":"Theoret. Comput. Sci."},{"key":"18_CR4","volume-title":"Introduction to Algorithms","author":"TH Cormen","year":"2001","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 2nd edn. MIT Press, Cambridge (2001)","edition":"2"},{"key":"18_CR5","doi-asserted-by":"publisher","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":"18_CR6","series-title":"EATCS Monographs in Theoretical Computer Science","volume-title":"Handbook of Weighted Automata","year":"2009","unstructured":"Droste, M., Kuich, W., Vogler, H. (eds.): Handbook of Weighted Automata. EATCS Monographs in Theoretical Computer Science. Springer, Heidelberg (2009)"},{"key":"18_CR7","first-page":"257","volume":"9","author":"M Eramian","year":"2004","unstructured":"Eramian, M.: Efficient simulation of nondeterministic weighted finite automata. J. Automata Lang. Comb. 9, 257\u2013267 (2004)","journal-title":"J. Automata Lang. Comb."},{"key":"18_CR8","doi-asserted-by":"publisher","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, 1067\u20131082 (2013)","journal-title":"Int. J. Found. Comput. Sci."},{"key":"18_CR9","doi-asserted-by":"publisher","first-page":"456","DOI":"10.1016\/j.ic.2010.11.013","volume":"209","author":"M Holzer","year":"2011","unstructured":"Holzer, M., Kutrib, M.: Descriptional and computational complexity of finite automata \u2014 a survey. Inf. Comput. 209, 456\u2013470 (2011)","journal-title":"Inf. Comput."},{"key":"18_CR10","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":"18_CR11","first-page":"278","volume":"8","author":"S Konstantinidis","year":"2002","unstructured":"Konstantinidis, S.: Transducers and the properties of error detection, error-correction, and finite-delay decodability. J. Univ. Comput. Sci. 8, 278\u2013291 (2002)","journal-title":"J. Univ. Comput. Sci."},{"key":"18_CR12","doi-asserted-by":"publisher","first-page":"1307","DOI":"10.1016\/j.ic.2007.06.001","volume":"205","author":"S Konstantinidis","year":"2007","unstructured":"Konstantinidis, S.: Computing the edit distance of a regular language. Inf. Comput. 205, 1307\u20131316 (2007)","journal-title":"Inf. Comput."},{"issue":"8","key":"18_CR13","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":"18_CR14","doi-asserted-by":"crossref","unstructured":"Ng, T., Rappaport, D., Salomaa, K.: State complexity of neighbourhoods and approximate pattern matching (March 2015, Submitted for publication)","DOI":"10.1007\/978-3-319-21500-6_31"},{"key":"18_CR15","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":"18_CR16","unstructured":"Povarov, G.: Descriptive complexity of the Hamming neighborhood of a regular language. In: Proceedings of the 1st International Conference Language and Automata Theory and Applications, LATA 2007, pp. 509\u2013520 (2007)"},{"issue":"6","key":"18_CR17","doi-asserted-by":"publisher","first-page":"1407","DOI":"10.1142\/S0129054107005443","volume":"18","author":"K Salomaa","year":"2007","unstructured":"Salomaa, K., Schofield, P.: State complexity of additive weighted finite automata. Int. J. Found. Comput. Sci. 18(6), 1407\u20131416 (2007)","journal-title":"Int. J. Found. Comput. Sci."},{"key":"18_CR18","unstructured":"Schofield, P.: Error Quantification and Recognition Using Weighted Finite Automata. MSc thesis, Queen\u2019s University, Kingston, Canada (2006)"},{"key":"18_CR19","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)"},{"key":"18_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, vol. 1, pp. 41\u2013110. Springer, Heidelberg (1997)"}],"container-title":["Lecture Notes in Computer Science","Descriptional Complexity of Formal Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-19225-3_18","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,20]],"date-time":"2023-01-20T09:08:34Z","timestamp":1674205714000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-19225-3_18"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783319192246","9783319192253"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-19225-3_18","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"16 June 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}