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

Michael Wachter, Rolf Haenni

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.

Subjects: 11. Knowledge Representation

Submitted: Feb 28, 2006

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.