Knowledge Compilation Map: Theory and Application

Boolean functions are fundamental whenever knowledge is represented by constraints on Boolean variables, i.e. through a set of possible states in the corresponding multi-dimensional Boolean space. In practice, working with Boolean functions presupposes efficient ways to represent them. Many research groups from different areas work on this subject, producing different types of representations of Boolean functions. Two basic qualities characterize these representations: their succinctness, and their set of queries and transformations supported in time polynomial in the size of the representation. This dissertation extends the work of Darwiche and Marquis by taking new representations and more transformations and queries into account. In addition, we make the transition from Boolean functions to Boolean-valued ones, and consider the representation of more general functions. Finally, the dissertation contains both a survey of several applications and a Java-based implementation.