{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,8]],"date-time":"2024-09-08T20:06:51Z","timestamp":1725826011307},"publisher-location":"Cham","reference-count":18,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319223599"},{"type":"electronic","value":"9783319223605"}],"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-22360-5_20","type":"book-chapter","created":{"date-parts":[[2015,7,27]],"date-time":"2015-07-27T08:24:42Z","timestamp":1437985482000},"page":"238-249","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["State Complexity of Prefix Distance"],"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,28]]},"reference":[{"key":"20_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"34","DOI":"10.1007\/978-3-642-12476-1_2","volume-title":"Algorithms and Applications","author":"A Apostolico","year":"2010","unstructured":"Apostolico, A.: Maximal words in sequence comparisons based on subword composition. In: Elomaa, T., Mannila, H., Orponen, P. (eds.) Ukkonen Festschrift 2010. LNCS, vol. 6060, pp. 34\u201344. Springer, Heidelberg (2010)"},{"key":"20_CR2","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1016\/0020-0190(92)90198-5","volume":"43","author":"JC Birget","year":"1992","unstructured":"Birget, J.C.: Intersection and union of regular languages and state complexity. Inf. Process. Lett. 43, 185\u2013190 (1992)","journal-title":"Inf. Process. Lett."},{"issue":"2","key":"20_CR3","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."},{"issue":"1","key":"20_CR4","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. Theor. Comput. Sci. 286(1), 117\u2013138 (2002)","journal-title":"Theor. Comput. Sci."},{"key":"20_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, Berlin Heidelberg (2009)"},{"key":"20_CR6","unstructured":"Gao, Y., Moreira, N., Reis, R., Yu, S.: A review on state complexity of individual operations. Faculdade de Ciencias, Universidade do Porto, Technical report DCC-2011-8 www.dcc.fc.up.pt\/dcc\/Pubs\/TReports\/TR11\/dcc-2011-08.pdf to appear in Computer Science Review"},{"key":"20_CR7","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 \u2013 a survey. Inf. Comput. 209, 456\u2013470 (2011)","journal-title":"Inf. Comput."},{"key":"20_CR8","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":"20_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":"20_CR10","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."},{"key":"20_CR11","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, Heidelberg (2014)"},{"key":"20_CR12","first-page":"70","volume":"111","author":"M Kutrib","year":"2013","unstructured":"Kutrib, M., Pighizzini, G.: Recent trends in descriptional complexity of formal languages. Bull. EATCS 111, 70\u201386 (2013)","journal-title":"Bull. EATCS"},{"key":"20_CR13","volume-title":"Applied Combinatorics on Words, Ch. 1 Algorithms on Words. Encyclopedia of Mathematics and It\u2019s Applications 105","author":"M Lothaire","year":"2005","unstructured":"Lothaire, M.: Applied Combinatorics on Words, Ch. 1 Algorithms on Words. Encyclopedia of Mathematics and It\u2019s Applications 105. Cambridge University Press, New York (2005)"},{"key":"20_CR14","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":"20_CR15","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":"20_CR16","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(06), 1407\u20131416 (2007)","journal-title":"Int. J. Found. Comput. Sci."},{"key":"20_CR17","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":"20_CR18","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-Verlag, Berlin (1997)"}],"container-title":["Lecture Notes in Computer Science","Implementation and Application of Automata"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-22360-5_20","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,20]],"date-time":"2023-01-20T20:25:54Z","timestamp":1674246354000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-22360-5_20"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783319223599","9783319223605"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-22360-5_20","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":"28 July 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}