{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,25]],"date-time":"2025-03-25T20:08:16Z","timestamp":1742933296484,"version":"3.40.3"},"publisher-location":"Cham","reference-count":16,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319411132"},{"type":"electronic","value":"9783319411149"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-3-319-41114-9_15","type":"book-chapter","created":{"date-parts":[[2016,6,27]],"date-time":"2016-06-27T10:05:14Z","timestamp":1467021914000},"page":"192-204","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["State Complexity of Prefix Distance of Subregular Languages"],"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":[[2016,6,28]]},"reference":[{"issue":"35","key":"15_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. Theor. Comput. Sci. 410(35), 3209\u20133222 (2009)","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"15_CR2","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":"15_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"60","DOI":"10.1007\/3-540-45526-4_6","volume-title":"Automata Implementation","author":"C C\u00e2mpeanu","year":"2001","unstructured":"C\u00e2mpeanu, C., Culik II, K., Salomaa, K., Yu, S.: State complexity of basic operations on finite languages. In: Boldt, O., J\u00fcrgensen, H. (eds.) WIA 1999. LNCS, vol. 2214, p. 60. Springer, Heidelberg (2001)"},{"issue":"1","key":"15_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":"15_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":"15_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. To appear in Computer Science Review. \n                    www.dcc.fc.up.pt\/dcc\/Pubs\/TReports\/TR11\/dcc-2011-08.pdf"},{"key":"15_CR7","unstructured":"Han, Y.S., Salomaa, K., Wood, D.: State complexity of prefix-free regular languages. In: Proceedings of the 8th International Workshop on Descriptive Complexity of Formal Systems. pp. 165\u2013176 (2006)"},{"issue":"1","key":"15_CR8","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1142\/S0129054112400084","volume":"23","author":"M Holzer","year":"2012","unstructured":"Holzer, M., Jakobi, S., Kutrib, M.: The magic number problem for subregular language families. Int. J. Found. Comput. Sci. 23(1), 115\u2013131 (2012)","journal-title":"Int. J. Found. Comput. Sci."},{"key":"15_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 \u2013 a survey. Inform. Comput. 209, 456\u2013470 (2011)","journal-title":"Inform. Comput."},{"key":"15_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"178","DOI":"10.1007\/978-3-642-22256-6_17","volume-title":"Implementation and Application of Automata","author":"M Holzer","year":"2011","unstructured":"Holzer, M., Kutrib, M., Meckel, K.: Nondeterministic state complexity of star-free languages. In: Bouchou-Markhoff, B., Caron, P., Champarnaud, J.-M., Maurel, D. (eds.) CIAA 2011. LNCS, vol. 6807, pp. 178\u2013189. Springer, Heidelberg (2011)"},{"key":"15_CR11","first-page":"109","volume":"2015","author":"M Holzer","year":"2015","unstructured":"Holzer, M., Truthe, B.: On relations between some subregular language families. Proc. NCMA 2015, 109\u2013124 (2015)","journal-title":"Proc. NCMA"},{"issue":"47\u201349","key":"15_CR12","doi-asserted-by":"publisher","first-page":"5010","DOI":"10.1016\/j.tcs.2009.07.049","volume":"410","author":"JY Kao","year":"2009","unstructured":"Kao, J.Y., Rampersad, N., Shallit, J.: On NFAs where all states are final, initial, or both. Theor. Comput. Sci. 410(47\u201349), 5010\u20135021 (2009)","journal-title":"Theor. Comput. Sci."},{"key":"15_CR13","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":"15_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"238","DOI":"10.1007\/978-3-319-22360-5_20","volume-title":"Implementation and Application of Automata","author":"T Ng","year":"2015","unstructured":"Ng, T., Rappaport, D., Salomaa, K.: State complexity of prefix distance. In: Drewes, F. (ed.) CIAA 2015. LNCS, vol. 9223, pp. 238\u2013249. Springer, Heidelberg (2015)"},{"key":"15_CR15","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":"15_CR16","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)"}],"container-title":["Lecture Notes in Computer Science","Descriptional Complexity of Formal Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-41114-9_15","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,7,13]],"date-time":"2020-07-13T00:03:23Z","timestamp":1594598603000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-41114-9_15"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783319411132","9783319411149"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-41114-9_15","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2016]]},"assertion":[{"value":"28 June 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}