{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,25]],"date-time":"2025-03-25T20:11:57Z","timestamp":1742933517780,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":33,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540880080"},{"type":"electronic","value":"9783540880097"}],"license":[{"start":{"date-parts":[[2008,1,1]],"date-time":"2008-01-01T00:00:00Z","timestamp":1199145600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2008,1,1]],"date-time":"2008-01-01T00:00:00Z","timestamp":1199145600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2008]]},"DOI":"10.1007\/978-3-540-88009-7_4","type":"book-chapter","created":{"date-parts":[[2008,9,20]],"date-time":"2008-09-20T03:52:54Z","timestamp":1221882774000},"page":"43-56","source":"Crossref","is-referenced-by-count":5,"title":["Learning Languages from Bounded Resources: The Case of the DFA and the Balls of Strings"],"prefix":"10.1007","author":[{"given":"Colin","family":"de la Higuera","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jean-Christophe","family":"Janodet","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Fr\u00e9d\u00e9ric","family":"Tantini","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"4","key":"4_CR1","first-page":"845","volume":"163","author":"V.I. Levenshtein","year":"1965","unstructured":"Levenshtein, V.I.: Binary codes capable of correcting deletions, insertions, and reversals. Doklady Akademii Nauk SSSR\u00a0163(4), 845\u2013848 (1965)","journal-title":"Doklady Akademii Nauk SSSR"},{"issue":"1","key":"4_CR2","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1145\/375360.375365","volume":"33","author":"G. Navarro","year":"2001","unstructured":"Navarro, G.: A guided tour to approximate string matching. ACM computing surveys\u00a033(1), 31\u201388 (2001)","journal-title":"ACM computing surveys"},{"issue":"3","key":"4_CR3","doi-asserted-by":"publisher","first-page":"273","DOI":"10.1145\/502807.502808","volume":"33","author":"E. Ch\u00e1vez","year":"2001","unstructured":"Ch\u00e1vez, E., Navarro, G., Baeza-Yates, R.A., Marroqu\u00edn, J.L.: Searching in metric spaces. ACM Computing Survey\u00a033(3), 273\u2013321 (2001)","journal-title":"ACM Computing Survey"},{"key":"4_CR4","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1016\/0167-8655(85)90061-3","volume":"3","author":"T. Kohonen","year":"1985","unstructured":"Kohonen, T.: Median strings. Pattern Recognition Letters\u00a03, 309\u2013313 (1985)","journal-title":"Pattern Recognition Letters"},{"issue":"1","key":"4_CR5","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1007\/s10032-002-0082-8","volume":"5","author":"K.U. Schulz","year":"2002","unstructured":"Schulz, K.U., Mihov, S.: Fast string correction with Levenshtein automata. Int. Journal on Document Analysis and Recognition\u00a05(1), 67\u201385 (2002)","journal-title":"Int. Journal on Document Analysis and Recognition"},{"key":"4_CR6","doi-asserted-by":"publisher","first-page":"245","DOI":"10.1007\/0-387-22444-0_8","volume-title":"Recent Advances in Algorithms and Combinatorics","author":"M.F. Sagot","year":"2003","unstructured":"Sagot, M.F., Wakabayashi, Y.: Pattern inference under many guises. In: Recent Advances in Algorithms and Combinatorics, pp. 245\u2013287. Springer, Heidelberg (2003)"},{"issue":"5","key":"4_CR7","doi-asserted-by":"publisher","first-page":"447","DOI":"10.1016\/S0019-9958(67)91165-5","volume":"10","author":"E.M. Gold","year":"1967","unstructured":"Gold, E.M.: Language identification in the limit. Information and Control\u00a010(5), 447\u2013474 (1967)","journal-title":"Information and Control"},{"key":"4_CR8","first-page":"319","volume":"2","author":"D. Angluin","year":"1987","unstructured":"Angluin, D.: Queries and concept learning. Machine Learning Journal\u00a02, 319\u2013342 (1987)","journal-title":"Machine Learning Journal"},{"issue":"11","key":"4_CR9","doi-asserted-by":"publisher","first-page":"1134","DOI":"10.1145\/1968.1972","volume":"27","author":"L.G. Valiant","year":"1984","unstructured":"Valiant, L.G.: A theory of the learnable. Communications of the ACM\u00a027(11), 1134\u20131142 (1984)","journal-title":"Communications of the ACM"},{"key":"4_CR10","first-page":"121","volume":"5","author":"D. Angluin","year":"1990","unstructured":"Angluin, D.: Negative results for equivalence queries. Machine Learning Journal\u00a05, 121\u2013150 (1990)","journal-title":"Machine Learning Journal"},{"key":"4_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"18","DOI":"10.1007\/3-540-51734-0_50","volume-title":"Analogical and Inductive Inference","author":"L. Pitt","year":"1989","unstructured":"Pitt, L.: Inductive inference, DFA\u2019s, and computational complexity. In: Jantke, K.P. (ed.) AII 1989. LNCS, vol.\u00a0397, pp. 18\u201344. Springer, Heidelberg (1989)"},{"key":"4_CR12","doi-asserted-by":"publisher","first-page":"911","DOI":"10.1137\/0220056","volume":"20","author":"M. Li","year":"1991","unstructured":"Li, M., Vitanyi, P.: Learning simple concepts under simple distributions. Siam Journal of Computing\u00a020, 911\u2013935 (1991)","journal-title":"Siam Journal of Computing"},{"issue":"1","key":"4_CR13","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1023\/A:1010826628977","volume":"44","author":"F. Denis","year":"2001","unstructured":"Denis, F.: Learning regular languages from simple positive examples. Machine Learning Journal\u00a044(1), 37\u201366 (2001)","journal-title":"Machine Learning Journal"},{"key":"4_CR14","series-title":"Lecture Notes in Artificial Intelligence","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1007\/978-3-540-45257-7_17","volume-title":"Grammatical Inference: Algorithms and Applications","author":"R.J. Parekh","year":"2000","unstructured":"Parekh, R.J., Honavar, V.: On the relationship between models for learning in helpful environments. In: Oliveira, A.L. (ed.) ICGI 2000. LNCS (LNAI), vol.\u00a01891, pp. 207\u2013220. Springer, Heidelberg (2000)"},{"issue":"2","key":"4_CR15","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1016\/0890-5401(91)90042-Z","volume":"95","author":"D. Haussler","year":"1991","unstructured":"Haussler, D., Kearns, M.J., Littlestone, N., Warmuth, M.K.: Equivalence of models for polynomial learnability. Information and Computation\u00a095(2), 129\u2013161 (1991)","journal-title":"Information and Computation"},{"key":"4_CR16","doi-asserted-by":"crossref","unstructured":"Kearns, M., Valiant, L.: Cryptographic limitations on learning boolean formulae and finite automata. In: 21st ACM Symposium on Theory of Computing (STOC 1989), pp. 433\u2013444 (1989)","DOI":"10.1145\/73007.73049"},{"key":"4_CR17","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1023\/A:1007353007695","volume":"27","author":"C. de la Higuera","year":"1997","unstructured":"de la Higuera, C.: Characteristic sets for polynomial grammatical inference. Machine Learning Journal\u00a027, 125\u2013138 (1997)","journal-title":"Machine Learning Journal"},{"key":"4_CR18","doi-asserted-by":"publisher","first-page":"168","DOI":"10.1145\/321796.321811","volume":"21","author":"R. Wagner","year":"1974","unstructured":"Wagner, R., Fisher, M.: The string-to-string correction problem. Journal of the ACM\u00a021, 168\u2013178 (1974)","journal-title":"Journal of the ACM"},{"key":"4_CR19","volume-title":"Computational Complexity","author":"C.M. Papadimitriou","year":"1994","unstructured":"Papadimitriou, C.M.: Computational Complexity. Addison Wesley, New York (1994)"},{"key":"4_CR20","series-title":"Lecture Notes in Artificial Intelligence","doi-asserted-by":"publisher","first-page":"18","DOI":"10.1007\/978-3-540-74958-5_6","volume-title":"Machine Learning: ECML 2007","author":"L. Becerra-Bonache","year":"2007","unstructured":"Becerra-Bonache, L., de la Higuera, C., Janodet, J.C., Tantini, F.: Learning balls of strings with correction queries. In: Kok, J.N., Koronacki, J., Lopez de Mantaras, R., Matwin, S., Mladeni\u010d, D., Skowron, A. (eds.) ECML 2007. LNCS (LNAI), vol.\u00a04701, pp. 18\u201329. Springer, Heidelberg (2007)"},{"key":"4_CR21","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1016\/S0019-9958(78)90683-6","volume":"39","author":"D. Angluin","year":"1987","unstructured":"Angluin, D.: Learning regular sets from queries and counterexamples. Information and Control\u00a039, 337\u2013350 (1987)","journal-title":"Information and Control"},{"key":"4_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"78","DOI":"10.1007\/3-540-51734-0_53","volume-title":"Analogical and Inductive Inference","author":"M. Warmuth","year":"1989","unstructured":"Warmuth, M.: Towards representation independence in PAC-learning. In: Jantke, K.P. (ed.) AII 1989. LNCS, vol.\u00a0397, pp. 78\u2013103. Springer, Heidelberg (1989)"},{"key":"4_CR23","doi-asserted-by":"crossref","DOI":"10.7551\/mitpress\/3897.001.0001","volume-title":"An Introduction to Computational Learning Theory","author":"M. Kearns","year":"1994","unstructured":"Kearns, M., Vazirani, U.: An Introduction to Computational Learning Theory. MIT Press, Cambridge (1994)"},{"issue":"4","key":"4_CR24","doi-asserted-by":"publisher","first-page":"965","DOI":"10.1145\/48014.63140","volume":"35","author":"L. Pitt","year":"1988","unstructured":"Pitt, L., Valiant, L.G.: Computational limitations on learning from examples. Journal of the ACM\u00a035(4), 965\u2013984 (1988)","journal-title":"Journal of the ACM"},{"key":"4_CR25","doi-asserted-by":"publisher","first-page":"322","DOI":"10.1145\/322063.322075","volume":"25","author":"D. Maier","year":"1977","unstructured":"Maier, D.: The complexity of some problems on subsequences and supersequences. Journal of the ACM\u00a025, 322\u2013336 (1977)","journal-title":"Journal of the ACM"},{"key":"4_CR26","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1016\/S0304-3975(97)00240-5","volume":"230","author":"C. de la Higuera","year":"2000","unstructured":"de la Higuera, C., Casacuberta, F.: Topology of strings: Median string is NP-complete. Theoretical Computer Science\u00a0230, 39\u201348 (2000)","journal-title":"Theoretical Computer Science"},{"issue":"1","key":"4_CR27","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1145\/138027.138042","volume":"40","author":"L. Pitt","year":"1993","unstructured":"Pitt, L., Warmuth, M.: The minimum consistent DFA problem cannot be approximated within any polynomial. Journal of the ACM\u00a040(1), 95\u2013142 (1993)","journal-title":"Journal of the ACM"},{"issue":"3","key":"4_CR28","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1145\/356914.356918","volume":"15","author":"D. Angluin","year":"1983","unstructured":"Angluin, D., Smith, C.: Inductive inference: theory and methods. ACM computing surveys\u00a015(3), 237\u2013269 (1983)","journal-title":"ACM computing surveys"},{"key":"4_CR29","unstructured":"Greenberg, R.I.: Bounds on the number of longest common subsequences. Technical report, Loyola University (2003), \n                      http:\/\/arXiv.org\/abs\/cs\/0301030v2"},{"key":"4_CR30","unstructured":"Greenberg, R.I.: Fast and simple computation of all longest common subsequences. Technical report, Loyola University (2002), \n                      http:\/\/arXiv.org\/abs\/cs.DS\/0211001"},{"key":"4_CR31","doi-asserted-by":"publisher","first-page":"302","DOI":"10.1016\/S0019-9958(78)90562-4","volume":"37","author":"E.M. Gold","year":"1978","unstructured":"Gold, E.M.: Complexity of automaton identification from given data. Information and Control\u00a037, 302\u2013320 (1978)","journal-title":"Information and Control"},{"key":"4_CR32","series-title":"Series in Machine Perception and Artificial Intelligence","first-page":"99","volume-title":"Advances in Structural and Syntactic Pattern Recognition","author":"J. Oncina","year":"1992","unstructured":"Oncina, J., Garc\u00eda, P.: Identifying regular languages in polynomial time. In: Advances in Structural and Syntactic Pattern Recognition. Series in Machine Perception and Artificial Intelligence, vol.\u00a05, pp. 99\u2013108. World Scientific, Singapore (1992)"},{"issue":"2","key":"4_CR33","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1016\/j.tcs.2003.11.008","volume":"313","author":"F. Denis","year":"2004","unstructured":"Denis, F., Lemay, A., Terlutte, A.: Learning regular languages using RFSA. Theoretical Computer Science\u00a0313(2), 267\u2013294 (2004)","journal-title":"Theoretical Computer Science"}],"container-title":["Lecture Notes in Computer Science","Grammatical Inference: Algorithms and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-88009-7_4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,5,10]],"date-time":"2024-05-10T03:48:47Z","timestamp":1715312927000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-540-88009-7_4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008]]},"ISBN":["9783540880080","9783540880097"],"references-count":33,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-88009-7_4","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2008]]}}}