{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T11:46:42Z","timestamp":1725536802869},"publisher-location":"Berlin, Heidelberg","reference-count":43,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642041792"},{"type":"electronic","value":"9783642041808"}],"license":[{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2009]]},"DOI":"10.1007\/978-3-642-04180-8_21","type":"book-chapter","created":{"date-parts":[[2009,8,27]],"date-time":"2009-08-27T08:11:20Z","timestamp":1251360680000},"page":"51-66","source":"Crossref","is-referenced-by-count":2,"title":["Empirical Study of Relational Learning Algorithms in the Phase Transition Framework"],"prefix":"10.1007","author":[{"given":"Erick","family":"Alphonse","sequence":"first","affiliation":[]},{"given":"Aomar","family":"Osmani","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"1","key":"21_CR1","doi-asserted-by":"publisher","first-page":"80","DOI":"10.1145\/959242.959252","volume":"5","author":"P. Domingos","year":"2003","unstructured":"Domingos, P.: Prospects and challenges for multi-relational data mining. SIGKDD Explorations\u00a05(1), 80\u201383 (2003)","journal-title":"SIGKDD Explorations"},{"key":"21_CR2","first-page":"415","volume":"4","author":"D. Page","year":"2003","unstructured":"Page, D., Srinivasan, A.: Ilp: a short look back and a longer look forward. J. Mach. Learn. Res.\u00a04, 415\u2013430 (2003)","journal-title":"J. Mach. Learn. Res."},{"key":"21_CR3","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1016\/0004-3702(82)90040-6","volume":"18","author":"T.M. Mitchell","year":"1982","unstructured":"Mitchell, T.M.: Generalization as search. Artificial Intelligence\u00a018, 203\u2013226 (1982)","journal-title":"Artificial Intelligence"},{"key":"21_CR4","volume-title":"Human Problem Solving","author":"A. Newell","year":"1972","unstructured":"Newell, A., Simon, H.A.: Human Problem Solving. Prentice-Hall, Englewood Cliffs (1972)"},{"key":"21_CR5","first-page":"331","volume-title":"Proc. of the 12th International Joint Conference on Artificial Intelligence","author":"P. Cheeseman","year":"1991","unstructured":"Cheeseman, P., Kanefsky, B., Taylor, W.: Where the really hard problems are. In: Proc. of the 12th International Joint Conference on Artificial Intelligence, pp. 331\u2013340. Morgan Kaufmann, San Francisco (1991)"},{"key":"21_CR6","unstructured":"Mitchell, D., Selman, B., Levesque, H.: Hard and easy distribution of SAT problems. In: Proceedings of the Tenth National Conference on Artificial Intelligence (AAAI 1992), pp. 440\u2013446 (1992)"},{"key":"21_CR7","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1038\/22055","volume":"400","author":"R. Monasson","year":"1999","unstructured":"Monasson, R., Zecchina, R., Kirkpatrick, S., Selman, B., Troyansky, L.: Determining computational complexity from characteristic \u2019phase transitions. Nature\u00a0400, 133\u2013137 (1999)","journal-title":"Nature"},{"issue":"1-2","key":"21_CR8","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1016\/0004-3702(95)00052-6","volume":"81","author":"B.M. Smith","year":"1996","unstructured":"Smith, B.M., Dyer, M.E.: Locating the phase transition in binary constraint satisfaction problems. Artificial Intelligence\u00a081(1-2), 155\u2013181 (1996)","journal-title":"Artificial Intelligence"},{"issue":"1\u20132","key":"21_CR9","doi-asserted-by":"publisher","first-page":"359","DOI":"10.1016\/0004-3702(94)90088-4","volume":"69","author":"T. Hogg","year":"1994","unstructured":"Hogg, T., Williams, C.: The hardest constraint problems: A double phase transition. Artificial Intelligence\u00a069(1\u20132), 359\u2013377 (1994)","journal-title":"Artificial Intelligence"},{"key":"21_CR10","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1613\/jair.370","volume":"7","author":"D.L. Mammen","year":"1997","unstructured":"Mammen, D.L., Hogg, T.: A new look at the easy-hard-easy pattern of combinatorial search difficulty. Journal of Artificial Intelligence Research\u00a07, 47\u201366 (1997)","journal-title":"Journal of Artificial Intelligence Research"},{"key":"21_CR11","doi-asserted-by":"crossref","unstructured":"Gomes, C., Heny Kautz, A.S., Selman, B.: Satisfiability solvers. In: Handbook of Knowledge Representation (2007)","DOI":"10.1016\/S1574-6526(07)03002-7"},{"issue":"1","key":"21_CR12","first-page":"7","volume":"4","author":"D. Haussler","year":"1989","unstructured":"Haussler, D.: Learning conjunctive concepts in structural domains. Machine Learning\u00a04(1), 7\u201340 (1989)","journal-title":"Machine Learning"},{"key":"21_CR13","doi-asserted-by":"crossref","DOI":"10.7551\/mitpress\/3897.001.0001","volume-title":"An Introduction to Computational Learning Theory","author":"M.J. Kearns","year":"1994","unstructured":"Kearns, M.J., Vazirani, U.V.: An Introduction to Computational Learning Theory. The MIT Press, Cambridge (1994)"},{"key":"21_CR14","doi-asserted-by":"crossref","first-page":"1","DOI":"10.3233\/SAT190014","volume":"2","author":"N. En","year":"2006","unstructured":"En, N., Srensson, N.: Translating pseudo-boolean constraints into SAT. Journal on Satisfiability, Boolean Modeling and Computation\u00a02, 1\u201326 (2006)","journal-title":"Journal on Satisfiability, Boolean Modeling and Computation"},{"issue":"2","key":"21_CR15","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1023\/A:1007329424533","volume":"27","author":"J. F\u00fcrnkranz","year":"1997","unstructured":"F\u00fcrnkranz, J.: Pruning algorithms for rule learning. Mach. Learn.\u00a027(2), 139\u2013172 (1997)","journal-title":"Mach. Learn."},{"key":"21_CR16","doi-asserted-by":"publisher","first-page":"1079","DOI":"10.1103\/PhysRevA.43.1079","volume":"43","author":"G.M. Shim","year":"1991","unstructured":"Shim, G.M., Choi, M.Y., Kim, D.: Phase transitions in a dynamic model of neural networks. Physics Review A\u00a043, 1079\u20131089 (1991)","journal-title":"Physics Review A"},{"key":"21_CR17","doi-asserted-by":"crossref","unstructured":"Nagashino, H., Kelso, J.A.: Phase transitions in oscillatory neural networks. In: Society of Photo-Optical Instrumentation Engineers (SPIE) Conference Series, vol.\u00a01710, pp. 279\u2013287 (1992)","DOI":"10.1117\/12.140094"},{"key":"21_CR18","doi-asserted-by":"publisher","first-page":"4515","DOI":"10.1088\/0305-4470\/28\/16\/010","volume":"28","author":"B. Schottky","year":"1995","unstructured":"Schottky, B.: Phase transitions in the generalization behaviour of multilayer neural networks. Journal of Physics A Mathematical General\u00a028, 4515\u20134531 (1995)","journal-title":"Journal of Physics A Mathematical General"},{"key":"21_CR19","doi-asserted-by":"publisher","first-page":"819","DOI":"10.1007\/BFb0108398","volume":"40\/2000","author":"M. Biehl","year":"2000","unstructured":"Biehl, M., Ahr, M., Schlsser, E.: Statistical physics of learning: Phase transitions in multilayered neural networks. Advances in Solid State Physics\u00a040\/2000, 819\u2013826 (2000)","journal-title":"Advances in Solid State Physics"},{"key":"21_CR20","first-page":"431","volume":"4","author":"M. Botta","year":"2003","unstructured":"Botta, M., Giordana, A., Saitta, L., Sebag, M.: Relational learning as search in a critical region. Journal of Machine Learning Research\u00a04, 431\u2013463 (2003)","journal-title":"Journal of Machine Learning Research"},{"key":"21_CR21","doi-asserted-by":"crossref","unstructured":"Alphonse, E., Osmani, A.: A model to study phase transition and plateaus in relational learning. In: Proc. of Conf. on Inductive Logic Programming, pp. 6\u201323 (2008)","DOI":"10.1007\/978-3-540-85928-4_6"},{"key":"21_CR22","series-title":"Lecture Notes in Artificial Intelligence","doi-asserted-by":"publisher","first-page":"405","DOI":"10.1007\/3-540-36755-1_34","volume-title":"Machine Learning: ECML 2002","author":"U. R\u00fcckert","year":"2002","unstructured":"R\u00fcckert, U., Kramer, S., Raedt, L.D.: Phase transitions and stochastic local search in k-term DNF learning. In: Elomaa, T., Mannila, H., Toivonen, H. (eds.) ECML 2002. LNCS (LNAI), vol.\u00a02430, pp. 405\u2013417. Springer, Heidelberg (2002)"},{"key":"21_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1007\/3540635149_31","volume-title":"Inductive Logic Programming","author":"G. Gottlob","year":"1997","unstructured":"Gottlob, G., Leone, N., Scarcello, F.: On the complexity of some inductive logic programming problems. In: D\u017eeroski, S., Lavra\u010d, N. (eds.) ILP 1997. LNCS, vol.\u00a01297, pp. 17\u201332. Springer, Heidelberg (1997)"},{"issue":"1-2","key":"21_CR24","doi-asserted-by":"publisher","first-page":"241","DOI":"10.1016\/0004-3702(95)00055-0","volume":"81","author":"T. Bylander","year":"1996","unstructured":"Bylander, T.: A probabilistic analysis of propositional strips planning. Artificial Intelligence\u00a081(1-2), 241\u2013271 (1996)","journal-title":"Artificial Intelligence"},{"key":"21_CR25","unstructured":"Gent, I.P., Walsh, T.: Beyond NP: the QSAT phase transition. In: AAAI 1999\/IAAI 1999: Proceedings of the sixteenth national conference on Artificial intelligence and the eleventh Innovative applications of artificial intelligence conference, pp. 648\u2013653 (1999)"},{"key":"21_CR26","unstructured":"Chen, H., Interian, Y.: A model for generating random quantified boolean formulas. In: Kaelbling, L.P., Saffiotti, A. (eds.) Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence, pp. 66\u201371. Professional Book Center (2005)"},{"key":"21_CR27","unstructured":"Srinivasan, A.: A learning engine for proposing hypotheses (Aleph) (1999), http:\/\/web.comlab.ox.ac.uk\/oucl\/research\/areas\/machlearn\/Aleph"},{"key":"21_CR28","doi-asserted-by":"publisher","first-page":"245","DOI":"10.1007\/BF03037227","volume":"13","author":"S. Muggleton","year":"1995","unstructured":"Muggleton, S.: Inverse entailment and PROGOL. New Generation Computing\u00a013, 245\u2013286 (1995)","journal-title":"New Generation Computing"},{"key":"21_CR29","series-title":"Lecture Notes in Artificial Intelligence","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1007\/978-3-540-73847-3_13","volume-title":"Inductive Logic Programming","author":"\u00c9. Alphonse","year":"2007","unstructured":"Alphonse, \u00c9., Rouveirol, C.: Extension of the top-down data-driven strategy to ILP. In: Muggleton, S.H., Otero, R., Tamaddoni-Nezhad, A. (eds.) ILP 2006. LNCS (LNAI), vol.\u00a04455, pp. 49\u201363. Springer, Heidelberg (2007)"},{"key":"21_CR30","doi-asserted-by":"crossref","unstructured":"Cook, S.A., Mitchell, D.G.: Finding hard instances of the satisfiability problem: A survey. In: DIMACS Series in Discrete Mathematics and Theoretical Computer Science, pp. 1\u201317. American Mathematical Society (1997)","DOI":"10.1090\/dimacs\/035\/01"},{"issue":"3","key":"21_CR31","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1016\/j.tcs.2006.01.001","volume":"355","author":"K. Xu","year":"2006","unstructured":"Xu, K., Li, W.: Many hard examples in exact phase transitions. Theor. Comput. Sci.\u00a0355(3), 291\u2013302 (2006)","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"21_CR32","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1016\/0020-0190(87)90103-7","volume":"24","author":"G. Gottlob","year":"1987","unstructured":"Gottlob, G.: Subsumption and implication. Information Processing Letters\u00a024(2), 109\u2013111 (1987)","journal-title":"Information Processing Letters"},{"key":"21_CR33","series-title":"Lecture Notes in Artificial Intelligence","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1007\/3-540-36169-3_22","volume-title":"Algorithmic Learning Theory","author":"J. F\u00fcrnkranz","year":"2002","unstructured":"F\u00fcrnkranz, J.: A pathology of bottom-up hill-climbing in inductive rule learning. In: Cesa-Bianchi, N., Numao, M., Reischuk, R. (eds.) ALT 2002. LNCS (LNAI), vol.\u00a02533, pp. 263\u2013277. Springer, Heidelberg (2002)"},{"key":"21_CR34","unstructured":"Plotkin, G.: A note on inductive generalization. In: Machine Intelligence, pp. 153\u2013163. Edinburgh University Press (1970)"},{"key":"21_CR35","first-page":"436","volume-title":"ACM Symposium on Theory of Computing (STOC 1984)","author":"L.G. Valiant","year":"1984","unstructured":"Valiant, L.G.: A theory of the learnable. In: ACM Symposium on Theory of Computing (STOC 1984), Baltimore, USA, pp. 436\u2013445. ACM Press, New York (1984)"},{"key":"21_CR36","unstructured":"Kietz, J.U.: A comparative study of structural most specific generalisations used in machine learning. In: Proc. Third Workshop on ILP, pp. 149\u2013164 (1993)"},{"key":"21_CR37","unstructured":"Muggleton, S., Feng, C.: Efficient induction of logic programs. In: Proc. of the 1st Conference on Algorithmic Learning Theory, Ohmsma, Tokyo, Japan, pp. 368\u2013381 (1990)"},{"issue":"8","key":"21_CR38","first-page":"664","volume":"31","author":"Y.I. Paskal","year":"1988","unstructured":"Paskal, Y.I.: The meaning of the terms phase and phase transition. Russian Physics Journal\u00a031(8), 664\u2013666 (1988)","journal-title":"Russian Physics Journal"},{"key":"21_CR39","unstructured":"Selman, B., Levesque, H.J., Mitchell, D.: A new method for solving hard satisfiability problems. In: Proc. of the Tenth National Conference on Artificial Intelligence, Menlo Park, California, pp. 440\u2013446 (1992)"},{"issue":"1\u20132","key":"21_CR40","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1016\/0004-3702(94)90109-0","volume":"70","author":"I.P. Gent","year":"1994","unstructured":"Gent, I.P., Walsh, T.: Easy problems are sometimes hard. Artificial Intelligence\u00a070(1\u20132), 335\u2013345 (1994)","journal-title":"Artificial Intelligence"},{"key":"21_CR41","unstructured":"Davenport, A.: A comparison of complete and incomplete algorithms in the easy and hard regions. In: Workshop on Studying and Solving Really Hard Problems, CP 1995, pp. 43\u201351 (1995)"},{"issue":"1\u20132","key":"21_CR42","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1016\/S0304-3975(01)00166-9","volume":"265","author":"B.M. Smith","year":"2001","unstructured":"Smith, B.M.: Constructing an asymptotic phase transition in random binary constraint satisfaction problems. Theoretical Computer Science\u00a0265(1\u20132), 265\u2013283 (2001)","journal-title":"Theoretical Computer Science"},{"issue":"8-9","key":"21_CR43","doi-asserted-by":"publisher","first-page":"514","DOI":"10.1016\/j.artint.2007.04.001","volume":"171","author":"K. Xu","year":"2007","unstructured":"Xu, K., Boussemart, F., Hemery, F., Lecoutre, C.: Random constraint satisfaction: Easy generation of hard (satisfiable) instances. Artif. Intell.\u00a0171(8-9), 514\u2013534 (2007)","journal-title":"Artif. Intell."}],"container-title":["Lecture Notes in Computer Science","Machine Learning and Knowledge Discovery in Databases"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-04180-8_21","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,5,21]],"date-time":"2020-05-21T20:04:25Z","timestamp":1590091465000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-04180-8_21"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642041792","9783642041808"],"references-count":43,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-04180-8_21","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2009]]}}}