Propositional DAGs: a New Graph-Based Language for Representing Boolean Functions

Principles of Knowledge Representation and Reasoning: Proceedings of the Tenth International Conference (KR2006)

Volume

Principles of Knowledge Representation and Reasoning: Proceedings of the Tenth International Conference (KR2006)

Contents

This paper continues the line of research on knowledge compilation in the context of Negation Normal Forms (NNF) and Binary Decision Diagrams (BDD). The idea is to analyze different target languages according to their succinctness and the classes of queries and transformations supported in polytime. We identify a new property called simple-negation, which is an implicit restriction of all NNFs and BDDs. The removal of this restriction leads to Propositional Directed Acyclic Graphs (PDAG), a more general family of graph-based languages for representing Boolean functions or propositional theories. With respect to certain NNF-based languages, we will show that corresponding PDAG-based languages are at least as succinct and support the same transformations. The most interesting language even supports the same queries and an additional transformation, making it more flexible.