(Birkbeck (University of London))

The following scenario is common in knowledge representation. There is a knowledge base and types of queries to be answered. The requirement is that all these queries must be answered in a polynomial time. However, some queries are intractable (e.g. NP-complete to answer) in the given representation of the knowledge base. A possible solution is *rewriting*: the knowledge base is compiled into a different format where the queries can be answered efficiently. Of course the compilation may take a lot of time. However, it is performed *offline*, at the preprocessing stage and if the knowledge base is not changed over a *long* period of time, the time savings from the query answering will amply compensate the additional preprocessing time.The real difficulty of application of the above methodology is that the knowledge base resulting from the rewriting may become prohibitively large. Therefore the main effort of researchers is concentrated towards design of rewriting algorithms having a reasonable space complexity of their output.

In this talk I will concentrate on the *propositional* rewriting also known as knowledge compilation. In the relevant scenario the initial format of the knowledge base is Conjunctive Normal Form (CNF) and a typical query is whether or not the given partial assignment to its variables can be extended to a satisfying assignment of this CNF.

This kind of query is called *clausal entailment* and it is clearly NP-complete since it is a generalization of the satisfiability testing, a classical NP-complete problem.

The methodology of knowledge compilation is transformation of the input CNF into an equivalent *good* representation for which the clausal entailment query can be answered in a polynomial time. I will overview a number of such representations including: decision trees, ordered binary decision diagrams, free binary decision diagrams, decomposable negation normal forms. I will also overview the relationship between these representations, their advantages and disadvantages.

In the final part of my talk I will intuitively overview an approach to obtain a space-efficient good representation from the initial CNF. This approach is based on the assumption that the CNF is associated with a natural parameter that is very small compared to the size of the CNF. The resulting representation is exponential in terms of this small parameter but polynomial in the input size.

Robert Recorde Room

Department of Computer Science