OATAO - Open Archive Toulouse Archive Ouverte Open Access Week

Semiring Labelled Decision Diagrams, Revisited: Canonicity and Spatial Efficiency Issues

Fargier, Hélène and Marquis, Pierre and Schmidt, Nicolas Semiring Labelled Decision Diagrams, Revisited: Canonicity and Spatial Efficiency Issues. (2013) In: International Joint Conference on Artificial Intelligence - IJCAI 2013, 3 August 2013 - 9 August 2013 (Beijing, China).

[img] (Document in English)

PDF (Author's version) - Depositor and staff only - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader
346kB

Abstract

Existing languages in the valued decision diagrams (VDDs) family, including ADD, AADD, and those of the SLDD family, prove to be valuable target languages for compiling multivariate functions. However, their efficiency is directly related to the size of the compiled formulae. In practice, the existence of canonical forms may have a major impact on the size of the compiled VDDs. While efficient normalization procedures have been pointed out for ADD and AADD the canonicity issue for SLDD formulae has not been addressed so far. In this paper, the SLDD family is revisited. We modify the algebraic requirements imposed on the valuation structure so as to ensure tractable conditioning, optimization and normalization for some languages of the revisited SLDD family. We show that AADD is captured by this family. Finally, we compare the spatial efficiency of some languages of this family, from both the theoretical side and the practical side.

Item Type:Conference or Workshop Item (Paper)
Additional Information:Thanks to ACM editor. The definitive version is available at http://dl.acm.org/citation.cfm?id=2540256
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 - INPT (FRANCE)
Université de Toulouse > Université Toulouse III - Paul Sabatier - UPS (FRANCE)
Université de Toulouse > Université Toulouse - Jean Jaurès - UT2J (FRANCE)
Université de Toulouse > Université Toulouse 1 Capitole - UT1 (FRANCE)
Other partners > Université d'Artois (FRANCE)
Laboratory name:
Funders:
ANR- 11-BS02-008
Statistics:download
Deposited By: IRIT IRIT
Deposited On:09 Apr 2015 12:51

Repository Staff Only: item control page