Résumé

La complexité du comptage et la compilation des connaissances sont deux domaines de recherche intimement liés. Alors que le premier a été étudié dans dans de nombreux sous-domaines de l’informatique depuis plusieurs décennies, le second est relativement jeune et était jusqu’à récemment confiné à l’intelligence artificielle, son domaine d’origine. Dans cette thèse d’habilitation, je passe en revue mes travaux sur le comptage et la compilation de connaissances au cours des huit dernières années. En particulier, je discute de la façon dont les restrictions structurelles des entrées conduisent à un comptage et une compilation de connaissances efficaces dans plusieurs domaines et je présente des techniques pour montrer des bornes inférieures pour la compilation de connaissances. Enfin, un accent particulier est mis sur les applications de la compilation de connaissances dans divers domaines, notamment dans l’intelligence artificielle, la théorie des bases de données et l’informatique théorique

Jury

  • Pierre Marquis (Directeur), Université d’Artois, France
  • Adnan Darwiche (Rapporteur), UCLA, États Unis
  • Reinhard Pichler (Rapporteur), TU Wien, Autriche
  • Pierre Senellart (Rapporteur), École normale supérieure, France
  • Nadia Creignou (Examinateur), Aix Marseille Université, France
  • Hélène Fargier (Examinateur), CNRS, France