{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T18:15:43Z","timestamp":1725560143130},"publisher-location":"Berlin, Heidelberg","reference-count":26,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540407201"},{"type":"electronic","value":"9783540451679"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2003]]},"DOI":"10.1007\/978-3-540-45167-9_39","type":"book-chapter","created":{"date-parts":[[2010,7,22]],"date-time":"2010-07-22T23:10:53Z","timestamp":1279840253000},"page":"537-551","source":"Crossref","is-referenced-by-count":4,"title":["Polynomial Certificates for Propositional Classes"],"prefix":"10.1007","author":[{"given":"Marta","family":"Arias","sequence":"first","affiliation":[]},{"given":"Roni","family":"Khardon","sequence":"additional","affiliation":[]},{"given":"Rocco A.","family":"Servedio","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"4","key":"39_CR1","first-page":"319","volume":"2","author":"D. Angluin","year":"1988","unstructured":"Angluin, D.: Queries and concept learning. Machine Learning\u00a02(4), 319\u2013342 (1988)","journal-title":"Machine Learning"},{"key":"39_CR2","first-page":"147","volume":"9","author":"D. Angluin","year":"1992","unstructured":"Angluin, D., Frazier, M., Pitt, L.: Learning conjunctions of Horn clauses. Machine Learning\u00a09, 147\u2013164 (1992)","journal-title":"Machine Learning"},{"key":"39_CR3","series-title":"Lecture Notes in Artificial Intelligence","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1007\/3-540-45583-3_3","volume-title":"Algorithmic Learning Theory","author":"D. Angluin","year":"2001","unstructured":"Angluin, D.: Queries revisited. In: Abe, N., Khardon, R., Zeugmann, T. (eds.) ALT 2001. LNCS (LNAI), vol.\u00a02225, pp. 12\u201331. Springer, Heidelberg (2001)"},{"key":"39_CR4","doi-asserted-by":"crossref","unstructured":"Arias, M., Khardon, R.: Learning closed horn expressions. Information and Computation, 214\u2013240 (2002)","DOI":"10.1016\/S0890-5401(02)93162-7"},{"key":"39_CR5","doi-asserted-by":"crossref","unstructured":"Arimura, H.: Learning acyclic first-order Horn sentences from entailment. In: Li, M. (ed.) ALT 1997. LNCS(LNAI), vol.\u00a01316. Springer, Heidelberg (1997)","DOI":"10.1007\/3-540-63577-7_59"},{"key":"39_CR6","doi-asserted-by":"crossref","unstructured":"Balc\u00e1zar, J.L., Castro, J., Guijarro, D.: The consistency dimension and distribution-dependent learning from queries. In: Nadathur, G. (ed.) PPDP 1999. LNCS(LNAI), vol.\u00a01702. Springer, Heidelberg (1999)","DOI":"10.1007\/3-540-46769-6_7"},{"key":"39_CR7","doi-asserted-by":"crossref","unstructured":"Bshouty, N.H.: Simple learning algorithms using divide and conquer. In: Proceedings of the Conference on COLT (1995)","DOI":"10.1145\/225298.225352"},{"issue":"1","key":"39_CR8","doi-asserted-by":"crossref","first-page":"187","DOI":"10.1016\/S0004-3702(97)00041-6","volume":"95","author":"L. Raedt","year":"1997","unstructured":"De Raedt, L.: Logical settings for concept learning. Artificial Intelligence\u00a095(1), 187\u2013201 (1997), . See also relevant Errata (forthcoming)","journal-title":"Artificial Intelligence"},{"key":"39_CR9","unstructured":"Feigelson, A.: On boolean functions and their orientations: Learning, monotone dimension and certificates. Ph.D. Thesis, Northwestern University, Department of Electrical and Computer Engineering (1998)"},{"issue":"2","key":"39_CR10","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1006\/inco.1997.2684","volume":"140","author":"A. Feigelson","year":"1988","unstructured":"Feigelson, A., Hellerstein, L.: Conjunctions of unate DNF formulas: Learning and structure. Information and Computation\u00a0140(2), 203\u2013228 (1988)","journal-title":"Information and Computation"},{"key":"39_CR11","first-page":"120","volume-title":"Proceedings of the International Conference on Machine Learning","author":"M. Frazier","year":"1993","unstructured":"Frazier, M., Pitt, L.: Learning from entailment: An application to propositional Horn sentences. In: Proceedings of the International Conference on Machine Learning, Amherst, MA, pp. 120\u2013127. Morgan Kaufmann, San Francisco (1993)"},{"key":"39_CR12","doi-asserted-by":"publisher","first-page":"108","DOI":"10.1145\/225298.225311","volume-title":"Proceedings of the 8th Annual Conference on Computational Learning Theory (COLT 1995)","author":"T. Hegedus","year":"1995","unstructured":"Hegedus, T.: On generalized teaching dimensions and the query complexity of learning. In: Proceedings of the 8th Annual Conference on Computational Learning Theory (COLT 1995), New York, NY, USA, pp. 108\u2013117. ACM Press, New York (1995)"},{"key":"39_CR13","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1016\/S0012-365X(00)00166-7","volume":"226","author":"L. Hellerstein","year":"2001","unstructured":"Hellerstein, L.: On generalized constraints and certificates. Discrete Mathematics\u00a0226, 211\u2013232 (2001)","journal-title":"Discrete Mathematics"},{"issue":"5","key":"39_CR14","doi-asserted-by":"publisher","first-page":"840","DOI":"10.1145\/234752.234755","volume":"43","author":"L. Hellerstein","year":"1996","unstructured":"Hellerstein, L., Pillaipakkamnatt, K., Raghavan, V., Wilkins, D.: How many queries are needed to learn? Journal of the ACM\u00a043(5), 840\u2013862 (1996)","journal-title":"Journal of the ACM"},{"key":"39_CR15","doi-asserted-by":"crossref","unstructured":"Hellerstein, L., Raghavan, V.: Exact learning of DNF formulas using DNF hypotheses. In: Proceedings of the 34th Annual ACM Symposium on Theory of Computing (STOC 2002), New York, May 19\u201321, pp. 465\u2013473. ACM Press, New York (2002)","DOI":"10.1145\/509907.509976"},{"key":"39_CR16","doi-asserted-by":"crossref","first-page":"14","DOI":"10.2307\/2268661","volume":"16","author":"A. Horn","year":"1956","unstructured":"Horn, A.: On sentences which are true of direct unions of algebras. Journal of Symbolic Logic\u00a016, 14\u201321 (1956)","journal-title":"Journal of Symbolic Logic"},{"key":"39_CR17","doi-asserted-by":"publisher","first-page":"241","DOI":"10.1023\/A:1007610422992","volume":"37","author":"R. Khardon","year":"1999","unstructured":"Khardon, R.: Learning function free Horn expressions. Machine Learning\u00a037, 241\u2013275 (1999)","journal-title":"Machine Learning"},{"issue":"2","key":"39_CR18","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1023\/A:1007581123604","volume":"35","author":"R. Khardon","year":"1999","unstructured":"Khardon, R., Roth, D.: Learning to reason with a restricted view. Machine Learning\u00a035(2), 95\u2013117 (1999)","journal-title":"Machine Learning"},{"issue":"1\u2013 2","key":"39_CR19","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1016\/S0004-3702(96)00006-9","volume":"87","author":"R. Khardon","year":"1996","unstructured":"Khardon, R., Roth, D.: Reasoning with models. Artificial Intelligence\u00a087(1\u2013 2), 187\u2013213 (1996)","journal-title":"Artificial Intelligence"},{"key":"39_CR20","first-page":"285","volume":"2","author":"N. Littlestone","year":"1988","unstructured":"Littlestone, N.: Learning quickly when irrelevant attributes abound: A new linearthreshold algorithm. Machine Learning\u00a02, 285\u2013318 (1988)","journal-title":"Machine Learning"},{"key":"39_CR21","first-page":"107","volume":"9","author":"W. Maass","year":"1992","unstructured":"Maass, W., Tur\u00e1n, G.: Lower bound methods and separation results for on-line learning models. Machine Learning\u00a09, 107\u2013145 (1992)","journal-title":"Machine Learning"},{"key":"39_CR22","doi-asserted-by":"publisher","first-page":"61","DOI":"10.2307\/2268172","volume":"8","author":"J.C.C. McKinsey","year":"1943","unstructured":"McKinsey, J.C.C.: The decision problem for some classes of sentences without quantifiers. J. Symbolic Logic\u00a08, 61\u201376 (1943)","journal-title":"J. Symbolic Logic"},{"key":"39_CR23","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1023\/A:1026455409889","volume":"25","author":"K. Pillaipakkamnatt","year":"1996","unstructured":"Pillaipakkamnatt, K., Raghavan, V.: On the limits of proper learnability of subclasses of DNF formulas. Machine Learning\u00a025, 237 (1996)","journal-title":"Machine Learning"},{"key":"39_CR24","series-title":"LNAI","doi-asserted-by":"crossref","first-page":"243","DOI":"10.1007\/3540635149_53","volume-title":"Inductive Logic Programming","author":"C. Reddy","year":"1997","unstructured":"Reddy, C., Tadepalli, P.: Learning Horn definitions with equivalence and membership queries. In: D\u017eeroski, S., Lavra\u010d, N. (eds.) ILP 1997. LNCS (LNAI), vol.\u00a01297, pp. 243\u2013255. Springer, Heidelberg (1997)"},{"key":"39_CR25","series-title":"LNAI","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1007\/BFb0027308","volume-title":"Inductive Logic Programming","author":"C. Reddy","year":"1998","unstructured":"Reddy, C., Tadepalli, P.: Learning first order acyclic Horn programs from entailment. In: Page, D.L. (ed.) ILP 1998. LNCS (LNAI), vol.\u00a01446, pp. 23\u201337. Springer, Heidelberg (1998)"},{"issue":"11","key":"39_CR26","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"}],"container-title":["Lecture Notes in Computer Science","Learning Theory and Kernel Machines"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-45167-9_39","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,31]],"date-time":"2019-05-31T12:59:00Z","timestamp":1559307540000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-45167-9_39"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003]]},"ISBN":["9783540407201","9783540451679"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-45167-9_39","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2003]]}}}