On Valued Negation Normal Form Formulas

Hélène Fargier, Pierre Marquis

Subsets of the Negation Normal Form formulas (NNFs) of propositional logic have received much attention in AI and proved as valuable representation languages for Boolean functions. In this paper, we present a new framework, called VNNF, for the representation of a much more general class of functions than just Boolean ones. This framework supports a larger family of queries and transformations than in the NNF case, including optimization ones. As such, it encompasses a number of existing settings, e.g. NNFs, semiring CSPs, mixed CSPs, SLDDs, ADD, AADDs. We show how the properties imposed on NNFs to define more "tractable" fragments (decomposability, determinism, decision, read-once) can be extended to VNNFs, giving rise to subsets for which a number of queries and transformations can be achieved in polynomial time.

URL: ftp://ftp.irit.fr/IRIT/RPDMP/PapersFargier/IJCAI07Fargier.pdf