{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,18]],"date-time":"2026-01-18T09:24:51Z","timestamp":1768728291328,"version":"3.49.0"},"reference-count":52,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2000,11,1]],"date-time":"2000-11-01T00:00:00Z","timestamp":973036800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2000,11,1]],"date-time":"2000-11-01T00:00:00Z","timestamp":973036800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Machine Learning"],"published-print":{"date-parts":[[2000,11]]},"DOI":"10.1023\/a:1007620705405","type":"journal-article","created":{"date-parts":[[2002,12,22]],"date-time":"2002-12-22T05:54:50Z","timestamp":1040536490000},"page":"217-251","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":36,"title":["Phase Transitions in Relational Learning"],"prefix":"10.1007","volume":"41","author":[{"given":"Attilio","family":"Giordana","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lorenza","family":"Saitta","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"274349_CR1","first-page":"119","volume":"20","author":"H. Ade","year":"1995","unstructured":"Ade, H., Raedt, L. D., & Bruynooghe, M. (1995). Declarative bias for specific-to-general ILP systems. Machine Learning, 20, 119\u2013154.","journal-title":"Machine Learning"},{"key":"274349_CR2","first-page":"434","volume-title":"Proceedings of the 7th International Conference on Genetic Algorithms","author":"C. Anglano","year":"1997","unstructured":"Anglano, C., Giordana, A., Lo Bello, G., & Saitta, L. (1997). A network genetic algorithm for concept learning. In Proceedings of the 7th International Conference on Genetic Algorithms (pp. 434\u2013441). MI: East Lansing."},{"key":"274349_CR3","unstructured":"Anglano, C., Giordana, A., Lo Bello, G., & Saitta, L. (1998). An experimental evaluation of coevolutive concept learning. In Proceedings of the 15th International Conference on Machine Learning (pp. 19\u201323). Madison, WI."},{"key":"274349_CR4","unstructured":"Bacchus, F. & van Beek, P. (1998). On the conversion between non-binary and binary constraint satisfaction problems. In Proceedings of the 15th National Conference on Artificial Intelligence (pp. 311\u2013318). Madison, WI."},{"key":"274349_CR5","first-page":"386","volume-title":"Proceedings of the 15th National Conference on Artificial Intelligence","author":"O. Bailleux","year":"1998","unstructured":"Bailleux, O. (1998). Local search for statistical counting. In Proceedings of the 15th National Conference on Artificial Intelligence (pp. 386\u2013391). Madison, WI: Morgan Kaufman."},{"key":"274349_CR6","first-page":"169","volume-title":"Proceedings of the 13th National Conference on Artificial Intelligence","author":"O. Bailleux","year":"1996","unstructured":"Bailleux, O. & Chabrier, J.-J. (1996). Approximate resolution of hard numbering problems. In Proceedings of the 13th National Conference on Artificial Intelligence (pp. 169\u2013174). Portland, Oregon: AAAI-Press."},{"key":"274349_CR7","unstructured":"Bayardo, R. & Schrag, R. (1997). Using CSP look-back techniques to solve real-world SAT instances. In Proceedings of the 14th National Conference on Artificial Intelligence (pp. 203\u2013208). Providence, RI."},{"key":"274349_CR8","doi-asserted-by":"crossref","unstructured":"Bergadano, F. Giordana, A., & Saitta, L. (1988). Learning concepts in noisy environment. IEEE Transaction on Pattern Analysis and Machine Intelligence, PAMI-10, 555\u2013578.","DOI":"10.1109\/34.3917"},{"key":"274349_CR9","unstructured":"Botta, M. Giordana, A., & Saitta, L. (1999). Relational learning: Hard problems and phase transitions. In Proceedings of the 16th International Joint Conference on Artificial Intelligence (pp. 1198\u20131203). Stockholm, Sweden."},{"key":"274349_CR10","volume-title":"Algorithmics: Theory and Practice","author":"G. Brassard","year":"1988","unstructured":"Brassard, G. & Bratley, P. (1988). Algorithmics: Theory and Practice. NJ: Prentice Hall, Englewood Cliffs."},{"key":"274349_CR11","unstructured":"Cheeseman, P., Kanefsky, B., & Taylor, W. (1991). Where the really hard problems are. In Proceedings 12th International Joint Conference on Artificial Intelligence (pp. 331\u2013337). Sidney, Australia."},{"key":"274349_CR12","unstructured":"Cohen, W. (1993). A PAC-learning algorithm for a restricted class of recursive logic programs. In Proceedings of the 10th National Conference on Artificial Intelligence (pp. 86\u201392). Washington, DC."},{"key":"274349_CR13","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1016\/0004-3702(95)00046-1","volume":"81","author":"J. Crawford","year":"1996","unstructured":"Crawford, J. & Auton, L. (1996). Experimental results on the crossover point in random 3-SAT. Artificial Intelligence, 81, 31\u201358.","journal-title":"Artificial Intelligence"},{"key":"274349_CR14","doi-asserted-by":"crossref","first-page":"375","DOI":"10.1016\/0004-3702(94)90112-0","volume":"70","author":"L. De Raedt","year":"1994","unstructured":"De Raedt, L. & D\u017eeroski, S. (1994). First-order jk-clausal theories are PAC-learnable. Artificial Intelligence, 70, 375\u2013392.","journal-title":"Artificial Intelligence"},{"key":"274349_CR15","unstructured":"desJardins, M. & Gordon, D. (Eds.). (1995). Machine Learning: Special Issue on Bias Evaluation and Selection (Vol. 20). Kluwer Academic."},{"key":"274349_CR16","doi-asserted-by":"crossref","unstructured":"D\u017eeroski, S., Muggleton, S., & Russell, S. (1992). PAC-learnability of determinate logic programs. In Proceedings of COLT-92 (pp. 128\u2013134). Pittsburgh, PA.","DOI":"10.1145\/130385.130399"},{"key":"274349_CR17","doi-asserted-by":"crossref","first-page":"183","DOI":"10.1016\/0004-3702(95)00051-8","volume":"81","author":"J. Freeman","year":"1996","unstructured":"Freeman, J. (1996). Hard random 3-SAT problems and the Davis-Putnam procedure. Artificial Intelligence, 81, 183\u2013198.","journal-title":"Artificial Intelligence"},{"key":"274349_CR18","unstructured":"Frost, D., Rish, I., & Vila, L. (1997). Summarizing CSP hardness with continuous probability distributions. In Proceedings of the 14th National Conference on Artificial Intelligence (pp. 327\u2013333). Providence, RI."},{"key":"274349_CR19","unstructured":"Gent, I. & Walsh, T. (1995). Phase transitions from real computational problems. In Proceedings of the 8th International Symposium on Artificial Intelligence (pp. 356\u2013364)."},{"key":"274349_CR20","doi-asserted-by":"crossref","first-page":"349","DOI":"10.1016\/S0004-3702(96)00030-6","volume":"88","author":"I. Gent","year":"1996","unstructured":"Gent, I. & Walsh, T. (1996). The TSP phase transition. Artificial Intelligence, 88, 349\u2013358.","journal-title":"Artificial Intelligence"},{"key":"274349_CR21","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1023\/A:1007361708126","volume":"27","author":"A. Giordana","year":"1997","unstructured":"Giordana, A., Neri, F., Saitta, L., & Botta, M. (1997). Integrating multiple learning strategies in first order logics. 1 Machine Learning, 27, 209\u2013240.","journal-title":"1 Machine Learning"},{"key":"274349_CR22","doi-asserted-by":"crossref","unstructured":"Giordana, A., Saitta, L., Bergadano, F., Brancadori, F., & De Marchi, D. (1993). ENIGMA: A system that learns diagnostic knowledge. IEEE Transactions on Knowledge and Data Engineering, KDE-5, 15\u201328.","DOI":"10.1109\/69.204088"},{"key":"274349_CR23","unstructured":"Giordana, A., Saitta, L., Sebag, M., & Botta, M. (2000). Analyzing relational learning in the phase transition framework. In Proceedings of the 17th International Conference on Machine Learning (pp. 311\u2013318), Stanford, CA."},{"key":"274349_CR24","unstructured":"Gomes, C. & Selman, B. (1997). Problem structure in the presence of perturbations. In Proceedings of the 14th National Conference on Artificial Intelligence (pp. 431\u2013437). Providence, RI."},{"key":"274349_CR25","unstructured":"Gomes, C., Selman, B., & Kautz, H. (1998). Boosting combinatorial search through randomizattion. In Proceedings of the 15th National Conference on Artificial Intelligence (pp. 431\u2013437). Madison, WI."},{"key":"274349_CR26","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1016\/0004-3702(95)00050-X","volume":"81","author":"T. Hogg","year":"1996","unstructured":"Hogg, T. (1996). Refining the phase transition in combinatorial search. Artificial Intelligence, 81, 127\u2013154.","journal-title":"Artificial Intelligence"},{"key":"274349_CR27","doi-asserted-by":"crossref","unstructured":"Hogg, T., Huberman, B., & Williams, C. (Eds.). (1996a). Artificial Intelligence: Special Issue on Frontiers in Problem Solving: Phase Transitions and Complexity (Vol. 81)(1\u20132). Elsevier.","DOI":"10.1016\/0004-3702(95)00044-5"},{"key":"274349_CR28","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0004-3702(95)00044-5","volume":"81","author":"T. Hogg","year":"1996","unstructured":"Hogg, T., Huberman, B., & Williams, C. (1996b). Phase transitions and the search problem. Artificial Intelligence, 81, 1\u201315.","journal-title":"Artificial Intelligence"},{"key":"274349_CR29","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1126\/science.275.5296.51","volume":"275","author":"B. Huberman","year":"1997","unstructured":"Huberman, B., Lukose, R., & Hogg, T. (1997). An economics approach to hard computational problems. Science, 275, 51\u201354.","journal-title":"Science"},{"key":"274349_CR30","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1016\/0020-0190(76)90095-8","volume":"5","author":"L. Hyafil","year":"1976","unstructured":"Hyafil, L. & Rivest, R. (1976). Constructing optimal binary decision trees is NP-complete. Information Processing Letters, 5, 15\u201317.","journal-title":"Information Processing Letters"},{"key":"274349_CR31","doi-asserted-by":"crossref","first-page":"22","DOI":"10.1145\/181668.181674","volume":"5","author":"J. Kietz","year":"1994","unstructured":"Kietz, J. & D\u017aeroski, S. (1994). Inductive logic programming and learnability. SIGART Bulletin, 5, 22\u201332.","journal-title":"SIGART Bulletin"},{"key":"274349_CR32","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1023\/A:1022626200450","volume":"14","author":"J. Kietz","year":"1994","unstructured":"Kietz, J. & Morik, K. (1994). A polynomial approach to the constructive induction of structural knowledge. Machine Learning, 14, 193\u2013218.","journal-title":"Machine Learning"},{"key":"274349_CR33","first-page":"107","volume-title":"Inductive Logic Programming","author":"J. Kietz","year":"1992","unstructured":"Kietz, J., & Wrobel, S. (1992). Controlling the complexity of learning through syntactic and task-oriented models. In Muggleton, S. (Ed.), Inductive Logic Programming (pp. 107\u2013126). Academic Press, London, UK."},{"key":"274349_CR34","doi-asserted-by":"crossref","first-page":"349","DOI":"10.1109\/TPAMI.1980.4767034","volume":"-2","author":"R. Michalski","year":"1980","unstructured":"Michalski, R. (1980). Pattern recognition as a rule-guided inductive inference. IEEE Transactions on Pattern Analysis and Machine Intelligence, PAMI-2, 349\u2013361.","journal-title":"IEEE Transactions on Pattern Analysis and Machine Intelligence, PAMI"},{"key":"274349_CR35","doi-asserted-by":"crossref","first-page":"203","DOI":"10.1016\/0004-3702(82)90040-6","volume":"18","author":"T. Mitchell","year":"1982","unstructured":"Mitchell, T. (1982). Generalization as search. Artificial Intelligence, 18, 203\u2013226.","journal-title":"Artificial Intelligence"},{"key":"274349_CR36","unstructured":"Morik, K. (1991). Balanced cooperative modeling. In Proceedings of the 1st Multistrategy Learning Workshop (pp. 65\u201380). Harpers Ferry, WV."},{"key":"274349_CR37","volume-title":"Inductive Logic Programming","year":"1992","unstructured":"Muggleton, S. (Ed.). (1992). Inductive Logic Programming. London, UK: Academic Press."},{"key":"274349_CR38","doi-asserted-by":"crossref","first-page":"245","DOI":"10.1007\/BF03037227","volume":"13","author":"S. Muggleton","year":"1995","unstructured":"Muggleton, S. (1995). Inverse entailment and Progol. New Generation Computing, 13, 245\u2013286.","journal-title":"New Generation Computing"},{"key":"274349_CR39","first-page":"299","volume":"1314","author":"U. Pompe","year":"1996","unstructured":"Pompe, U. (1996). Efficient proof encoding. Lecture Notes in Artificial Intelligence, 1314, 299\u2013314.","journal-title":"Lecture Notes in Artificial Intelligence"},{"key":"274349_CR40","doi-asserted-by":"crossref","first-page":"81","DOI":"10.1016\/0004-3702(95)00048-8","volume":"81","author":"P. Prosser","year":"1996","unstructured":"Prosser, P. (1996). An empirical study of phase transitions in binary constraint satisfaction problems. Artificial Intelligence, 81, 81\u2013110.","journal-title":"Artificial Intelligence"},{"key":"274349_CR41","first-page":"239","volume":"5","author":"R. Quinlan","year":"1990","unstructured":"Quinlan, R. (1990). Learning logical definitions from relations. Machine Learning, 5, 239\u2013266.","journal-title":"Machine Learning"},{"key":"274349_CR42","unstructured":"Sebag, M. & Rouveirol, C. (1997). Tractable induction and classification in first order logic via Stochastic Matching. In Proceedings of the 15th International Joint Conference on Artificial Intelligence (pp. 888\u2013893). Nagoya, Japan."},{"key":"274349_CR43","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1023\/A:1007629922420","volume":"38","author":"M. Sebag","year":"2000","unstructured":"Sebag, M. & Rouveirol, C. (2000). Stochastic relational inference: Sampling-based heuristics for any-time inductive and deductive reasoning. Machine Learning, 38, 41\u201362.","journal-title":"Machine Learning"},{"key":"274349_CR44","doi-asserted-by":"crossref","first-page":"273","DOI":"10.1016\/0004-3702(95)00056-9","volume":"81","author":"B. Selman","year":"1996","unstructured":"Selman, B. & Kirkpatrick, S. (1996). Critical behavior in the computational cost of satisfiability testing. Artificial Intelligence, 81, 273\u2013296.","journal-title":"Artificial Intelligence"},{"key":"274349_CR45","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1016\/0004-3702(95)00052-6","volume":"81","author":"B. Smith","year":"1996","unstructured":"Smith, B. & Dyer, M. (1996). Locating the phase transition in binary constraint satisfaction problems. Artificial Intelligence, 81, 155\u2013181.","journal-title":"Artificial Intelligence"},{"key":"274349_CR46","unstructured":"Srinivasan, A., Muggleton, S., & King, R. (1995). Comparing the use of background knowledge by two ILP systems. In Proceedings of the 5th International Workshop on ILP (pp. 199\u2013229). Leuven, Belgium."},{"key":"274349_CR47","doi-asserted-by":"crossref","first-page":"1134","DOI":"10.1145\/1968.1972","volume":"27","author":"L. Valiant","year":"1984","unstructured":"Valiant, L. (1984). A theory of the learnable. Communications of the ACM, 27, 1134\u20131142.","journal-title":"Communications of the ACM"},{"key":"274349_CR48","unstructured":"Walsh, T. (1998). The constrainedness knife-edge. In Proceedings of the 15th National Conference on Artificial Intelligence (pp. 406\u2013411). Madison, WI."},{"key":"274349_CR49","volume-title":"Knowing and Guessing: A Quantitative Study of Inference and Information","author":"S. Watanabe","year":"1969","unstructured":"Watanabe, S. (1969). Knowing and Guessing: A Quantitative Study of Inference and Information. New York, NY: John Wiley & Sons."},{"key":"274349_CR50","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1016\/0004-3702(94)90104-X","volume":"70","author":"C. Williams","year":"1994","unstructured":"Williams, C. & Hogg, T. (1994). Exploiting the deep structure of constraint problems. Artificial Intelligence, 70, 73\u2013117.","journal-title":"Artificial Intelligence"},{"key":"274349_CR51","doi-asserted-by":"crossref","first-page":"223","DOI":"10.1016\/0004-3702(95)00054-2","volume":"81","author":"W. Zhang","year":"1996","unstructured":"Zhang, W. & Korf, R. (1996). A study of complexity transition on the asymmetric travelling salesman problem. Artificial Intelligence, 81, 223\u2013239.","journal-title":"Artificial Intelligence"},{"key":"274349_CR52","unstructured":"Zucker, J.-D. (1996). Representation changes for efficient learning in structural domains. In Proceedings of the 13th International Conference on Machine Learning (pp. 543\u2013551). Bari, Italy."}],"container-title":["Machine Learning"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1023\/A:1007620705405.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1023\/A:1007620705405\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1023\/A:1007620705405.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,10]],"date-time":"2025-07-10T11:33:47Z","timestamp":1752147227000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1023\/A:1007620705405"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000,11]]},"references-count":52,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2000,11]]}},"alternative-id":["274349"],"URL":"https:\/\/doi.org\/10.1023\/a:1007620705405","relation":{},"ISSN":["0885-6125","1573-0565"],"issn-type":[{"value":"0885-6125","type":"print"},{"value":"1573-0565","type":"electronic"}],"subject":[],"published":{"date-parts":[[2000,11]]},"assertion":[{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}