OATAO - Open Archive Toulouse Archive Ouverte Open Access Week

A Knowledge Compilation Map for Ordered Real-Valued Decision Diagrams

Fargier, Hélène and Marquis, Pierre and Niveau, Alexandre and Schmidt, Nicolas A Knowledge Compilation Map for Ordered Real-Valued Decision Diagrams. (2016) In: AAAI'14 : 28th Conference on Artificial Intelligence (2014), 27 July 2014 - 31 July 2014 (Quebec, Canada).

(Document in English)

PDF (Author's version) - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader


Valued decision diagrams (VDDs) are data structures that represent functions mapping variable-value assignments to non-negative real numbers. They prove useful to compile cost functions, utility functions, or probability distributions. While the complexity of some queries (notably optimization) and transformations (notably conditioning) on VDD languages has been known for some time, there remain many significant queries and transformations, such as the various kinds of cuts, marginalizations, and combinations, the complexity of which has not been identified so far. This paper contributes to filling this gap and completing previous results about the time and space efficiency of VDD languages, thus leading to a knowledge compilation map for real-valued functions. Our results show that many tasks that are hard on valued CSPs are actually tractable on VDDs.

Item Type:Conference or Workshop Item (Paper)
Additional Information:Thanks to Association for the Advancement of Artificial Intelligence (AAAI). The definitive version is available at https: //www.aaai.org The original PDF of the article can be found at: https://www.aaai.org/ocs/index.php/AAAI/AAAI14/paper/view/8195
HAL Id:hal-04077580
Audience (conference):International conference proceedings
Uncontrolled Keywords:
Institution:French research institutions > Centre National de la Recherche Scientifique - CNRS (FRANCE)
Université de Toulouse > Institut National Polytechnique de Toulouse - Toulouse INP (FRANCE)
Université de Toulouse > Université Toulouse III - Paul Sabatier - UT3 (FRANCE)
Université de Toulouse > Université Toulouse - Jean Jaurès - UT2J (FRANCE)
Université de Toulouse > Université Toulouse 1 Capitole - UT1 (FRANCE)
Other partners > Université de Caen Basse-Normandie (FRANCE)
Other partners > Université d'Artois (FRANCE)
Laboratory name:
Deposited On:08 Jun 2017 13:26

Repository Staff Only: item control page