Informatik, TU Wien

Symposium on New Frontiers in Knowledge Compilation

This symposium is supported by VCLA and the Wolfgang Pauli Institute.

AIMS AND SCOPE

Many reasoning problems in artificial intelligence and automated deduction are computationally intractable in general. Various approaches have been devised to deal with this complexity by exploiting additional conditions that are satisfied in the domain of application at hand. One example involves the case where many instances share a common part, which can be preprocessed once for many instances. Knowledge compilation is devoted to understanding the potential and the limits of preprocessing in computational models and concrete applications.

In typical reasoning scenarios (for instance, automated configuration) many instances share a common background knowledge that is not very often subject to change. This “constant” piece of information can be compiled into a format that allows for more efficient reasoning, once the “varying” part of the instances becomes available. The time needed to compile the background knowledge together with the cumulative time needed to solve a sequence of instances with the compiled background knowledge can be lower (sometimes by orders of magnitude) than the cumulative time needed to solve the sequence of instances with the non-compiled background knowledge. Consequently, sometimes a relatively expensive compilation process may be worthwhile if its results are amortized by repeated use of the compiled knowledge.

Pioneered more than two decades ago, knowledge compilation is now a very active field of research. The aim of this symposium is to bring together researchers who work on knowledge compilation from various angles, including knowledge representation, constraints, theory of algorithms, complexity, machine learning, and databases, as well as researchers from related areas. Lectures and discussions will put all these different approaches into context and will stimulate a fruitful exchange of ideas between researchers from different fields.

Symposium chairs

Pierre Marquis (CRIL-CNRS/Université d’Artois, France)
Stefan Szeider (TU Wien, Austria)