{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T13:11:18Z","timestamp":1743081078569,"version":"3.40.3"},"publisher-location":"Cham","reference-count":20,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319214993"},{"type":"electronic","value":"9783319215006"}],"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-21500-6_31","type":"book-chapter","created":{"date-parts":[[2015,7,17]],"date-time":"2015-07-17T08:07:44Z","timestamp":1437120464000},"page":"389-400","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["State Complexity of Neighbourhoods and Approximate Pattern Matching"],"prefix":"10.1007","author":[{"given":"Timothy","family":"Ng","sequence":"first","affiliation":[]},{"given":"David","family":"Rappaport","sequence":"additional","affiliation":[]},{"given":"Kai","family":"Salomaa","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2015,7,18]]},"reference":[{"key":"31_CR1","doi-asserted-by":"publisher","first-page":"3209","DOI":"10.1016\/j.tcs.2009.05.019","volume":"410","author":"H Bordihn","year":"2009","unstructured":"Bordihn, H., Holzer, M., Kutrib, M.: Determination of finite automata accepting subregular languages. Theoretical Computer Science 410, 3209\u20133249 (2009)","journal-title":"Theoretical Computer Science"},{"key":"31_CR2","doi-asserted-by":"publisher","first-page":"762","DOI":"10.1145\/359842.359859","volume":"20","author":"RS Boyer","year":"1977","unstructured":"Boyer, R.S., Moore, J.S.: A fast string searching algorithm. Communications of ACM 20, 762\u2013772 (1977)","journal-title":"Communications of ACM"},{"key":"31_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"208","DOI":"10.1007\/978-3-642-12200-2_20","volume-title":"LATIN 2010: Theoretical Informatics","author":"J Brzozowski","year":"2010","unstructured":"Brzozowski, J., Jir\u00e1skov\u00e1, G., Li, B.: Quotient complexity of ideal languages. In: L\u00f3pez-Ortiz, A. (ed.) LATIN 2010. LNCS, vol. 6034, pp. 208\u2013221. Springer, Heidelberg (2010)"},{"issue":"2","key":"31_CR4","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. Journal of Universal Computer Science 8(2), 141\u2013152 (2002)","journal-title":"Journal of Universal Computer Science"},{"key":"31_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-Verlag, Heidelberg (2009)"},{"key":"31_CR6","unstructured":"El-Mabrouk, N.: On the size of minimal automata for approximate string matching. Technical report, Institut Gaspard Monge, Universit\u00e9 de Marne la Vall\u00e9e, Paris (1997)"},{"key":"31_CR7","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. International Journal of Foundations of Computer Science 24, 1067\u20131082 (2013)","journal-title":"International Journal of Foundations of Computer Science"},{"key":"31_CR8","first-page":"293","volume":"9","author":"L Kari","year":"2004","unstructured":"Kari, L., Konstantinidis, S.: Descriptional complexity of error\/edit systems. Journal of Automata, Languages, and Combinatorics 9, 293\u2013309 (2004)","journal-title":"Journal of Automata, Languages, and Combinatorics"},{"key":"31_CR9","unstructured":"Kari, L., Konstantinidis, S., Kopecki, S., Yang, M.: An efficient algorithm for computing the edit distance of a regular language via input-altering transducers. CoRR abs\/1406.1041 (2014)"},{"key":"31_CR10","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. Journal of Universal Computer Science 8, 278\u2013291 (2002)","journal-title":"Journal of Universal Computer Science"},{"key":"31_CR11","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. Information and Computation 205, 1307\u20131316 (2007)","journal-title":"Information and Computation"},{"key":"31_CR12","first-page":"55","volume":"13","author":"S Konstantinidis","year":"2008","unstructured":"Konstantinidis, S., Silva, P.: Maximal error-detecting capabilities of formal languages. J. Automata, Languages and Combinatorics 13, 55\u201371 (2008)","journal-title":"J. Automata, Languages and Combinatorics"},{"key":"31_CR13","doi-asserted-by":"crossref","first-page":"257","DOI":"10.3233\/FI-2010-287","volume":"101","author":"S Konstantinidis","year":"2010","unstructured":"Konstantinidis, S., Silva, P.: Computing maximal error-detecting capabilities and distances of regular languages. Fundamenta Informaticae 101, 257\u2013270 (2010)","journal-title":"Fundamenta Informaticae"},{"issue":"8","key":"31_CR14","first-page":"707","volume":"10","author":"VI Levenshtein","year":"1966","unstructured":"Levenshtein, V.I.: Binary codes capable of correcting deletions, insertions, and reversals. Soviet Physics Doklady 10(8), 707\u2013710 (1966)","journal-title":"Soviet Physics Doklady"},{"key":"31_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1007\/978-3-319-19225-3_18","volume-title":"Descriptional Complexity of Formal Systems","author":"T Ng","year":"2015","unstructured":"Ng, T., Rappaport, D., Salomaa, K.: Quasi-distances and weighted finite automata. In: Shallit, J., Okhotin, A. (eds.) DCFS 2015. LNCS, vol. 9118, pp. 209\u2013219. Springer, Heidelberg (2015)"},{"key":"31_CR16","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? Information and Computation 165, 1\u201313 (2001)","journal-title":"Information and Computation"},{"key":"31_CR17","unstructured":"Povarov, G.: Descriptive complexity of the hamming neighborhood of a regular language. In: Language and Automata Theory and Applications, pp. 509\u2013520 (2007)"},{"issue":"06","key":"31_CR18","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. International Journal of Foundations of Computer Science 18(06), 1407\u20131416 (2007)","journal-title":"International Journal of Foundations of Computer Science"},{"key":"31_CR19","doi-asserted-by":"crossref","unstructured":"Shallit, J.: A Second Course in Formal Languages and Automata Theory. Cambridge University Press (2009)","DOI":"10.1017\/CBO9780511808876"},{"key":"31_CR20","doi-asserted-by":"crossref","unstructured":"Yu, S.: Regular languages. In: Rozenberg, G., Salomaa, A. (Eds.) Handbook of Formal Languages, vol. I, pp. 41\u2013110. Springer (1997)","DOI":"10.1007\/978-3-642-59136-5_2"}],"container-title":["Lecture Notes in Computer Science","Developments in Language Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-21500-6_31","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,20]],"date-time":"2023-01-20T18:35:12Z","timestamp":1674239712000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-21500-6_31"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783319214993","9783319215006"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-21500-6_31","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":"18 July 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}