{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:32:49Z","timestamp":1759638769852,"version":"3.40.3"},"publisher-location":"Cham","reference-count":27,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319537320"},{"type":"electronic","value":"9783319537337"}],"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":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2017]]},"DOI":"10.1007\/978-3-319-53733-7_14","type":"book-chapter","created":{"date-parts":[[2017,2,15]],"date-time":"2017-02-15T05:39:21Z","timestamp":1487137161000},"page":"196-207","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Consensus String Problem for Multiple Regular Languages"],"prefix":"10.1007","author":[{"given":"Yo-Sub","family":"Han","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sang-Ki","family":"Ko","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Timothy","family":"Ng","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,2,16]]},"reference":[{"issue":"39","key":"14_CR1","doi-asserted-by":"publisher","first-page":"5239","DOI":"10.1016\/j.tcs.2011.05.034","volume":"412","author":"A Amir","year":"2011","unstructured":"Amir, A., Landau, G.M., Na, J.C., Park, H., Park, K., Sim, J.S.: Efficient algorithms for consensus string problems minimizing both distance sum and radius. Theoret. Comput. Sci. 412(39), 5239\u20135246 (2011)","journal-title":"Theoret. Comput. Sci."},{"issue":"10\u201311","key":"14_CR2","doi-asserted-by":"publisher","first-page":"371","DOI":"10.1016\/j.ipl.2013.02.016","volume":"113","author":"A Amir","year":"2013","unstructured":"Amir, A., Paryenty, H., Roditty, L.: On the hardness of the consensus string problem. Inf. Process. Lett. 113(10\u201311), 371\u2013374 (2013)","journal-title":"Inf. Process. Lett."},{"issue":"2","key":"14_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":"14_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. Theoret. Comput. Sci. 286(1), 117\u2013138 (2002)","journal-title":"Theoret. Comput. Sci."},{"issue":"5","key":"14_CR5","doi-asserted-by":"publisher","first-page":"1617","DOI":"10.1109\/18.623161","volume":"43","author":"GD Cohen","year":"2006","unstructured":"Cohen, G.D., Honkala, I.S., Litsyn, S.N., Sol\u00e9, P.: Long packing and covering codes. IEEE Trans. Inf. Theor. 43(5), 1617\u20131619 (2006)","journal-title":"IEEE Trans. Inf. Theor."},{"key":"14_CR6","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)"},{"issue":"2","key":"14_CR7","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1007\/BF02679443","volume":"30","author":"M Frances","year":"1997","unstructured":"Frances, M., Litman, A.: On covering problems of codes. Theor. Comput. Syst. 30(2), 113\u2013119 (1997)","journal-title":"Theor. Comput. Syst."},{"issue":"3","key":"14_CR8","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1109\/TIT.1985.1057039","volume":"31","author":"RL Graham","year":"2006","unstructured":"Graham, R.L., Sloane, N.J.A.: On the covering radius of codes. IEEE Trans. Inf. Theor. 31(3), 385\u2013401 (2006)","journal-title":"IEEE Trans. Inf. Theor."},{"key":"14_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"441","DOI":"10.1007\/3-540-45678-3_38","volume-title":"Algorithms and Computation","author":"J Gramm","year":"2001","unstructured":"Gramm, J., Niedermeier, R., Rossmanith, P.: Exact solutions for closest string and related problems. In: Eades, P., Takaoka, T. (eds.) ISAAC 2001. LNCS, vol. 2223, pp. 441\u2013453. Springer, Heidelberg (2001). doi:\n                      10.1007\/3-540-45678-3_38"},{"key":"14_CR10","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1007\/s00453-003-1028-3","volume":"37","author":"J Gramm","year":"2003","unstructured":"Gramm, J., Niedermeier, R., Rossmanith, P.: Fixed-parameter algorithms for closest string and related problems. Algorithmica 37, 25\u201342 (2003)","journal-title":"Algorithmica"},{"issue":"7","key":"14_CR11","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(7), 1067\u20131082 (2013)","journal-title":"Int. J. Found. Comput. Sci."},{"issue":"3","key":"14_CR12","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\u2014a survey. Inf. Comput. 209(3), 456\u2013470 (2011)","journal-title":"Inf. Comput."},{"issue":"9","key":"14_CR13","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(9), 1307\u20131316 (2007)","journal-title":"Inf. Comput."},{"key":"14_CR14","doi-asserted-by":"crossref","unstructured":"Kozen, D.: Lower bounds for natural proof systems. In: Proceedings of the 18th Annual Symposium on Foundations of Computer Science, pp. 254\u2013266 (1977)","DOI":"10.1109\/SFCS.1977.16"},{"issue":"8","key":"14_CR15","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."},{"issue":"4","key":"14_CR16","doi-asserted-by":"publisher","first-page":"1432","DOI":"10.1137\/080739069","volume":"39","author":"B Ma","year":"2010","unstructured":"Ma, B., Sun, X.: More efficient algorithms for closest string and substring problems. SIAM J. Comput. 39(4), 1432\u20131443 (2010)","journal-title":"SIAM J. Comput."},{"issue":"1\u20133","key":"14_CR17","doi-asserted-by":"publisher","first-page":"331","DOI":"10.1016\/j.tcs.2005.02.002","volume":"337","author":"B Manthey","year":"2005","unstructured":"Manthey, B., Reischuk, R.: The intractability of computing the Hamming distance. Theoret. Comput. Sci. 337(1\u20133), 331\u2013346 (2005)","journal-title":"Theoret. Comput. Sci."},{"key":"14_CR18","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1016\/0020-0190(95)00007-Y","volume":"54","author":"G Myers","year":"1995","unstructured":"Myers, G.: Approximately matching context-free languages. Inf. Process. Lett. 54, 85\u201392 (1995)","journal-title":"Inf. Process. Lett."},{"key":"14_CR19","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). doi:\n                      10.1007\/978-3-319-19225-3_18"},{"key":"14_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"389","DOI":"10.1007\/978-3-319-21500-6_31","volume-title":"Developments in Language Theory","author":"T Ng","year":"2015","unstructured":"Ng, T., Rappaport, D., Salomaa, K.: State complexity of neighbourhoods and approximate pattern matching. In: Potapov, I. (ed.) DLT 2015. LNCS, vol. 9168, pp. 389\u2013400. Springer, Heidelberg (2015). doi:\n                      10.1007\/978-3-319-21500-6_31"},{"issue":"1","key":"14_CR21","doi-asserted-by":"publisher","first-page":"164","DOI":"10.1016\/j.jcss.2011.02.008","volume":"78","author":"L Palopoli","year":"2012","unstructured":"Palopoli, L., Chen, Z.-Z., Ma, B., Wang, L.: A three-string approach to the closest string problem. J. Comput. Syst. Sci. 78(1), 164\u2013178 (2012)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"14_CR22","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), 1\u201313 (2001)","journal-title":"Inf. Comput."},{"key":"14_CR23","unstructured":"Povarov, G.: Descriptive complexity of the hamming neighborhood of a regular language. In: Proceedings of the 1st International Conference on Language and Automata Theory and Applications, pp. 509\u2013520 (2007)"},{"key":"14_CR24","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511808876","volume-title":"A Second Course in Formal Languages and Automata Theory","author":"J Shallit","year":"2008","unstructured":"Shallit, J.: A Second Course in Formal Languages and Automata Theory, 1st edn. Cambridge University Press, New York (2008)","edition":"1"},{"issue":"1","key":"14_CR25","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1016\/S1570-8667(03)00011-X","volume":"1","author":"JS Sim","year":"2003","unstructured":"Sim, J.S., Park, K.: The consensus string problem for a metric is NP-complete. J. Discret. Algorithms 1(1), 111\u2013117 (2003)","journal-title":"J. Discret. Algorithms"},{"key":"14_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"126","DOI":"10.1007\/3-540-63307-3_53","volume-title":"Algorithms and Data Structures","author":"N Stojanovic","year":"1997","unstructured":"Stojanovic, N., Berman, P., Gumucio, D., Hardison, R., Miller, W.: A linear-time algorithm for the 1-mismatch problem. In: Dehne, F., Rau-Chaplin, A., Sack, J.-R., Tamassia, R. (eds.) WADS 1997. LNCS, vol. 1272, pp. 126\u2013135. Springer, Heidelberg (1997). doi:\n                      10.1007\/3-540-63307-3_53"},{"key":"14_CR27","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, Berlin (1997)"}],"container-title":["Lecture Notes in Computer Science","Language and Automata Theory and Applications"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-53733-7_14","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,20]],"date-time":"2019-05-20T01:45:24Z","timestamp":1558316724000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-53733-7_14"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017]]},"ISBN":["9783319537320","9783319537337"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-53733-7_14","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2017]]},"assertion":[{"value":"16 February 2017","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"LATA","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Language and Automata Theory and Applications","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Ume\u00e5","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Sweden","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2017","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"6 March 2017","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"9 March 2017","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"11","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"lata2017","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/grammars.grlmc.com\/LATA2017\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}