proc-tutorial

Knowledge Compilation: A Sightseeing Tour(tutorial notes – ECAI’08)1Pierre MarquisAbstract. software, applications, etc.). One of the objectives of these notes isto review the main ones, focusing on the propositional case.Pioneered two decades ago, knowledge compilation (KC) has If KC has been identified as a research topic in the quite re-been for a few years acknowledged as an important research cent past, the idea of pre-processing pieces of information for im-topic in AI. KC is concerned with the pre-processing of pieces proving computations (which typically means “saving computationof available information for improving the computational effi- time”) is an old one. It has many applications in Computer Scienceciency of some tasks based on them. In AI such tasks typically (even before the modern computer era). One of the most salient ex-amount to inference or decision making. KC gathers a number ample for illustrating it is the notion of table of logarithms. Suchthof research lines focusing on different problems, ranging from tables have been introduced during the 17 century and used fortheoretical ones (where the key issue is the compilability one, centuries as “compiled forms” for improving many computationsi.e., determining whether computational improvements can be (it was still used three decades ago in french secondary schools).guaranteed via pre-processing) to more practical ones (mainly The principle is first to compute the values of log (x) (using ...