OATAO - Open Archive Toulouse Archive Ouverte Open Access Week

Compiling CSPs: A Complexity Map of (Non-Deterministic) Multivalued Decision Diagrams

Amilhastre, Jérôme and Fargier, Hélène and Niveau, Alexandre and Pralet, Cedric Compiling CSPs: A Complexity Map of (Non-Deterministic) Multivalued Decision Diagrams. (2014) International Journal on Artificial Intelligence Tools, 23 (4). ISSN 0218-2130

(Document in English)

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

Official URL: http://dx.doi.org/10.1142/S021821301460015X


Constraint Satisfaction Problems (CSPs) offer a powerful framework for representing a great variety of problems. The difficulty is that most of the requests associated with CSPs are NP-hard. When these requests have to be addressed online, Multivalued Decision Diagrams (MDDs) have been proposed as a way to compile CSPs. In the present paper, we draw a compilation map of MDDs, in the spirit of the NNF compilation map, analyzing MDDs according to their succinctness and to their tractable transformations and queries. Deterministic ordered MDDs are a generalization of ordered binary decision diagrams to non-Boolean domains: unsurprisingly, they have similar capabilities. More interestingly, our study puts forward the interest of non-deterministic ordered MDDs: when restricted to Boolean domains, they capture OBDDs and DNFs as proper subsets and have performances close to those of DNNFs. The comparison to classical, deterministic MDDs shows that relaxing the determinism requirement leads to an increase in succinctness and allows more transformations to be satisfied in polynomial time (typically, the disjunctive ones). Experiments on random problems confirm the gain in succinctness.

Item Type:Article
Additional Information:Thanks to World Scientific editor. The definitive version is available at http://www.worldscientific.com/worldscinet/ijait The original PDF of the article can be found at: http://www.worldscientific.com/doi/abs/10.1142/S021821301460015X
HAL Id:hal-01303816
Audience (journal):International peer-reviewed journal
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)
French research institutions > Office National d'Etudes et Recherches Aérospatiales - ONERA (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 > Cameleon Software (FRANCE)
Other partners > Université d'Artois (FRANCE)
Laboratory name:
Deposited On:15 Mar 2016 10:18

Repository Staff Only: item control page