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

Hélène Fargier (1, 2) , Pierre Marquis (3) , Nicolas Schmidt (3)

1 IRIT-ADRIA - Argumentation, Décision, Raisonnement, Incertitude et Apprentissage
2 CNRS - Centre National de la Recherche Scientifique
3 CRIL - Centre de Recherche en Informatique de Lens

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.

Mots clés: Valued decision diagrams; Canonicity; Spatial efficiency; Languages

Domaines: Intelligence artificielle [cs.AI]; Informatique et langage [cs.CL]; Apprentissage [cs.LG]; Logique en informatique [cs.LO]

Hélène Fargier, Pierre Marquis, Nicolas Schmidt. Semiring Labelled Decision Diagrams, Revisited: Canonicity and Spatial Efficiency Issues. 23rd International Joint Conference on Artificial Intelligence (IJCAI 2013), International Joint Conferences on Artificial Intelligence (IJCAI), Aug 2013, Pékin, China. pp.884-890. ⟨hal-04085303⟩