Florent Capelli, Université d’Artois, CRIL

Les transparents: ici.

The tractability of many reasoning tasks on knowledge bases heavily depends on the way the knowledge itself is represented. Unfortunately, it often happens that the most natural representation is also the most intractable one. To circumvent this difficulty, it may sometimes be interesting to spend some time offline to compute a better and more tractable representation of the knowledge base so that interacting with it gets easier. The field of Knowledge Compilation studies the different representations, their properties and the cost of changing the representation of a given knowledge base. While knowledge compilation has mostly focused on representing Boolean functions, the underlying data structures used in this domain have recently found applications in databases, mathematical optimization or complexity theory. In this talk, we will give an overview of the definition of these data structures, their properties and their use in different subfields of computer science.