M. Abadi and J. Y. Halpern, Decidability and Expressiveness for First-Order Logics of Probability, Information and Computation, vol.112, issue.1, pp.1-36, 1994.
DOI : 10.1006/inco.1994.1049

D. Angluin, Queries and concept learning, Machine Learning, pp.319-342, 1988.
DOI : 10.1007/BF00116828
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.454.4681

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.
DOI : 10.1016/S1571-0653(04)00313-0

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

N. Cesa-bianchi, Analysis of two gradient-based algorithms for on-line regression, Proceedings of the tenth annual conference on Computational learning theory , COLT '97, pp.392-411, 1999.
DOI : 10.1145/267460.267492

M. Chavira and A. Darwiche, On probabilistic inference by weighted model counting. Artificial Intelligence, 2008.

M. Chavira, A. Darwiche, and M. Jaeger, Compiling relational Bayesian networks for exact inference, International Journal of Approximate Reasoning, vol.42, issue.1-2, pp.4-20, 2006.
DOI : 10.1016/j.ijar.2005.10.001

J. Chen, I. A. Kanj, and G. Xia, Simplicity is beauty: Improved upper bounds for vertex cover, 2005.

V. S. Costa, D. Page, M. Qazi, and J. Cussens, CLP(BN): Constraint logic programming for probabilistic knowledge, Proc. of the Nineteenth Conference in Uncertainty in Artificial Intelligence, pp.517-524, 2003.

R. T. Cox, Probability, Frequency and Reasonable Expectation, American Journal of Physics, vol.14, issue.1, pp.1-13, 1946.
DOI : 10.1119/1.1990764

C. M. Cumby and D. Roth, Relational representations that facilitate learning, Proceedings or the Seventeenth International Conference on the Principles of Knowledge Representation and Reasoning, pp.425-434, 2000.

A. Darwiche, A differential approach to inference in Bayesian networks, Journal of the ACM, vol.50, issue.3, pp.280-305, 2003.
DOI : 10.1145/765568.765570

A. Darwiche and P. Marquis, A knowledge compilation map, Journal of Artificial Intelligence Research, vol.17, pp.229-264, 2002.

L. De-raedt and K. Kersting, Probabilistic inductive logic programming, Proceedings ot the Fifteenth International Conference on Algorithmic Learning Theory, pp.19-36, 2004.

D. Val and A. , First order LUB approximations: characterization and algorithms, Artificial Intelligence, vol.162, issue.1-2, pp.7-48, 2005.
DOI : 10.1016/j.artint.2004.01.003

N. Friedman, L. Getoor, D. Koller, and A. Pfeffer, Learning probabilistic relational models, Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence, pp.1300-1309, 1999.

C. Gentile, -norm algorithms, Proceedings of the twelfth annual conference on Computational learning theory , COLT '99, pp.265-299, 2003.
DOI : 10.1145/307400.307405
URL : https://hal.archives-ouvertes.fr/hal-00809067

L. Getoor and B. Taskar, Introduction to Statistical Relational Learning, 2007.

R. Greiner, A. J. Grove, and D. Schuurmans, Learning Bayesian nets that perform well, Proceedings of the Thirteenth Conference on Uncertainty in Artificial Intelligence, pp.198-207, 1997.

A. J. Grove, J. Y. Halpern, and D. Koller, Random worlds and maximum entropy, [1992] Proceedings of the Seventh Annual IEEE Symposium on Logic in Computer Science, pp.33-88, 1994.
DOI : 10.1109/LICS.1992.185516
URL : http://arxiv.org/abs/cs/9408101

A. J. Grove, N. Littlestone, and D. Schuurmans, General convergence results for linear discriminant updates, Proceedings of the tenth annual conference on Computational learning theory , COLT '97, pp.173-210, 2001.
DOI : 10.1145/267460.267493

J. Y. Halpern, Reasoning about Uncertainty, 2003.

D. P. Helmbold, R. E. Schapire, Y. Singer, and M. K. Warmuth, A comparison of new and old algorithms for a mixture estimation problem, Proceedings of the eighth annual conference on Computational learning theory , COLT '95, pp.97-119, 1997.
DOI : 10.1145/225298.225306

M. Jaeger, Relational Bayesian networks, Proceedings of the Thirteenth Conference on Uncertainty in Artificial Intelligence, 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

K. Kersting, An Inductive Logic Programming Approach to Statistical Relational Learning, Frontiers in Artificial Intelligence and Applications, vol.148, 2006.

R. Khardon, Learning to take actions, Machine Learning, pp.57-90, 1999.

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

S. Kok and P. Domingos, Learning the structure of Markov logic networks, Proceedings of the 22nd international conference on Machine learning , ICML '05, pp.441-448, 2005.
DOI : 10.1145/1102351.1102407

P. Liberatore, Compilation of intractable problems and its application to artificial intelligence, Dipartimento di Informatica e Sistemistica, 1998.

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=10.1.1.130.9013

N. Littlestone, Mistake bounds and logarithmic linear-threshold learning algorithms, 1989.

M. Manzano, Extensions of First-Order Logic, 2005.

L. Mihalkova, T. Huynh, and R. J. Mooney, Mapping and revising Markov logic networks for transfer learning, Proceedings of the Twenty-Second AAAI Conference Frédéric Koriche on Artificial Intelligence, pp.608-614, 2007.

S. Muggleton, Stochastic logic programs, Advances in Inductive Logic Programming, pp.254-264, 1996.

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, Proceedings of the Ninth International Conference in Theory and Applications of Satisfiability Testing, pp.396-409, 2006.
DOI : 10.1007/11814948_36
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.217.5747

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

A. Pfeffer, Probabilistic Reasoning for Complex Systems, 2000.

D. Poole, Probabilistic Horn abduction and Bayesian networks, Artificial Intelligence, vol.64, issue.1, pp.81-129, 1993.
DOI : 10.1016/0004-3702(93)90061-F
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.50.603

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

Y. Ruan, H. A. Kautz, and E. Horvitz, The backdoor key: A path to understanding problem hardness, Proceedings of the Nineteenth National Conference on Artificial Intelligence, pp.124-130, 2004.

T. Sang, P. Beame, and H. A. Kautz, Performing Bayesian inference by weighted model counting, Proceedings of the Twentieth National Conference on Artificial Intelligence, pp.475-482, 2005.

B. Selman and H. A. Kautz, Knowledge compilation and theory approximation, Journal of the ACM, vol.43, issue.2, pp.193-224, 1996.
DOI : 10.1145/226643.226644
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.100.2077

B. Taskar, P. Abbeel, and D. Koller, Discriminative probabilistic models for relational data, Proceedings of the Eighteenth Conference in Uncertainty in Artificial Intelligence, pp.485-492, 2002.

B. Taskar, V. Chatalbashev, and D. Koller, Learning associative Markov networks, Twenty-first international conference on Machine learning , ICML '04, 2004.
DOI : 10.1145/1015330.1015444
URL : http://ai.stanford.edu/~koller/Papers/Taskar+al:ICML04.pdf

B. Taskar, C. Guestrin, and D. Koller, Max-margin Markov networks, Advances in Neural Information Processing Systems 16, 2003.

L. G. Valiant, Circuits of the Mind, 1994.

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
URL : http://doi.org/10.1016/s0004-3702(00)00002-3

R. Williams, C. P. Gomes, and B. Selman, Backdoors to typical case complexity, Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence, pp.1173-1178, 2003.