{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,17]],"date-time":"2025-05-17T08:02:43Z","timestamp":1747468963802,"version":"3.30.1"},"reference-count":30,"publisher":"Elsevier BV","issue":"1-2","license":[{"start":{"date-parts":[[2001,5,1]],"date-time":"2001-05-01T00:00:00Z","timestamp":988675200000},"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":4460,"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":[[2001,5]]},"DOI":"10.1016\/s0304-3975(00)00043-8","type":"journal-article","created":{"date-parts":[[2002,7,25]],"date-time":"2002-07-25T10:59:17Z","timestamp":1027594757000},"page":"549-575","source":"Crossref","is-referenced-by-count":6,"title":["Monotone term decision lists"],"prefix":"10.1016","volume":"259","author":[{"given":"David","family":"Guijarro","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"V\u0131\u0301ctor","family":"Lav\u0131\u0301n","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Vijay","family":"Raghavan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"78","reference":[{"key":"10.1016\/S0304-3975(00)00043-8_BIB1","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":"Machine Learning"},{"key":"10.1016\/S0304-3975(00)00043-8_BIB2","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1007\/BF00116034","article-title":"Negative results for equivalence queries","volume":"5","author":"Angluin","year":"1990","journal-title":"Machine Learning"},{"issue":"1","key":"10.1016\/S0304-3975(00)00043-8_BIB3","doi-asserted-by":"crossref","first-page":"185","DOI":"10.1145\/138027.138061","article-title":"Learning read-once formulas with queries","volume":"40","author":"Angluin","year":"1993","journal-title":"J. ACM"},{"key":"10.1016\/S0304-3975(00)00043-8_BIB4","doi-asserted-by":"crossref","unstructured":"D. Angluin, M. Kri\u0137is, Learning with malicious membership queries and exceptions, Proc. 10th Ann. Conf. on computational Learning Theory, ACM Press, New York, NY, 1997, pp. 285\u2013297.","DOI":"10.1145\/267460.267515"},{"year":"1992","series-title":"Computational Learning Theory: An Introduction","author":"Anthony","key":"10.1016\/S0304-3975(00)00043-8_BIB5"},{"key":"10.1016\/S0304-3975(00)00043-8_BIB6","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0166-218X(94)00007-Z","article-title":"On specifying Boolean functions by labelled examples","volume":"61","author":"Anthony","year":"1995","journal-title":"Discrete Appl. Math."},{"key":"10.1016\/S0304-3975(00)00043-8_BIB7","doi-asserted-by":"crossref","first-page":"80","DOI":"10.1016\/S0020-0190(80)90078-2","article-title":"Equivalence of free Boolean graphs can be decided probabilistically in polynomial time","volume":"10","author":"Blum","year":"1980","journal-title":"Inform. Process. Lett."},{"key":"10.1016\/S0304-3975(00)00043-8_BIB8","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1016\/0304-3975(92)90367-O","article-title":"On the necessity of Occam algorithms","volume":"100","author":"Board","year":"1992","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/S0304-3975(00)00043-8_BIB9","doi-asserted-by":"crossref","first-page":"677","DOI":"10.1109\/TC.1986.1676819","article-title":"Graph based algorithms for Boolean function manipulation","volume":"C-35","author":"Bryant","year":"1986","journal-title":"IEEE Trans. Comput."},{"key":"10.1016\/S0304-3975(00)00043-8_BIB10","doi-asserted-by":"crossref","unstructured":"N. Bshouty, Simple learning algorithms using divide and conquer, Proc. 8th Ann. Conf. on Computational Learning Theory, 1995, pp. 447\u2013453.","DOI":"10.1145\/225298.225352"},{"key":"10.1016\/S0304-3975(00)00043-8_BIB11","doi-asserted-by":"crossref","unstructured":"J. Castro, J.L. Balc\u00e1zar, Simple PAC Learning of Simple Decision Lists, Proc. 6th Internat. Workshop on Algorithmic Learning Theory (ALT\u201995), Lecture Notes in Artificial Intelligence, Vol. 997, Springer, Berlin, 1995, pp. 239\u2013250.","DOI":"10.1007\/3-540-60454-5_42"},{"key":"10.1016\/S0304-3975(00)00043-8_BIB12","doi-asserted-by":"crossref","first-page":"231","DOI":"10.1016\/0890-5401(89)90001-1","article-title":"Learning decision trees from random examples","volume":"82","author":"Ehrenfeucht","year":"1989","journal-title":"Inform. and Comput."},{"key":"10.1016\/S0304-3975(00)00043-8_BIB13","doi-asserted-by":"crossref","first-page":"618","DOI":"10.1006\/jagm.1996.0062","article-title":"On the complexity of dualization of monotone disjunctive normal form","volume":"21","author":"Fredman","year":"1996","journal-title":"J. Algorithms"},{"key":"10.1016\/S0304-3975(00)00043-8_BIB14","doi-asserted-by":"crossref","unstructured":"S. Goldman, M. Kearns, On the complexity of teaching, Proc. 4th Ann. Workshop on Computational Learning Theory, 1991, pp. 303\u2013314.","DOI":"10.1016\/B978-1-55860-213-7.50031-6"},{"key":"10.1016\/S0304-3975(00)00043-8_BIB15","doi-asserted-by":"crossref","unstructured":"D. Guijarro, V. Lav\u0131\u0301n, V. Raghavan, Learning monotone term decision lists, Proc. 3rd European Conf. on Computational Learning Theory (Eurocolt\u201997), Lecture Notes in Artificial Intelligence, Vol. 1208, Springer, Berlin, 1997, pp. 16\u201326.","DOI":"10.1007\/3-540-62685-9_3"},{"issue":"2","key":"10.1016\/S0304-3975(00)00043-8_BIB16","doi-asserted-by":"crossref","first-page":"114","DOI":"10.1006\/inco.1996.0040","article-title":"Lower bounds on learning decision lists and trees","volume":"126","author":"Hancock","year":"1996","journal-title":"Inform. and Comput."},{"issue":"5","key":"10.1016\/S0304-3975(00)00043-8_BIB17","doi-asserted-by":"crossref","first-page":"840","DOI":"10.1145\/234752.234755","article-title":"How many queries are needed to learn?","volume":"43","author":"Hellerstein","year":"1996","journal-title":"J. ACM"},{"year":"1994","series-title":"An Introduction to Computational Learning Theory","author":"Kearns","key":"10.1016\/S0304-3975(00)00043-8_BIB18"},{"key":"10.1016\/S0304-3975(00)00043-8_BIB19","doi-asserted-by":"crossref","unstructured":"E. Kushilevitz, A simple algorithm for learning O(log n)-Term DNF, Proc. 9th Annual Conf. on Computational Learning Theory, 1996, pp. 266\u2013269.","DOI":"10.1145\/238061.238115"},{"key":"10.1016\/S0304-3975(00)00043-8_BIB20","doi-asserted-by":"crossref","first-page":"911","DOI":"10.1137\/0220056","article-title":"Learning simple concepts under simple distributions","volume":"20","author":"Li","year":"1991","journal-title":"SIAM J. Comput."},{"key":"10.1016\/S0304-3975(00)00043-8_BIB21","unstructured":"R. Lipton, The reachability problem requires exponential space, Research Report 62, Department of Computer Science, Yale University, New Haven, Connecticut, January 1976."},{"year":"1991","series-title":"Machine Learning: A Theoretical Approach","author":"Natarajan","key":"10.1016\/S0304-3975(00)00043-8_BIB22"},{"key":"10.1016\/S0304-3975(00)00043-8_BIB23","doi-asserted-by":"crossref","unstructured":"J.L. Peterson, Petri nets, Comput. Surveys 9(3) (1977) 223\u2013252.","DOI":"10.1145\/356698.356702"},{"issue":"4","key":"10.1016\/S0304-3975(00)00043-8_BIB24","doi-asserted-by":"crossref","first-page":"965","DOI":"10.1145\/48014.63140","article-title":"Computational limitations on learning from examples","volume":"35","author":"Pitt","year":"1988","journal-title":"J. Assoc. Comput. Mach."},{"key":"10.1016\/S0304-3975(00)00043-8_BIB25","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1007\/BF00058680","article-title":"Learning decision lists","volume":"2","author":"Rivest","year":"1987","journal-title":"Mach. Learning"},{"key":"10.1016\/S0304-3975(00)00043-8_BIB26","doi-asserted-by":"crossref","unstructured":"H.U. Simon, Learning decision lists and trees with equivalence queries, Proc. 2nd European Conf. EUROCOLT, 1995, pp. 322\u2013336.","DOI":"10.1007\/3-540-59119-2_188"},{"key":"10.1016\/S0304-3975(00)00043-8_BIB27","unstructured":"E. Takimoto, Y. Sakai, A. Maruoka, Learnability of Exclusive- Or Expansion Based on Monotone DNF Formulas, Proc. 7th Internat. Workshop on Algorithmic Learning Theory (ALT\u201996), Lecture Notes on Artificial Intelligence, Springer, Berlin, Vol. 1160, 1996, pp. 12\u201325."},{"issue":"11","key":"10.1016\/S0304-3975(00)00043-8_BIB28","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":"Commun. ACM"},{"key":"10.1016\/S0304-3975(00)00043-8_BIB29","doi-asserted-by":"crossref","unstructured":"O. Watanabe, A Formal Study of Learning via Queries, Proc. 17th Internat. Colloquium on Automata, Languages and Programming, Lecture Notes in Computer Science, Vol. 443, Springer, Berlin, 1990, pp. 139\u2013152.","DOI":"10.1007\/BFb0032028"},{"year":"1987","series-title":"The Complexity of Boolean Functions","author":"Wegener","key":"10.1016\/S0304-3975(00)00043-8_BIB30"}],"container-title":["Theoretical Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0304397500000438?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0304397500000438?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2024,12,3]],"date-time":"2024-12-03T17:33:32Z","timestamp":1733247212000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0304397500000438"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001,5]]},"references-count":30,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2001,5]]}},"alternative-id":["S0304397500000438"],"URL":"https:\/\/doi.org\/10.1016\/s0304-3975(00)00043-8","relation":{},"ISSN":["0304-3975"],"issn-type":[{"type":"print","value":"0304-3975"}],"subject":[],"published":{"date-parts":[[2001,5]]}}}