Knowledge representation languages and knowledge compilation

In this talk, the word “knowledge” has a rather restricted meaning. It is just a set of rules and constraints over variables with a binary domain. Although this setting may seem to be very restricted, in fact a vast number of practical problems can be formulated using this formalism. There is a number of different knowledge representation languages which fit into this framework. Perhaps the most popular one consists of Boolean formulas in conjunctive normal form, others include various types of binary decision diagrams, negational normal forms, circuits and list-based representations. Of course, different languages are suitable for different tasks, and hence selecting the right language is a key ingredient in obtaining a useful knowledge representation. In this talk we will survey a number of standard and also less known knowledge representation languages and discuss their properties.

Knowledge compilation is a research area that studies how the computational complexity of standard tasks such as queries (e.g., consistency check, validity check, model counting, etc.) and transformations (negation, conjunction, disjunction, conditioning, etc.) depends on the chosen knowledge representation language. Furthermore, knowledge compilation studies the complexity of translating (i.e. compiling) given knowledge from one language into another one for various pairs of knowledge representation languages. We will look at some interesting recent results from this area, in particular those connected to the SLR language introduced by the speaker and his students.