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.

Subjects: 11. Knowledge Representation; 15.2 Constraint Satisfaction

Submitted: Oct 12, 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.