{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,28]],"date-time":"2025-03-28T01:39:20Z","timestamp":1743125960767,"version":"3.40.3"},"publisher-location":"Cham","reference-count":19,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319986531"},{"type":"electronic","value":"9783319986548"}],"license":[{"start":{"date-parts":[[2018,1,1]],"date-time":"2018-01-01T00:00:00Z","timestamp":1514764800000},"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":[[2018]]},"DOI":"10.1007\/978-3-319-98654-8_32","type":"book-chapter","created":{"date-parts":[[2018,8,4]],"date-time":"2018-08-04T19:43:57Z","timestamp":1533411837000},"page":"392-403","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Closest Substring Problems for 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":[[2018,8,5]]},"reference":[{"key":"32_CR1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-79235-9","volume-title":"Structural Complexity I","author":"JL Balc\u00e1zar","year":"1995","unstructured":"Balc\u00e1zar, J.L., Diaz, J., Gabarr\u00f3, J.: Structural Complexity I, 2nd edn. Springer, Heidelberg (1995). \n                    https:\/\/doi.org\/10.1007\/978-3-642-79235-9","edition":"2"},{"key":"32_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1007\/978-3-642-40313-2_17","volume-title":"Mathematical Foundations of Computer Science 2013","author":"H Bj\u00f6rklund","year":"2013","unstructured":"Bj\u00f6rklund, H., Martens, W., Schwentick, T.: Validity of tree pattern queries with respect to schema information. In: Chatterjee, K., Sgall, J. (eds.) MFCS 2013. LNCS, vol. 8087, pp. 171\u2013182. Springer, Heidelberg (2013). \n                    https:\/\/doi.org\/10.1007\/978-3-642-40313-2_17"},{"key":"32_CR3","unstructured":"Boas, P.V.E.: The convenience of tilings. In: Complexity, Logic, and Recursion Theory, pp. 331\u2013363. Marcel Dekker Inc. (1997)"},{"key":"32_CR4","unstructured":"Bulteau, L., H\u00fcffner, F., Komusiewicz, C., Niedermeier, R.: Multivariate algorithmics for NP-hard string problems. Bull. EATCS, 114 (2014)"},{"issue":"2","key":"32_CR5","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":"32_CR6","doi-asserted-by":"publisher","first-page":"114","DOI":"10.1145\/322234.322243","volume":"28","author":"AK Chandra","year":"1981","unstructured":"Chandra, A.K., Kozen, D.C., Stockmeyer, L.J.: Alternation. J. ACM 28(1), 114\u2013133 (1981)","journal-title":"J. ACM"},{"key":"32_CR7","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). \n                    https:\/\/doi.org\/10.1007\/978-3-642-00234-2"},{"issue":"2","key":"32_CR8","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1007\/s00493-006-0011-4","volume":"26","author":"MR Fellows","year":"2006","unstructured":"Fellows, M.R., Gramm, J., Niedermeier, R.: On the parameterized intractability of motif search problems. Combinatorica 26(2), 141\u2013167 (2006)","journal-title":"Combinatorica"},{"issue":"2","key":"32_CR9","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. Theory Comput. Syst. 30(2), 113\u2013119 (1997)","journal-title":"Theory Comput. Syst."},{"issue":"3","key":"32_CR10","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. Theory 31(3), 385\u2013401 (2006)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"32_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"196","DOI":"10.1007\/978-3-319-53733-7_14","volume-title":"Language and Automata Theory and Applications","author":"Y-S Han","year":"2017","unstructured":"Han, Y.-S., Ko, S.-K., Ng, T., Salomaa, K.: Consensus string problem for multiple regular languages. In: Drewes, F., Mart\u00edn-Vide, C., Truthe, B. (eds.) LATA 2017. LNCS, vol. 10168, pp. 196\u2013207. Springer, Cham (2017). \n                    https:\/\/doi.org\/10.1007\/978-3-319-53733-7_14"},{"key":"32_CR12","first-page":"293","volume":"9","author":"L Kari","year":"2004","unstructured":"Kari, L., Konstantinidis, S.: Descriptional complexity of error\/edit systems. J. Autom. Lang. Comb. 9, 293\u2013309 (2004)","journal-title":"J. Autom. Lang. Comb."},{"issue":"4","key":"32_CR13","doi-asserted-by":"publisher","first-page":"1382","DOI":"10.1137\/060673898","volume":"38","author":"D Marx","year":"2008","unstructured":"Marx, D.: Closest substring problems with small distances. SIAM J. Comput. 38(4), 1382\u20131410 (2008)","journal-title":"SIAM J. Comput."},{"key":"32_CR14","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, Cham (2015). \n                    https:\/\/doi.org\/10.1007\/978-3-319-21500-6_31"},{"key":"32_CR15","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)"},{"issue":"3","key":"32_CR16","doi-asserted-by":"publisher","first-page":"13:1","DOI":"10.1145\/3110290","volume":"9","author":"ML Schmid","year":"2017","unstructured":"Schmid, M.L.: Finding consensus strings with small length difference between input and solution strings. ACM Trans. Comput. Theory 9(3), 13:1\u201313:18 (2017)","journal-title":"ACM Trans. Comput. Theory"},{"key":"32_CR17","volume-title":"Introduction to the Theory of Computation","author":"M Sipser","year":"1996","unstructured":"Sipser, M.: Introduction to the Theory of Computation, 1st edn. International Thomson Publishing, Stamford (1996)","edition":"1"},{"issue":"1","key":"32_CR18","doi-asserted-by":"publisher","first-page":"100","DOI":"10.1016\/S0019-9958(85)80046-2","volume":"64","author":"E Ukkonen","year":"1985","unstructured":"Ukkonen, E.: Algorithms for approximate string matching. Inf. Control 64(1), 100\u2013118 (1985)","journal-title":"Inf. Control"},{"key":"32_CR19","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 Heidelberg (1997). \n                    https:\/\/doi.org\/10.1007\/978-3-642-59136-5_2"}],"container-title":["Lecture Notes in Computer Science","Developments in Language Theory"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-98654-8_32","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2018,9,2]],"date-time":"2018-09-02T19:17:50Z","timestamp":1535915870000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-98654-8_32"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018]]},"ISBN":["9783319986531","9783319986548"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-98654-8_32","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2018]]}}}