Skip to content Search
Search our website:

Succinctness in Knowledge Representation

  • Speaker: Dr. Simone Bova, Institute of Information Systems, Vienna University of Technology.
  • Date: Wednesday, 10 December 2014 from 16:00 to 17:00
  • Location: Room 151, Birkbeck Main Building

The aim of knowledge compilation is to succinctly represent propositional knowledge bases in a format that allows for answering a number of queries in polynomial time. Choosing a representation language generally involves a trade-off between succinctness and the range of queries that can be efficiently answered. For instance, conjunctive normal form formulas (CNFs) are more succinct than prime implicate formulas, but the latter representation enjoys clause entailment checks in polynomial time whereas CNFs in general do not (unless P=NP). In seminal work, motivated by the need to balance the competing requirements of succinctness and tractability, Darwiche and Marquis systematically investigate a hierarchy of representation languages that strike this balance in different ways. However, the current knowledge on how such languages relate to each other in terms of succinctness is still partial. For certain pairs of languages the succinctness relation is unknown, or only conditionally known (some classes of Boolean functions have a superpolynomial increase in the size of their representations in translating from one language to the other, unless the polynomial hierarchy collapses). In this talk, we summarize the current knowledge on the succinctness relation, discuss recent results improving it, and pose questions for future research.