{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,13]],"date-time":"2025-11-13T10:03:44Z","timestamp":1763028224887,"version":"3.45.0"},"reference-count":17,"publisher":"Elsevier","isbn-type":[{"type":"print","value":"9781558601413"}],"license":[{"start":{"date-parts":[[1990,1,1]],"date-time":"1990-01-01T00:00:00Z","timestamp":631152000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[1990,1,1]],"date-time":"1990-01-01T00:00:00Z","timestamp":631152000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/legal\/tdmrep-license"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1990]]},"DOI":"10.1016\/b978-1-55860-141-3.50049-3","type":"book-chapter","created":{"date-parts":[[2014,7,1]],"date-time":"2014-07-01T02:53:40Z","timestamp":1404183220000},"page":"384-391","source":"Crossref","is-referenced-by-count":11,"title":["Learning String Patterns and Tree Patterns from Examples"],"prefix":"10.1016","author":[{"given":"Ker-I","family":"Ko","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Assaf","family":"Marron","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Wen-Guey","family":"Tzeng","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"78","reference":[{"key":"10.1016\/B978-1-55860-141-3.50049-3_bib1","doi-asserted-by":"crossref","first-page":"46","DOI":"10.1016\/0022-0000(80)90041-0","article-title":"Finding patterns common to a set of strings","volume":"21","author":"Angluin","year":"1980","journal-title":"J. of Computer and System Sciences"},{"key":"10.1016\/B978-1-55860-141-3.50049-3_bib2","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1145\/356914.356918","article-title":"Inductive inference: theory and methods","volume":"15","author":"Angluin","year":"1983","journal-title":"Computing Survey"},{"key":"10.1016\/B978-1-55860-141-3.50049-3_bib3","doi-asserted-by":"crossref","first-page":"377","DOI":"10.1016\/0020-0190(87)90114-1","article-title":"Occam's razor","volume":"24","author":"Blumer","year":"1987","journal-title":"Information Processing Letters"},{"issue":"4","key":"10.1016\/B978-1-55860-141-3.50049-3_bib4","doi-asserted-by":"crossref","first-page":"929","DOI":"10.1145\/76359.76371","article-title":"Learnability and the Vapnik-Chervonenkis dimension","volume":"36","author":"Blumer","year":"1989","journal-title":"J. of ACM"},{"key":"10.1016\/B978-1-55860-141-3.50049-3_bib5","doi-asserted-by":"crossref","unstructured":"D. Benanav, D. Kapur, P. Narendran, Complexity of matching problems, Proc. 1st Conference on Rewriting Techniques and Applications, Springer Verlag, 1985","DOI":"10.1007\/3-540-15976-2_22"},{"key":"10.1016\/B978-1-55860-141-3.50049-3_bib6","doi-asserted-by":"crossref","unstructured":"C. Dwork, P. Kanellakis, J.C. Mitchell, Oil the sequential nature of unification, J. of Logic Programming 1:35\u201350","DOI":"10.1016\/0743-1066(84)90022-0"},{"key":"10.1016\/B978-1-55860-141-3.50049-3_bib7","doi-asserted-by":"crossref","unstructured":"C. Dwork, P. Kanellakis, L. Stockmeyer, Parallel algorithm for term matching, Proc. 8th Conference on Automated Deduction, 1986","DOI":"10.1007\/3-540-16780-3_109"},{"year":"1979","series-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"Garey","key":"10.1016\/B978-1-55860-141-3.50049-3_bib8"},{"key":"10.1016\/B978-1-55860-141-3.50049-3_bib9","doi-asserted-by":"crossref","unstructured":"W.I. Gasarch, C.H. Smith, Learning via queries, Proc. 29th IEEE Symposium on Foundations of Computer Science, pp. 130\u2013137, 1988","DOI":"10.1109\/SFCS.1988.21931"},{"key":"10.1016\/B978-1-55860-141-3.50049-3_bib10","unstructured":"D. Haussler, M. Kearns, N. Littlestone, M.k. Warmuth, Equivalence of models for polynomial learnability, Proc. 1st Workshop on Computational Learning Theory, pp.42\u201355, Morgan Kaufmann, San Mateo, CA, 1988"},{"issue":"1","key":"10.1016\/B978-1-55860-141-3.50049-3_bib11","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1016\/0022-0000(87)90006-7","article-title":"A note oil the two-variable pattern-finding problem","volume":"34","author":"Ko","year":"1987","journal-title":"J. of Computer and System Sciences"},{"key":"10.1016\/B978-1-55860-141-3.50049-3_bib12","doi-asserted-by":"crossref","unstructured":"M. Kearns, L. Pitt, A polynomial-time algorithm for learning k-variable pattern languages from examples, Proc. 2nd Workshop on Computational Learning Theory, pp.57\u201370, Morgan Kaufmann, San Mateo, CA, 1989","DOI":"10.1016\/B978-0-08-094829-4.50007-6"},{"key":"10.1016\/B978-1-55860-141-3.50049-3_bib13","unstructured":"A. Marron, Learning Pattern Languages from Examples and from Queries, Ph.D. Thesis, University of Houston, 1989"},{"key":"10.1016\/B978-1-55860-141-3.50049-3_bib14","doi-asserted-by":"crossref","unstructured":"R. Schapire, Pattern languages are not learnable, manuscript, 1989","DOI":"10.1016\/B978-1-55860-146-8.50012-6"},{"key":"10.1016\/B978-1-55860-141-3.50049-3_bib15","unstructured":"W. Tzeng, K. Ko, Finding common patterns is complete for the second level of the polynomial time hierarchy, manuscript, 1990"},{"issue":"11","key":"10.1016\/B978-1-55860-141-3.50049-3_bib16","doi-asserted-by":"crossref","first-page":"1134","DOI":"10.1145\/1968.1972","article-title":"A theory of the learnable","volume":"27","author":"Valiant","year":"1984","journal-title":"Communication of ACM"},{"key":"10.1016\/B978-1-55860-141-3.50049-3_bib17","unstructured":"R.M. Verma, I.V. Ramakrishnan, Tight complexity bounds for some AC matching problems, Symposium on Theoretical Aspects of Computer Science, 1989"}],"container-title":["Machine Learning Proceedings 1990"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:B9781558601413500493?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:B9781558601413500493?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2025,11,13]],"date-time":"2025-11-13T09:59:26Z","timestamp":1763027966000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/B9781558601413500493"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1990]]},"ISBN":["9781558601413"],"references-count":17,"URL":"https:\/\/doi.org\/10.1016\/b978-1-55860-141-3.50049-3","relation":{},"subject":[],"published":{"date-parts":[[1990]]}}}