F. Bacchus, A. J. Grove, J. Y. Halpern, and D. Koller, From statistical knowledge bases to degrees of belief, Artificial Intelligence, vol.87, issue.1-2, pp.75-143, 1996.
DOI : 10.1016/S0004-3702(96)00003-3

H. , K. Büning, and X. Zhao, Satisfiable formulas closed under replacement, Electronic Notes in Discrete Mathematics, vol.9, pp.48-58, 2001.

T. Bylander, Worst-case analysis of the perception and exponentiated update algorithms, Artificial Intelligence, vol.106, issue.2, pp.335-352, 1998.
DOI : 10.1016/S0004-3702(98)00098-8

C. M. Cumby and D. Roth, Relational representations that facilitate learning, 17th Int. Conf. on Knowledge Representation and Reasoning, pp.425-434, 2000.

R. Greiner, A. J. Grove, and D. Schuurmans, Learning bayesian nets that perform well, 13th Conference on Uncertainty in AI, pp.198-207, 1997.

D. Haussler, N. Littlestone, and M. K. Warmuth, Predicting {0, 1}-Functions on Randomly Drawn Points, Information and Computation, vol.115, issue.2, pp.248-292, 1994.
DOI : 10.1006/inco.1994.1097

URL : http://dx.doi.org/10.1006/inco.1994.1097

T. Horváth and G. Turán, Learning logic programs with structured background knowledge??????An extended abstract of this paper appeared in: L.??De Raedt (Ed.), Proceedings of the Fifth International Workshop on Inductive Logic Programming, Tokyo, Japan, 1995, pp. 53???76, Scientific Report of the Department of Computer Science, Katholieke Universiteit Leuven, and also in the post-conference volume: L.??De Raedt (Ed.), Advances in Inductive Logic Programming, IOS Press, Amsterdam/Ohmsha, Tokyo, 1996, pp. 172???191., Artificial Intelligence, vol.128, issue.1-2, pp.31-97, 2001.
DOI : 10.1016/S0004-3702(01)00062-5

M. Jaeger, Relational bayesian networks, 13th Int. Conference on Uncertainty in AI, pp.266-273, 1997.

M. Jaeger, On the complexity of inference about probabilistic relational models, Artificial Intelligence, vol.117, issue.2, pp.297-308, 2000.
DOI : 10.1016/S0004-3702(99)00109-5

R. Khardon and D. Roth, Learning to reason, Journal of the ACM, vol.44, issue.5, pp.697-725, 1997.
DOI : 10.1145/265910.265918

R. Khardon and D. Roth, Learning to reason with a restricted view, Proceedings of the eighth annual conference on Computational learning theory , COLT '95, pp.95-116, 1999.
DOI : 10.1145/225298.225335

J. Kivinen and M. K. Warmuth, Exponentiated Gradient versus Gradient Descent for Linear Predictors, Information and Computation, vol.132, issue.1, pp.1-63, 1997.
DOI : 10.1006/inco.1996.2612

URL : http://doi.org/10.1006/inco.1996.2612

D. Koller and A. Pfeffer, Learning probabilities for noisy first-order rules, Proc. of the 15th Int. Joint Conference on Artificial Intelligence, pp.1316-1323, 1997.

N. Littlestone, Learning quickly when irrelevant attributes abound: A new linearthreshold algorithm, Machine Learning, pp.285-318, 1988.
DOI : 10.1109/sfcs.1987.37

URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=

R. Ng and V. S. Subrahmanian, Probabilistic logic programming, Information and Computation, vol.101, issue.2, pp.150-201, 1992.
DOI : 10.1016/0890-5401(92)90061-J

URL : http://doi.org/10.1016/0890-5401(92)90061-j

L. Ngo and P. Haddawy, Answering queries from context-sensitive probabilistic knowledge bases, Theoretical Computer Science, vol.171, issue.1-2, pp.147-177, 1997.
DOI : 10.1016/S0304-3975(96)00128-4

URL : http://doi.org/10.1016/s0304-3975(96)00128-4

N. Nishimura, P. Ragde, and S. Szeider, Solving #SAT using vertex covers, SAT: 9th International Conference, pp.396-409, 2006.
DOI : 10.1007/11814948_36

URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=

J. Pearl, Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference, 1988.

D. Poole, The independent choice logic for modelling multiple agents under uncertainty, Artificial Intelligence, vol.94, issue.1-2, pp.7-56, 1997.
DOI : 10.1016/S0004-3702(97)00027-1

D. Roth, On the hardness of approximate reasoning, Artificial Intelligence, vol.82, issue.1-2, pp.273-302, 1996.
DOI : 10.1016/0004-3702(94)00092-1

T. Sang, P. Beame, and H. A. Kautz, Performing Bayesian inference by weighted model counting, 20h National Conference on Artificial Intelligence (AAAI), pp.475-482, 2005.

L. G. Valiant, A neuroidal architecture for cognitive computation, Journal of the ACM, vol.47, issue.5, pp.854-882, 2000.
DOI : 10.1145/355483.355486

L. G. Valiant, Robust logics, Artificial Intelligence, vol.117, issue.2, pp.231-253, 2000.
DOI : 10.1016/S0004-3702(00)00002-3

T. Van-allen, R. Greiner, and P. Hooper, Bayesian error-bars for belief net inference, 17th Conference on Uncertainty in AI, pp.522-529, 2001.

M. Veloso, Learning by Analogical Reasoning in General Problem Solving, 1992.