On Valued Negation Normal Form Formulas
Proceedings of the Twentieth International Joint Conference on Artificial Intelligence. Pages 360-364.
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.
@inproceedings{ijcai2007p56,
title = {On Valued Negation Normal Form Formulas},
author = {Fargier, Helene and Marquis, Pierre},
booktitle = {Proceedings of the Twentieth International Joint Conference on
Artificial Intelligence, {IJCAI-07}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Ramon López de Mántaras},
pages = {360--364},
year = {2007},
url = {https://ijcai.org/proceedings/2007/56},
}
TY - CPAPER TI - On Valued Negation Normal Form Formulas AU - Fargier, Helene AU - Marquis, Pierre T2 - Proceedings of the Twentieth International Joint Conference on Artificial Intelligence, IJCAI-07 PB - International Joint Conferences on Artificial Intelligence PY - 2007 SP - 360 EP - 364 UR - https://ijcai.org/proceedings/2007/56 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
