{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T17:47:27Z","timestamp":1725558447250},"publisher-location":"Berlin, Heidelberg","reference-count":25,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540201441"},{"type":"electronic","value":"9783540399179"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2003]]},"DOI":"10.1007\/978-3-540-39917-9_4","type":"book-chapter","created":{"date-parts":[[2010,6,28]],"date-time":"2010-06-28T00:02:15Z","timestamp":1277683335000},"page":"22-37","source":"Crossref","is-referenced-by-count":2,"title":["Complexity Parameters for First-Order Classes"],"prefix":"10.1007","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","reference":[{"issue":"4","key":"4_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":"4_CR2","doi-asserted-by":"crossref","unstructured":"Arias, M., Khardon, R.: Learning closed horn expressions. Information and Computation, 214\u2013240 (2002)","DOI":"10.1006\/inco.2002.3162"},{"key":"4_CR3","doi-asserted-by":"crossref","unstructured":"Arias, M., Khardon, R., Servedio, R.A.: Polynomial certificates for propositional classes. In: Proceedings of the Conference on Computational Learning Theory (2003)","DOI":"10.1007\/978-3-540-45167-9_39"},{"key":"4_CR4","series-title":"LNAI","volume-title":"Algorithmic Learning Theory","author":"H. Arimura","year":"1997","unstructured":"Arimura, H.: Learning acyclic first-order Horn sentences from entailment. In: Li, M. (ed.) ALT 1997. LNCS (LNAI), vol.\u00a01316, Springer, Heidelberg (1997)"},{"issue":"4","key":"4_CR5","doi-asserted-by":"publisher","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.: Learnability and the Vapnik-Chervonenkis dimension. Journal of the ACM\u00a036(4), 929\u2013965 (1989)","journal-title":"Journal of the ACM"},{"key":"4_CR6","doi-asserted-by":"crossref","first-page":"501","DOI":"10.1613\/jair.97","volume":"2","author":"W. Cohen","year":"1995","unstructured":"Cohen, W.: PAC-learning recursive logic programs: Efficient algorithms. Journal of Artificial Intelligence Research\u00a02, 501\u2013539 (1995)","journal-title":"Journal of Artificial Intelligence Research"},{"key":"4_CR7","doi-asserted-by":"publisher","first-page":"375","DOI":"10.1016\/0004-3702(94)90112-0","volume":"70","author":"L. Raedt De","year":"1994","unstructured":"De Raedt, L., Dzeroski, S.: First order jk-clausal theories are PAC-learnable. Artificial Intelligence\u00a070, 375\u2013392 (1994)","journal-title":"Artificial Intelligence"},{"key":"4_CR8","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.: PAC-learnability of determinate logic programs. In: Haussler, D. (ed.) Proceedings of the Conference on Computational Learning Theory, Pittsburgh, PA, pp. 128\u2013135. ACM Press, New York (1992)"},{"issue":"3","key":"4_CR9","doi-asserted-by":"publisher","first-page":"247","DOI":"10.1016\/0890-5401(89)90002-3","volume":"82","author":"A. Ehrenfeucht","year":"1989","unstructured":"Ehrenfeucht, A., Haussler, D., Kearns, M., Valiant, L.: A general lower bound on the number of examples needed for learning. Information and Computation\u00a082(3), 247\u2013251 (1989)","journal-title":"Information and Computation"},{"key":"4_CR10","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 prepositional Horn sentences. In: Proceedings of the International Conference on Machine Learning, Amherst, MA, pp. 120\u2013127. Morgan Kaufmann, San Francisco (1993)"},{"key":"4_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"645","DOI":"10.1007\/3-540-45841-7_53","volume-title":"STACS 2002","author":"M. Grohe","year":"2002","unstructured":"Grohe, M., Tur\u00e1n, G.: Learnability and definability in trees and similar structures. In: Alt, H., Ferreira, A. (eds.) STACS 2002. LNCS, vol.\u00a02285, pp. 645\u2013658. Springer, Heidelberg (2002)"},{"key":"4_CR12","doi-asserted-by":"publisher","first-page":"108","DOI":"10.1145\/225298.225311","volume-title":"Proceedings of the Conference on Computational Learning Theory","author":"T. Hegedus","year":"1995","unstructured":"Hegedus, T.: On generalized teaching dimensions and the query complexity of learning. In: Proceedings of the Conference on Computational Learning Theory, pp. 108\u2013117. ACM Press, New York (1995)"},{"issue":"5","key":"4_CR13","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"},{"issue":"1-2","key":"4_CR14","doi-asserted-by":"publisher","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.: Learning logic programs with structured background knowledge. Artificial Intelligence\u00a0128(1-2), 31\u201397 (2001)","journal-title":"Artificial Intelligence"},{"key":"4_CR15","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"},{"key":"4_CR16","series-title":"Lecture Notes in Artificial Intelligence","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1007\/3-540-49097-3_10","volume-title":"Computational Learning Theory","author":"R. Khardon","year":"1999","unstructured":"Khardon, R.: Learning range restricted Horn expressions. In: Fischer, P., Simon, H.U. (eds.) EuroCOLT 1999. LNCS (LNAI), vol.\u00a01572, pp. 111\u2013125. Springer, Heidelberg (1999)"},{"issue":"1","key":"4_CR17","doi-asserted-by":"publisher","first-page":"22","DOI":"10.1145\/181668.181674","volume":"5","author":"J.-U. Kietz","year":"1994","unstructured":"Kietz, J.-U., Dzeroski, S.: Inductive logic programming and learnability. SIGART Bulletin\u00a05(1), 22\u201332 (1994)","journal-title":"SIGART Bulletin"},{"key":"4_CR18","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-83189-8","volume-title":"Foundations of Logic Programming","author":"J.W. Lloyd","year":"1987","unstructured":"Lloyd, J.W.: Foundations of Logic Programming. Springer, Heidelberg (1987)"},{"key":"4_CR19","unstructured":"Maass, W., Turan, G.: On learnability and predicate logic (extended abstract). In: Proceedings of the 4th Bar-Ilan Symposium on Foundations of AI, BISFAI (1995)"},{"key":"4_CR20","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":"4_CR21","first-page":"281","volume-title":"Inductive Logic Programming","author":"S. Muggleton","year":"1992","unstructured":"Muggleton, S., Feng, C.: Efficient induction of logic programs. In: Muggleton, S. (ed.) Inductive Logic Programming, pp. 281\u2013298. Academic Press, London (1992)"},{"key":"4_CR22","doi-asserted-by":"publisher","first-page":"629","DOI":"10.1016\/0743-1066(94)90035-3","volume":"19 and 20","author":"S. Muggleton","year":"1994","unstructured":"Muggleton, S., De Raedt, L.: Inductive logic programming: Theory and methods. The Journal of Logic Programming\u00a019 and 20, 629\u2013680 (1994)","journal-title":"The Journal of Logic Programming"},{"key":"4_CR23","series-title":"Lecture Notes in Artificial Intelligence","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1007\/3-540-49730-7_11","volume-title":"Algorithmic Learning Theory","author":"K. Rao","year":"1998","unstructured":"Rao, K., Sattar, A.: Learning from entailment of logic programs with local variables. In: Richter, M.M., Smith, C.H., Wiehagen, R., Zeugmann, T. (eds.) ALT 1998. LNCS (LNAI), vol.\u00a01501, pp. 143\u2013157. Springer, Heidelberg (1998)"},{"key":"4_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":"4_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)"}],"container-title":["Lecture Notes in Computer Science","Inductive Logic Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-39917-9_4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,30]],"date-time":"2019-05-30T09:34:22Z","timestamp":1559208862000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-39917-9_4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003]]},"ISBN":["9783540201441","9783540399179"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-39917-9_4","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2003]]}}}