ML Anthology

On Valued Negation Normal Form Formulas

Hélène Fargier, Pierre Marquis
IJCAI 2007 pp. 360-365
/ijcai/2007/fargier2007ijcai-valued/

Abstract

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

PDF Semantic Scholar

Cite

Text

Fargier and Marquis. "On Valued Negation Normal Form Formulas." International Joint Conference on Artificial Intelligence, 2007.

Markdown

[Fargier and Marquis. "On Valued Negation Normal Form Formulas." International Joint Conference on Artificial Intelligence, 2007.](https://mlanthology.org/ijcai/2007/fargier2007ijcai-valued/)

BibTeX

@inproceedings{fargier2007ijcai-valued,
  title     = {{On Valued Negation Normal Form Formulas}},
  author    = {Fargier, Hélène and Marquis, Pierre},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year      = {2007},
  pages     = {360-365},
  url       = {https://mlanthology.org/ijcai/2007/fargier2007ijcai-valued/}
}