{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,11]],"date-time":"2025-07-11T10:46:40Z","timestamp":1752230800253,"version":"3.33.0"},"publisher-location":"Berlin, Heidelberg","reference-count":46,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540667483"},{"type":"electronic","value":"9783540467694"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1999]]},"DOI":"10.1007\/3-540-46769-6_29","type":"book-chapter","created":{"date-parts":[[2007,2,28]],"date-time":"2007-02-28T12:42:39Z","timestamp":1172666559000},"page":"347-363","source":"Crossref","is-referenced-by-count":8,"title":["On Learning Unions of Pattern Languages and Tree Patterns"],"prefix":"10.1007","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":"297","published-online":{"date-parts":[[2000,5,19]]},"reference":[{"key":"29_CR1","doi-asserted-by":"crossref","unstructured":"Andris Ambainis, Sanjay Jain, and Arun Sharma. Ordinal mind change complexity of language identification. In Computational Learning Theory: Eurocolt\u2019 97, pages 301\u2013315. Springer-Verlag, 1997.","DOI":"10.1007\/3-540-62685-9_25"},{"key":"29_CR2","first-page":"175","volume-title":"Proc. 11th Annu. Conf. on Comput. Learning Theory","author":"T. R. Amoth","year":"1998","unstructured":"Thomas R. Amoth, Paul Cull, and Prasad Tadepalli. Exact learning of tree patterns from queries and counterexamples. In Proc. 11th Annu. Conf. on Comput. Learning Theory, pages 175\u2013186. ACM Press, New York, NY, 1998."},{"key":"29_CR3","first-page":"323","volume-title":"Proc. 12th Annu. Conf. on Comput. Learning Theory","author":"T. R. Amoth","year":"1999","unstructured":"Thomas R. Amoth, Paul Cull, and Prasad Tadepalli. Exact learning of unordered tree patterns from queries. In Proc. 12th Annu. Conf. on Comput. Learning Theory, pages 323\u2013332. ACM Press, New York, NY, 1999."},{"key":"29_CR4","doi-asserted-by":"publisher","first-page":"46","DOI":"10.1016\/0022-0000(80)90041-0","volume":"21","author":"D. Angluin","year":"1980","unstructured":"D. Angluin. Finding patterns common to a set of strings. J. of Comput. Syst. Sci., 21:46\u201362, 1980.","journal-title":"J. of Comput. Syst. Sci."},{"issue":"2","key":"29_CR5","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1016\/S0019-9958(80)90285-5","volume":"45","author":"D. Angluin","year":"1980","unstructured":"D. Angluin. Inductive inference of formal languages from positive data. Inform. Control, 45(2):117\u2013135, May 1980.","journal-title":"Inform. Control"},{"issue":"4","key":"29_CR6","first-page":"319","volume":"2","author":"D. Angluin","year":"1988","unstructured":"D. Angluin. Queries and concept learning. Machine Learning, 2(4):319\u2013342, April 1988.","journal-title":"Machine Learning"},{"key":"29_CR7","doi-asserted-by":"crossref","unstructured":"S. Arikawa, S. Kuhara, S. Miyano, Y. Mukouchi, A. Shinohara, and T. Shinohara. A machine discovery from amino acid sequences by decision trees over regular patterns. In Intern. Conference on Fifth Generation Computer Systems, 1992.","DOI":"10.1007\/BF03037183"},{"issue":"4","key":"29_CR8","first-page":"405","volume":"E75-D","author":"S. Arikawa","year":"1992","unstructured":"S. Arikawa, S. Miyano, A. Shinohara, T. Shinohara, and A. Yamamota. Algorithmic learning theory with elementary formal systems. In IEICE Trans. Inf. And Syst., volume E75-D No 4, pages 405\u2013414, 1992.","journal-title":"IEICE Trans. Inf. And Syst."},{"key":"29_CR9","doi-asserted-by":"crossref","first-page":"107","DOI":"10.1007\/BFb0030388","volume":"659","author":"S. Arikawa","year":"1991","unstructured":"S. Arikawa, A. Shinohara, S. Miyano, and A. Shinohara. More about learning elementary formal systems. In Nonmonotonic and Inductive Logic, Lecture Notes in Artificial Intelligence, volume 659, pages 107\u2013117. Springer-Verlag, 1991.","journal-title":"Nonmonotonic and Inductive Logic, Lecture Notes in Artificial Intelligence"},{"key":"29_CR10","first-page":"59","volume":"13","author":"H. Arimura","year":"1994","unstructured":"H. Arimura, H. Ishizaka, T. Shinohara, and S. Otsuki. A generalization of the least general generalization. In Machine Learning, volume 13, pages 59\u201385. Oxford Univ. Press, 1994.","journal-title":"Machine Learning"},{"key":"29_CR11","doi-asserted-by":"crossref","unstructured":"Hiroki Arimura, Hiroki Ishizaka, and Takeshi Shinohara. Learning unions of tree patterns using queries. In Proc. 6th Int. Workshop on Algorithmic Learning Theory, pages 66\u201379. Springer-Verlag, 1995.","DOI":"10.1007\/3-540-60454-5_29"},{"key":"29_CR12","first-page":"312","volume-title":"Proceedings of the 36th Annual Symposium on Foundations of Computer Science","author":"P. Auer","year":"1995","unstructured":"Peter Auer and Manfred Warmuth. Tracking the best disjunction. In Proceedings of the 36th Annual Symposium on Foundations of Computer Science, pages 312\u2013321. IEEE Computer Society Press, Los Alamitos, CA, 1995."},{"key":"29_CR13","doi-asserted-by":"crossref","first-page":"2241","DOI":"10.1093\/nar\/19.suppl.2241","volume":"19","author":"A. Bairoch","year":"1991","unstructured":"A. Bairoch. Prosite: A dictionary of sites and patterns in proteins. In Nucleic Acid Research, volume 19, pages 2241\u20132245, 1991.","journal-title":"Nucleic Acid Research"},{"key":"29_CR14","first-page":"1224","volume":"13","author":"J. M. Barzdin","year":"1972","unstructured":"J. M. Barzdin and R. V. Frievald. On the prediction of general recursive functions. Soviet Math. Doklady, 13:1224\u20131228, 1972.","journal-title":"Soviet Math. Doklady"},{"key":"29_CR15","first-page":"65","volume":"18","author":"C. Cardie","year":"1997","unstructured":"C. Cardie. Empirical methods in information extraction. In AI Magazine, volume 18, pages 65\u201380, 1997.","journal-title":"AI Magazine"},{"key":"29_CR16","doi-asserted-by":"crossref","unstructured":"Thomas Erlebach, Peter Rossmanith, Hans Stadtherr, Angelika Steger, and Thomas Zeugmann. Learning one-variable pattern languages very efficiently on average, in parallel, and by asking queries. In Algorithmic Learning Theory: ALT\u2019 97, pages 260\u2013276. Springer-Verlag, 1997.","DOI":"10.1007\/3-540-63577-7_48"},{"key":"29_CR17","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1145\/267460.267520","volume-title":"Proc. 10th Annu. Conf. on Comput. Learning Theory","author":"S. A. Goldman","year":"1997","unstructured":"Sally A. Goldman, Stephen S. Kwek, and Stephen D. Scott. Agnostic learning of geometric patterns. In Proc. 10th Annu. Conf. on Comput. Learning Theory, pages 325\u2013333. ACM Press, New York, NY, 1997."},{"key":"29_CR18","unstructured":"C. Hua and K. Ko. A note on the pattern-finding problem. Technical Report UH-CS-84-4, Department of Computer Science, University of Houston, 1984."},{"key":"29_CR19","unstructured":"O. H. Ibarra and T. Jiang. Learning regular languages from counterexamples. In Proc. 1st Annu. Workshop on Comput. Learning Theory, pages 371\u2013385, San Mateo, CA, 1988. Morgan Kaufmann."},{"key":"29_CR20","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1145\/238061.238093","volume-title":"Proc. 9th Annu. Conf. on Comput. Learning Theory","author":"S. Jain","year":"1996","unstructured":"Sanjay Jain and Arun Sharma. Elementary formal systems, intrinsic complexity, and procrastination. In Proc. 9th Annu. Conf. on Comput. Learning Theory, pages 181\u2013192. ACM Press, New York, NY, 1996."},{"key":"29_CR21","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"314","DOI":"10.1007\/3-540-12920-0_29","volume-title":"Proceedings of the Symposium of Theoretical Aspects of Computer Science","author":"K. P. Jantke","year":"1984","unstructured":"K. P. Jantke. Polynomial-time inference of general pattern languages. In Proceedings of the Symposium of Theoretical Aspects of Computer Science; Lecture Notes in Computer Science, volume 166, pages 314\u2013325. Springer, 1984."},{"key":"29_CR22","doi-asserted-by":"crossref","unstructured":"K. P. Jantke and S. Lange. Case-based representation and learning of pattern languages. In Proc. 4th Internat. Workshop on Algorithmic Learning Theory, pages 87\u2013100. Springer-Verlag, 1993. Lecture Notes in Artificial Intelligence 744.","DOI":"10.1007\/3-540-57370-4_39"},{"key":"29_CR23","unstructured":"C. Page Jr. and A. Frisch. Generalization and learnability: A study of constrained atoms. In Inductive Logic Programming, pages 29\u201361, 1992."},{"key":"29_CR24","doi-asserted-by":"crossref","unstructured":"M. Kearns and L. Pitt. A polynomial-time algorithm for learning k-variable pattern languages from examples. In Proc. 2nd Annu. Workshop on Comput. Learning Theory, pages 57\u201371, San Mateo, CA, 1989. Morgan Kaufmann.","DOI":"10.1016\/B978-0-08-094829-4.50007-6"},{"key":"29_CR25","doi-asserted-by":"crossref","unstructured":"K. Ko, A. Marron, and W. Tzeng. Learnig string patterns and tree patterns from examples. abstract. In State University of New York Stony Brook, 1989.","DOI":"10.1016\/B978-1-55860-141-3.50049-3"},{"issue":"3","key":"29_CR26","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1007\/BF01200064","volume":"1","author":"K. Ko","year":"1991","unstructured":"K. Ko and W. Tzeng. Three \u03a3 2 p -complete problems in computational learning theory. Computational Complexity, 1(3):269\u2013310, 1991.","journal-title":"Computational Complexity"},{"key":"29_CR27","doi-asserted-by":"publisher","first-page":"361","DOI":"10.1007\/BF03037093","volume":"8","author":"S. Lange","year":"1991","unstructured":"S. Lange and R. Wiehagen. Polynomial time inference of arbitrary pattern languages. New Generation Computing, 8:361\u2013370, 1991.","journal-title":"New Generation Computing"},{"key":"29_CR28","first-page":"285","volume":"2","author":"N. Littlestone","year":"1988","unstructured":"N. Littlestone. Learning when irrelevant attributes abound: A new linear-threshold algorithm. Machine Learning, 2:285\u2013318, 1988.","journal-title":"Machine Learning"},{"key":"29_CR29","doi-asserted-by":"crossref","unstructured":"N. Littlestone. Redundant noisy attributes, attribute errors, and linear threshold learning using Winnow. In Proc. 4th Annu. Workshop on Comput. Learning Theory, pages 147\u2013156, San Mateo, CA, 1991. Morgan Kaufmann.","DOI":"10.1016\/B978-1-55860-213-7.50017-1"},{"issue":"2","key":"29_CR30","doi-asserted-by":"publisher","first-page":"212","DOI":"10.1006\/inco.1994.1009","volume":"108","author":"N. Littlestone","year":"1994","unstructured":"N. Littlestone and M. K. Warmuth. The weighted majority algorithm. Information and Computation, 108(2):212\u2013261, 1994.","journal-title":"Information and Computation"},{"key":"29_CR31","unstructured":"A. Marron. Learning pattern languages from a single initial example and from queries. In Proc. 1st Annu. Workshop on Comput. Learning Theory, pages 345\u2013358, San Mateo, CA, 1988. Morgan Kaufmann."},{"key":"29_CR32","doi-asserted-by":"crossref","unstructured":"Satoshi Matsumoto and Ayumi Shinohara. Learning pattern languages using queries. In Computational Learning Theory: Eurocolt\u2019 97, pages 185\u2013197. Springer-Verlag, 1997.","DOI":"10.1007\/3-540-62685-9_16"},{"key":"29_CR33","first-page":"64","volume-title":"Proc. 11th Annu. Conf. on Comput. Learning Theory","author":"A. R. Mitchell","year":"1998","unstructured":"Andrew R. Mitchell. Learnability of a subclass of extended pattern languages. In Proc. 11th Annu. Conf. on Comput. Learning Theory, pages 64\u201371. ACM Press, New York, NY, 1998."},{"key":"29_CR34","first-page":"163","volume-title":"Machine Learning","author":"T. Mitchell","year":"1983","unstructured":"T. Mitchell, P. Utgoff, and R. Banerji. Learning by experimentation: Acquiring and refining problem solving heuristics. In R. Michalski, J. Carbonell, T. Mitchell eds., Machine Learning, pages 163\u2013190. Palo Alto, CA: Tioga, 1983."},{"key":"29_CR35","unstructured":"S. Miyano, A. Shinohara, and T. Shinohara. Which classes of elementary formal systems are polynomial-time learnable? In Proc. 2nd Int. Workshop on Algorithmic Learning Theory, pages 139\u2013150. IOS Press, 1992."},{"key":"29_CR36","doi-asserted-by":"crossref","unstructured":"R. Nix. Editing by example. In Proc. 11th ACM Symposium on Principles of Programming Languages, pages 186\u2013195. ACM Press, 1984.","DOI":"10.1145\/800017.800530"},{"issue":"3","key":"29_CR37","doi-asserted-by":"publisher","first-page":"430","DOI":"10.1016\/0022-0000(90)90028-J","volume":"41","author":"L. Pitt","year":"1990","unstructured":"L. Pitt and M. K. Warmuth. Prediction preserving reducibility. J. of Comput. Syst. Sci., 41(3):430\u2013467, December 1990. Special issue of the for the Third Annual Conference of Structure in Complexity Theory (Washington, DC., June 88).","journal-title":"J. of Comput. Syst. Sci."},{"key":"29_CR38","first-page":"198","volume-title":"Proc. 11th Annu. Conf. on Comput. Learning Theory","author":"R. Reischuk","year":"1998","unstructured":"R\u00fcdiger Reischuk and Thomas Zeugmann. Learning one-variable pattern languages in linear average time. In Proc. 11th Annu. Conf. on Comput. Learning Theory, pages 198\u2013208. ACM Press, New York, NY, 1998."},{"key":"29_CR39","doi-asserted-by":"crossref","unstructured":"R. E. Schapire. Pattern languages are not learnable. In Proc. 3rd Annu. Workshop on Comput. Learning Theory, pages 122\u2013129, San Mateo, CA, 1990. Morgan Kaufmann.","DOI":"10.1016\/B978-1-55860-146-8.50012-6"},{"key":"29_CR40","series-title":"Lect Notes Comput Sci","first-page":"115","volume-title":"RIMS Symposia on Software Science and Engineering, Kyoto, Japan","author":"T. Shinohara","year":"1982","unstructured":"T. Shinohara. Polynomial time inference of extended regular pattern languages. In RIMS Symposia on Software Science and Engineering, Kyoto, Japan, pages 115\u2013127. Springer Verlag, 1982. Lecture Notes in Computer Science 147."},{"key":"29_CR41","unstructured":"T. Shinohara. Polynomial time inference of pattern languages and its applications. Proceedings, 7th IBM Symp. on Math. Foundations of Computer Science, 1982."},{"key":"29_CR42","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1007\/3-540-60922-9_19","volume-title":"Proc. 13th Symposium on Theoretical Aspects of Computer Science","author":"E. Tateishi","year":"1996","unstructured":"E. Tateishi, O. Maruyama, and 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 1046, pages 219\u2013230, 1996."},{"key":"29_CR43","doi-asserted-by":"crossref","unstructured":"E. Tateishi and S. Miyano. A greedy strategy for finding motifs from positive and negative examples. In Proc. First Pacific Symposium on Biocomputing, pages 599\u2013613. World Scientific Press, 1996.","DOI":"10.1007\/3-540-60922-9_19"},{"key":"29_CR44","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1080\/09528139408953785","volume":"6","author":"R. Wiehagen","year":"1994","unstructured":"R. Wiehagen and T. Zeugmann. Ingnoring data may be the only way to learn efficiently. Journal of Experimental and Artificial Intelligence, 6:131\u2013144, 1994.","journal-title":"Journal of Experimental and Artificial Intelligence"},{"key":"29_CR45","doi-asserted-by":"crossref","unstructured":"K. Wright. Identification of unions of languages drawn from an identifiable class. In Proc. 2nd Annu. Workshop on Comput. Learning Theory, pages 328\u2013333. Morgan Kaufmann, 1989. (See also the correction by Motoki, Shinohara and Wright in the Proceedings of the Fourth Annual Workshop on Computational Learning Theory, page 375, 1991).","DOI":"10.1016\/B978-0-08-094829-4.50026-X"},{"key":"29_CR46","unstructured":"T. Zeugmann. Lange and Wiehagen\u2019s pattern language learning algorithm: An average-case analysis with respect to its total learning time. Technical Report RIFIS-TR-CS-111, RIFIS, Kyushu University 33, 1995."}],"container-title":["Lecture Notes in Computer Science","Algorithmic Learning Theory"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-46769-6_29","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,14]],"date-time":"2025-01-14T09:40:09Z","timestamp":1736847609000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-46769-6_29"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1999]]},"ISBN":["9783540667483","9783540467694"],"references-count":46,"URL":"https:\/\/doi.org\/10.1007\/3-540-46769-6_29","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[1999]]}}}