{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,3]],"date-time":"2022-04-03T05:43:44Z","timestamp":1648964624073},"reference-count":50,"publisher":"Elsevier BV","issue":"2","license":[{"start":{"date-parts":[[2002,10,1]],"date-time":"2002-10-01T00:00:00Z","timestamp":1033430400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2013,7,17]],"date-time":"2013-07-17T00:00:00Z","timestamp":1374019200000},"content-version":"vor","delay-in-days":3942,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theoretical Computer Science"],"published-print":{"date-parts":[[2002,10]]},"DOI":"10.1016\/s0304-3975(01)00402-9","type":"journal-article","created":{"date-parts":[[2002,10,11]],"date-time":"2002-10-11T20:38:10Z","timestamp":1034368690000},"page":"237-254","source":"Crossref","is-referenced-by-count":6,"title":["On learning unions of pattern languages and tree patterns in the mistake bound model"],"prefix":"10.1016","volume":"288","author":[{"given":"Sally A.","family":"Goldman","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Stephen S.","family":"Kwek","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"78","reference":[{"issue":"2","key":"10.1016\/S0304-3975(01)00402-9_BIB1","doi-asserted-by":"crossref","first-page":"323","DOI":"10.1016\/S0304-3975(99)00005-5","article-title":"Ordinal mind change complexity of language identification","volume":"220","author":"Ambainis","year":"1999","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/S0304-3975(01)00402-9_BIB2","series-title":"Proc. 11th Annu. Conf. on Computational Learning Theory","first-page":"175","article-title":"Exact learning of tree patterns from queries and counterexamples","author":"Amoth","year":"1998"},{"key":"10.1016\/S0304-3975(01)00402-9_BIB3","series-title":"Proc. 12th Annu. Conf. on Computational Learning Theory","first-page":"323","article-title":"Exact learning of unordered tree patterns from queries","author":"Amoth","year":"1999"},{"key":"10.1016\/S0304-3975(01)00402-9_BIB4","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. Comput. Systems Sci."},{"issue":"2","key":"10.1016\/S0304-3975(01)00402-9_BIB5","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1016\/S0019-9958(80)90285-5","article-title":"Inductive inference of formal languages from positive data","volume":"45","author":"Angluin","year":"1980","journal-title":"Inform. and Control"},{"issue":"4","key":"10.1016\/S0304-3975(01)00402-9_BIB6","doi-asserted-by":"crossref","first-page":"319","DOI":"10.1007\/BF00116828","article-title":"Queries and concept learning","volume":"2","author":"Angluin","year":"1988","journal-title":"Mach. Learning"},{"key":"10.1016\/S0304-3975(01)00402-9_BIB7","unstructured":"S. Arikawa, S. Kuhara, S. Miyano, Y. Mukouchi, A. Shinohara, T. Shinohara, A machine discovery from amino acid sequences by decision trees over regular patterns, in: Internat. Conf. on Fifth Generation Computer Systems, 1992, pp. 618\u2013625."},{"issue":"4","key":"10.1016\/S0304-3975(01)00402-9_BIB8","first-page":"405","article-title":"Algorithmic learning theory with elementary formal systems","volume":"E75-D","author":"Arikawa","year":"1992","journal-title":"IEICE Trans. Inform. and Syst."},{"key":"10.1016\/S0304-3975(01)00402-9_BIB9","first-page":"107","article-title":"More about learning elementary formal systems","volume":"Vol. 659","author":"Arikawa","year":"1991"},{"key":"10.1016\/S0304-3975(01)00402-9_BIB10","first-page":"59","article-title":"A generalization of the least general generalization","volume":"Vol. 13","author":"Arimura","year":"1994"},{"key":"10.1016\/S0304-3975(01)00402-9_BIB11","first-page":"66","article-title":"Learning unions of tree patterns using queries","volume":"Vol. 872","author":"Arimura","year":"1995"},{"key":"10.1016\/S0304-3975(01)00402-9_BIB12","series-title":"Proc. 36th Annu. Symp. on Foundations of Computer Science","first-page":"312","article-title":"Tracking the best disjunction","author":"Auer","year":"1995"},{"key":"10.1016\/S0304-3975(01)00402-9_BIB13","doi-asserted-by":"crossref","first-page":"2241","DOI":"10.1093\/nar\/19.suppl.2241","article-title":"Prosite","volume":"19","author":"Bairoch","year":"1991","journal-title":"Nucleic Acid Res."},{"key":"10.1016\/S0304-3975(01)00402-9_BIB14","first-page":"1224","article-title":"On the prediction of general recursive functions","volume":"13","author":"Barzdin","year":"1972","journal-title":"Soviet Math. Dokl."},{"key":"10.1016\/S0304-3975(01)00402-9_BIB15","first-page":"65","article-title":"Empirical methods in information extraction","volume":"18","author":"Cardie","year":"1997","journal-title":"AI Mag."},{"key":"10.1016\/S0304-3975(01)00402-9_BIB16","first-page":"260","article-title":"Learning one-variable pattern languages very efficiently on average, in parallel, and by asking queries","volume":"Vol. 1316","author":"Erlebach","year":"1997"},{"issue":"1","key":"10.1016\/S0304-3975(01)00402-9_BIB17","doi-asserted-by":"crossref","first-page":"123","DOI":"10.1006\/jcss.2000.1723","article-title":"Agnostic learning of geometric patterns","volume":"62","author":"Goldman","year":"2001","journal-title":"J. Comput. Systems Sci."},{"key":"10.1016\/S0304-3975(01)00402-9_BIB18","unstructured":"C. Hua, K. Ko, A note on the pattern-finding problem, Technical Report UH-CS-84-4, Department of Computer Science, University of Houston, 1984."},{"key":"10.1016\/S0304-3975(01)00402-9_BIB19","series-title":"Proc. 1st Annu. Workshop on Computational Learning Theory","first-page":"371","article-title":"Learning regular languages from counterexamples","author":"Ibarra","year":"1988"},{"key":"10.1016\/S0304-3975(01)00402-9_BIB20","unstructured":"N. Inago, H. Arimura, Polynomial time online-learning of one-variable pattern languages, in: Proc. LA Winter Symp. 1998, RIMS Lecture Notes, Vol. 1041, April 1998, pp. 183\u2013190 (in Japanese)."},{"key":"10.1016\/S0304-3975(01)00402-9_BIB21","unstructured":"N. Inago, H. Arimura, Empirical Comparison of two online algorithms for learning one-variable pattern languages, in: Proc. Annu. Meeting of IPSJ, Kyushu Chapter, Information Processing Society Japan (IPSJ), Kagoshima, Japan, March 1998 (in Japanese)."},{"issue":"1","key":"10.1016\/S0304-3975(01)00402-9_BIB22","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1006\/inco.1996.2614","article-title":"Elementary formal systems, intrinsic complexity, and procrastination","volume":"132","author":"Jain","year":"1997","journal-title":"Inform. and Comput."},{"key":"10.1016\/S0304-3975(01)00402-9_BIB23","first-page":"314","article-title":"Polynomial-time inference of general pattern languages","volume":"Vol. 166","author":"Jantke","year":"1984"},{"key":"10.1016\/S0304-3975(01)00402-9_BIB24","first-page":"87","article-title":"Case-based representation and learning of pattern languages","volume":"Vol. 744","author":"Jantke","year":"1993"},{"key":"10.1016\/S0304-3975(01)00402-9_BIB25","unstructured":"C. Page Jr., A. Frisch, Generalization and learnability: a study of constrained atoms, in: S. Muggleton (Ed.), Inductive Logic Programming, 1992, pp. 29\u201361."},{"key":"10.1016\/S0304-3975(01)00402-9_BIB26","first-page":"57","article-title":"A polynomial-time algorithm for learning k-variable pattern languages from examples","author":"Kearns","year":"1989"},{"key":"10.1016\/S0304-3975(01)00402-9_BIB27","doi-asserted-by":"crossref","unstructured":"K. Ko, A. Marron, W. Tzeng, Learning string patterns and tree patterns from examples. abstract, in: Proc. 7th Int. Conf. on Machine Learning, 1990, pp. 384\u2013391.","DOI":"10.1016\/B978-1-55860-141-3.50049-3"},{"issue":"3","key":"10.1016\/S0304-3975(01)00402-9_BIB28","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1007\/BF01200064","article-title":"Three \u03a32p-complete problems in computational learning theory","volume":"1","author":"Ko","year":"1991","journal-title":"Comput. Complexity"},{"key":"10.1016\/S0304-3975(01)00402-9_BIB29","doi-asserted-by":"crossref","first-page":"361","DOI":"10.1007\/BF03037093","article-title":"Polynomial time inference of arbitrary pattern languages","volume":"8","author":"Lange","year":"1991","journal-title":"New Generation Comput."},{"key":"10.1016\/S0304-3975(01)00402-9_BIB30","doi-asserted-by":"crossref","first-page":"285","DOI":"10.1007\/BF00116827","article-title":"Learning when irrelevant attributes abound","volume":"2","author":"Littlestone","year":"1998","journal-title":"Mach. Learning"},{"key":"10.1016\/S0304-3975(01)00402-9_BIB31","series-title":"Proc. 4th Annu. Workshop on Computational Learning Theory","first-page":"147","article-title":"Redundant noisy attributes, attribute errors, and linear threshold learning using Winnow","author":"Littlestone","year":"1991"},{"issue":"2","key":"10.1016\/S0304-3975(01)00402-9_BIB32","doi-asserted-by":"crossref","first-page":"212","DOI":"10.1006\/inco.1994.1009","article-title":"The weighted majority algorithm","volume":"108","author":"Littlestone","year":"1994","journal-title":"Informat. and Comput."},{"key":"10.1016\/S0304-3975(01)00402-9_BIB33","series-title":"Proc. 1st Annu. Workshop on Comput. Learning Theory","first-page":"345","article-title":"Learning pattern languages from a single initial example and from queries","author":"Marron","year":"1988"},{"key":"10.1016\/S0304-3975(01)00402-9_BIB34","first-page":"185","article-title":"Learning pattern languages using queries","volume":"Vol. 1208","author":"Matsumoto","year":"1997"},{"key":"10.1016\/S0304-3975(01)00402-9_BIB35","series-title":"Proc. 11th Annu. Conf. on Computational Learning Theory","first-page":"64","article-title":"Learnability of a subclass of extended pattern languages","author":"Mitchell","year":"1998"},{"key":"10.1016\/S0304-3975(01)00402-9_BIB36","first-page":"93","article-title":"The VC-Dimension of Subclasses of Pattern Languages","volume":"Vol. 1720","author":"Mitchell","year":"1999"},{"key":"10.1016\/S0304-3975(01)00402-9_BIB37","series-title":"Mach. Learning","first-page":"163","article-title":"Learning by experimentation","author":"Mitchell","year":"1983"},{"key":"10.1016\/S0304-3975(01)00402-9_BIB38","series-title":"Proc. 2nd Int. Workshop on Algorithmic Learning Theory II","first-page":"139","article-title":"Which classes of elementary formal systems are polynomial-time learnable?","author":"Miyano","year":"1992"},{"key":"10.1016\/S0304-3975(01)00402-9_BIB39","series-title":"Proc. 11th ACM Symp. on Principles of Programming Languages","first-page":"186","article-title":"Editing by example","author":"Nix","year":"1984"},{"key":"10.1016\/S0304-3975(01)00402-9_BIB40","doi-asserted-by":"crossref","unstructured":"L. Pitt, M. Warmuth, Prediction preserving reducibility, J. Comput. Systems Sci. 41(3) (December 1990) 430\u2013467. (Special issue of the for the 3rd Annu. Conference of Structure in Complexity Theory, Washington, DC., June 1988).","DOI":"10.1016\/0022-0000(90)90028-J"},{"key":"10.1016\/S0304-3975(01)00402-9_BIB41","series-title":"Proc. 11th Annu. Conf. on Computational Learning Theory","first-page":"198","article-title":"Learning one-variable pattern languages in linear average time","author":"Reischuk","year":"1998"},{"key":"10.1016\/S0304-3975(01)00402-9_BIB42","series-title":"Proc. 3rd Annu. Workshop on Computational Learning Theory","first-page":"122","article-title":"Pattern languages are not learnable","author":"Schapire","year":"1990"},{"key":"10.1016\/S0304-3975(01)00402-9_BIB43","first-page":"115","article-title":"Polynomial time inference of extended regular pattern languages","volume":"Vol. 147","author":"Shinohara","year":"1982"},{"key":"10.1016\/S0304-3975(01)00402-9_BIB44","unstructured":"T. Shinohara, Polynomial time inference of pattern languages and its applications, Proc. 7th IBM Symp. on Math. Foundations of Computer Science, 1982."},{"key":"10.1016\/S0304-3975(01)00402-9_BIB45","unstructured":"E. Tateishi, O. Maruyama, S. Miyano, Extracting motifs from positive and negative sequence data, in: Proc. 13th Symposium on Theoretical Aspects of Computer Science, Lecture Notes in Computer Science, Vol. 1046, 1996, pp. 219\u2013230."},{"key":"10.1016\/S0304-3975(01)00402-9_BIB46","series-title":"Proc. 1st Pacific Symp. on Biocomputing","first-page":"599","article-title":"A greedy strategy for finding motifs from positive and negative examples","author":"Tateishi","year":"1996"},{"key":"10.1016\/S0304-3975(01)00402-9_BIB47","doi-asserted-by":"crossref","first-page":"1134","DOI":"10.1145\/1968.1972","article-title":"A theory of the learnable","volume":"11","author":"Valiant","year":"1984","journal-title":"Commu. ACM"},{"key":"10.1016\/S0304-3975(01)00402-9_BIB48","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1080\/09528139408953785","article-title":"Ignoring data may be the only way to learn efficiently","volume":"6","author":"Wiehagen","year":"1994","journal-title":"J. Exp. Artif. Intell."},{"key":"10.1016\/S0304-3975(01)00402-9_BIB49","doi-asserted-by":"crossref","unstructured":"K. Wright, Identification of unions of languages drawn from an identifiable class, in: Proc. 2nd Annu. Workshop on Computational Learning Theory, Morgan Kaufmann, 1989, pp. 328\u2013333. (See also the correction by Motoki, Shinohara and Wright in the Proc. 4th Annu. Workshop on Computational Learning Theory, 1991, p. 375.)","DOI":"10.1016\/B978-0-08-094829-4.50026-X"},{"key":"10.1016\/S0304-3975(01)00402-9_BIB50","unstructured":"T. Zeugmann, Lange and Wiehagen's pattern language learning algorithm: an average-case analysis with respect to its total learning time, in: Ann. Math. and Artif. Intell. 23(1\u20132) (1998) 117\u2013145 (special issue for ALT 1994 and AII 1994)."}],"container-title":["Theoretical Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0304397501004029?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0304397501004029?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2020,1,8]],"date-time":"2020-01-08T11:49:51Z","timestamp":1578484191000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0304397501004029"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002,10]]},"references-count":50,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2002,10]]}},"alternative-id":["S0304397501004029"],"URL":"https:\/\/doi.org\/10.1016\/s0304-3975(01)00402-9","relation":{},"ISSN":["0304-3975"],"issn-type":[{"value":"0304-3975","type":"print"}],"subject":[],"published":{"date-parts":[[2002,10]]}}}