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

Fargier, Helene; Marquis, Pierre; Schmidt, Nicolas

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

Hélène Fargier, Pierre Marquis, Nicolas Schmidt

Download BibTeX Cite

Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence. Pages 884-889.

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.

Helene Fargier, Pierre Marquis, and Nicolas Schmidt. 2013. Semiring Labelled Decision Diagrams, Revisited: Canonicity and Spatial Efficiency Issues. In Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence, IJCAI-13. IJCAI, 884–889. https://ijcai.org/proceedings/2013/136

@inproceedings{ijcai2013p136,
  title     = {Semiring Labelled Decision Diagrams, Revisited: Canonicity and Spatial Efficiency Issues},
  author    = {Fargier, Helene and Marquis, Pierre and Schmidt, Nicolas},
  booktitle = {Proceedings of the Twenty-Third International Joint Conference on
               Artificial Intelligence, {IJCAI-13}},
  publisher = {AAAI Press / International Joint Conferences on Artificial Intelligence},
  editor    = {Francesca Rossi},
  pages     = {884--889},
  year      = {2013},
  month     = {8},
  url       = {https://ijcai.org/proceedings/2013/136},
}

TY  - CPAPER
TI  - Semiring Labelled Decision Diagrams, Revisited: Canonicity and Spatial Efficiency Issues
AU  - Fargier, Helene
AU  - Marquis, Pierre
AU  - Schmidt, Nicolas
T2  - Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence, IJCAI-13
PB  - AAAI Press / International Joint Conferences on Artificial Intelligence
PY  - 2013
SP  - 884
EP  - 889
UR  - https://ijcai.org/proceedings/2013/136
ER  -