{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,12,21]],"date-time":"2023-12-21T19:38:15Z","timestamp":1703187495971},"reference-count":29,"publisher":"Springer Science and Business Media LLC","issue":"1-3","license":[{"start":{"date-parts":[[2006,5,8]],"date-time":"2006-05-08T00:00:00Z","timestamp":1147046400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Mach Learn"],"published-print":{"date-parts":[[2006,9]]},"DOI":"10.1007\/s10994-006-8261-3","type":"journal-article","created":{"date-parts":[[2006,5,8]],"date-time":"2006-05-08T16:44:52Z","timestamp":1147106692000},"page":"121-144","source":"Crossref","is-referenced-by-count":5,"title":["Complexity parameters for first order classes"],"prefix":"10.1007","volume":"64","author":[{"given":"Marta","family":"Arias","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Roni","family":"Khardon","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2006,5,8]]},"reference":[{"issue":"4","key":"8261_CR1","first-page":"319","volume":"2","author":"D. Angluin","year":"1988","unstructured":"Angluin, D. (1988). Queries and Concept Learning. Machine Learning, 2(4), 319\u2013342.","journal-title":"Machine Learning"},{"key":"8261_CR2","doi-asserted-by":"crossref","first-page":"214","DOI":"10.1016\/S0890-5401(02)93162-7","volume":"178","author":"M. Arias","year":"2002","unstructured":"Arias, M., & Khardon, R. (2002). Learning Closed Horn Expressions. Information and Computation, 178, 214\u2013240.","journal-title":"Information and Computation"},{"key":"8261_CR3","doi-asserted-by":"crossref","unstructured":"Arias, M., Khardon, R., & Servedio, R. A. (2003). Polynomial Certificates for Propositional Classes. In: Proceedings of the Conference on Computational Learning Theory (pp. 537\u2013551). Springer-Verlag.","DOI":"10.1007\/978-3-540-45167-9_39"},{"key":"8261_CR4","doi-asserted-by":"crossref","unstructured":"Arimura, H. (1997). Learning Acyclic First-order Horn Sentences from Entailment. In: Proceedings of the International Conference on Algorithmic Learning Theory. Springer-Verlag.","DOI":"10.1007\/3-540-63577-7_59"},{"issue":"4","key":"8261_CR5","doi-asserted-by":"crossref","first-page":"929","DOI":"10.1145\/76359.76371","volume":"36","author":"A. Blumer","year":"1989","unstructured":"Blumer, A., Ehrenfeucht, A., Haussler, D., & Warmuth, M. K. (1989). Learnability and the Vapnik-Chervonenkis dimension. Journal of the ACM, 36(4), 929\u2013965.","journal-title":"Journal of the ACM"},{"key":"8261_CR6","doi-asserted-by":"crossref","unstructured":"Cohen, W. (1995). PAC-learning recursive logic programs: Efficient algorithms. Journal of Artificial Intelligence Research, 2.","DOI":"10.1613\/jair.97"},{"issue":"1","key":"8261_CR7","doi-asserted-by":"crossref","first-page":"187","DOI":"10.1016\/S0004-3702(97)00041-6","volume":"95","author":"L. Raedt De","year":"1997","unstructured":"De Raedt, L. (1997). Logical Settings for Concept Learning. Artificial Intelligence, 95(1), 187\u2013201.","journal-title":"Artificial Intelligence"},{"key":"8261_CR8","doi-asserted-by":"crossref","unstructured":"De Raedt, L., & D\u017eeroski, S. (1994). First order jk-clausal theories are PAC-learnable. Artificial Intelligence, 70.","DOI":"10.1016\/0004-3702(94)90112-0"},{"key":"8261_CR9","first-page":"128","volume-title":"Proceedings of the Conference on Computational Learning Theory","author":"S. D\u017eeroski","year":"1992","unstructured":"D\u017eeroski, S., Muggleton, S., & Russell, S. (1992). PAC-learnability of Determinate Logic Programs. In: D. Haussler (Ed.) Proceedings of the Conference on Computational Learning Theory. (pp. 128\u2013135). Pittsburgh, PA: ACM Press."},{"key":"8261_CR10","doi-asserted-by":"crossref","unstructured":"Ehrenfeucht, A., Haussler, D., Kearns, M., & Valiant, L. (1989). A General Lower Bound on the Number of Examples Needed for Learning. Information and Computation, 82(3).","DOI":"10.1016\/0890-5401(89)90002-3"},{"key":"8261_CR11","first-page":"120","volume-title":"Proceedings of the International Conference on Machine Learning","author":"M. Frazier","year":"1993","unstructured":"Frazier, M., & Pitt, L. (1993). Learning from entailment: An application to propositional horn sentences\u2019. In: Proceedings of the International Conference on Machine Learning. (pp. 120\u2013127). Amherst, MA: Morgan Kaufmann."},{"issue":"2","key":"8261_CR12","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1016\/0020-0190(87)90103-7","volume":"24","author":"G. Gottlob","year":"1987","unstructured":"Gottlob, G. (1987). Subsumption and implication. Information Processing Letters, 24(2), 109\u2013111.","journal-title":"Information Processing Letters"},{"key":"8261_CR13","doi-asserted-by":"crossref","unstructured":"Grohe, M., & Tur\u00e1n, G. (2002). Learnability and Definability in Trees and Similar Structures. In: Proceedings of the 19th Annual Symposium on Theoretical Aspects of Computer Science (STACS) (pp. 645\u2013658). Springer-Verlag. LNCS 2285.","DOI":"10.1007\/3-540-45841-7_53"},{"key":"8261_CR14","first-page":"108","volume-title":"Proceedings of the Conference on Computational Learning Theory","author":"T. Heged\u0171s","year":"1995","unstructured":"Heged\u0171s, T. (1995) On Generalized Teaching Dimensions and the query complexity of learning. In: Proceedings of the Conference on Computational Learning Theory. (pp. 108\u2013117). New York, NY, USA: ACM Press."},{"issue":"5","key":"8261_CR15","doi-asserted-by":"crossref","first-page":"840","DOI":"10.1145\/234752.234755","volume":"43","author":"L. Hellerstein","year":"1996","unstructured":"Hellerstein, L., Pillaipakkamnatt, K., Raghavan, V., & Wilkins, D. (1996). How Many Queries are Needed to Learn? Journal of the ACM, 43(5), 840\u2013862.","journal-title":"Journal of the ACM"},{"issue":"1\u20132","key":"8261_CR16","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1016\/S0004-3702(01)00062-5","volume":"128","author":"T. Horv\u00e1th","year":"2001","unstructured":"Horv\u00e1th, T., & Tur\u00e1n, G. (2001). Learning logic programs with structured background knowledge. Artificial Intelligence, 128(1\u20132), 31\u201397.","journal-title":"Artificial Intelligence"},{"key":"8261_CR17","doi-asserted-by":"crossref","DOI":"10.7551\/mitpress\/3897.001.0001","volume-title":"An Introduction to computational learning theory","author":"M. Kearns","year":"1994","unstructured":"Kearns, M., & Vazirani, U. (1994). An Introduction to computational learning theory. Cambridge: MIT Press."},{"key":"8261_CR18","doi-asserted-by":"crossref","unstructured":"Khardon, R. (1999a). Learning Function Free Horn Expressions. Machine Learning, 37.","DOI":"10.1023\/A:1007610422992"},{"key":"8261_CR19","doi-asserted-by":"crossref","unstructured":"Khardon, R. (1999b). Learning Range Restricted Horn Expressions. In: Proceedings of the Fourth European Conference on Computational Learning Theory (pp. 111\u2013125), Springer-Verlag.","DOI":"10.1007\/3-540-49097-3_10"},{"issue":"1","key":"8261_CR20","doi-asserted-by":"crossref","first-page":"22","DOI":"10.1145\/181668.181674","volume":"5","author":"J. U. Kietz","year":"1994","unstructured":"Kietz, J. U., & D\u017eeroski, S. (1994). Inductive logic programming and learnability. SIGART Bulletin, 5(1), 22\u201332.","journal-title":"SIGART Bulletin"},{"key":"8261_CR21","unstructured":"Krishna Rao, M., & Sattar, A. (1998). Learning from entailment of logic programs with local variables. In: Proceedings of the International Conference on Algorithmic Learning Theory. Springer-Verlag."},{"key":"8261_CR22","unstructured":"Lloyd, J. W. (1987). Foundations of logic programming; (2nd extended ed.). Springer-Verlag."},{"key":"8261_CR23","first-page":"107","volume":"9","author":"W. Maass","year":"1992","unstructured":"Maass, W., & Tur\u00e1n, G. (1992). Lower bound methods and separation results for online learning models. Machine Learning, 9, 107\u2013145.","journal-title":"Machine Learning"},{"key":"8261_CR24","unstructured":"Maass, W., & Tur\u00e1n, G. (1995). On learnability and predicate logic (extended abstract). In: Proceedings of the 4th Bar-Ilan Symposium on Foundations of AI (BISFAI)."},{"key":"8261_CR25","doi-asserted-by":"crossref","unstructured":"Muggleton, S., & De Raedt, L. (1994). Inductive Logic Programming: Theory and methods. The Journal of Logic Programming, 19 & 20, 629\u2013680.","DOI":"10.1016\/0743-1066(94)90035-3"},{"key":"8261_CR26","unstructured":"Muggleton, S., & Feng, C. (1992). Efficient Induction of Logic Programs. In: S. Muggleton (Ed.) Inductive Logic Programming. (pp. 281\u2013298) Academic Press."},{"key":"8261_CR27","doi-asserted-by":"crossref","first-page":"243","DOI":"10.1007\/3540635149_53","volume-title":"International Workshop on Inductive Logic Programming","author":"C. Reddy","year":"1997","unstructured":"Reddy, C., & Tadepalli, P. (1997). Learning Horn Definitions with Equivalence and Membership Queries. In: International Workshop on Inductive Logic Programming. (pp. 243\u2013255). Prague, Czech Republic: Springer-Verlag."},{"key":"8261_CR28","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1007\/BFb0027308","volume-title":"International Conference on Inductive Logic Programming","author":"C. Reddy","year":"1998","unstructured":"Reddy, C., & Tadepalli, P. (1998). Learning First Order Acyclic Horn Programs from Entailment. In: International Conference on Inductive Logic Programming. (pp. 23\u201337), Madison, WI: Springer-Verlag."},{"issue":"2","key":"8261_CR29","doi-asserted-by":"crossref","first-page":"264","DOI":"10.1137\/1116025","volume":"16","author":"V. Vapnik","year":"1971","unstructured":"Vapnik, V., & Chervonenkis, A. (1971). On the Uniform Convergence of Relative Frequencies of Events to their probabilities. Theory of Probability and its Applications, 16(2), 264\u2013280.","journal-title":"Theory of Probability and its Applications"}],"container-title":["Machine Learning"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10994-006-8261-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10994-006-8261-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10994-006-8261-3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,1]],"date-time":"2019-06-01T01:40:21Z","timestamp":1559353221000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10994-006-8261-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,5,8]]},"references-count":29,"journal-issue":{"issue":"1-3","published-print":{"date-parts":[[2006,9]]}},"alternative-id":["8261"],"URL":"https:\/\/doi.org\/10.1007\/s10994-006-8261-3","relation":{},"ISSN":["0885-6125","1573-0565"],"issn-type":[{"value":"0885-6125","type":"print"},{"value":"1573-0565","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006,5,8]]}}}