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.
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.