OATAO - Open Archive Toulouse Archive Ouverte Open Access Week

Compilation de CSPs : carte de complexité des MDDs non-déterministes

Amilhastre, Jérôme and Fargier, Hélène and Niveau, Alexandre and Pralet, Cedric Compilation de CSPs : carte de complexité des MDDs non-déterministes. (2013) In: Neuvièmes Journées Francophones de Programmation par Contraintes (JFPC 2013), 12 June 2013 - 14 June 2013 (Aix en Provence, France).

[img]
Preview
(Document in English)

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

Official URL: http://www.lsis.org/jfpc-jiaf2013/jfpc/articles/papier_28.pdf

Abstract

Les CSPs fournissent un cadre puissant pour la représentation de problèmes très divers. La difficulté est que la plupart des requêtes associées aux CSPs sont NP-difficiles, mais doivent dans certains contextes être traitées « en ligne ». C’est pour cette raison que les diagrammes de décision multivalués (MDDs) ont été proposés pour la compilation de CSPs. Cet article dresse une carte de compilation des MDDs, dans l’esprit de la carte de la famille des NNFs de Darwiche et Marquis, en analysant les MDDs selon leur compacité et les requêtes et transformations qu’ils supportent en temps polynomial. Les MDDs déterministes et ordonnés généralisant les diagrammes de décision binaire ordonnes à des variables non-booléennes, le fait que leurs propriétés soient similaires n’est pas surprenant. Cependant, notre étude met en avant l’intérêt des MDDs ordonnes non déterministes : restreint aux variables booléennes, ce fragment est strictement plus compact que ceux des OBDDs et des DNFs, et admet des performances proches de celles des DNNFs. La comparaison aux MDDs classiques montre que relâcher la contrainte du déterminisme améliore la compacité et permet a plus de transformations d’être supportées en temps polynomial. Des expériences sur des problèmes aléatoires confirment le gain en compacité.

Item Type:Conference or Workshop Item (Paper)
Additional Information:ISBN: 978-1-63266-375-7 ; http://www.lsis.org/jfpc-jiaf2013/jfpc/articles/papier_28.pdf
HAL Id:hal-01217173
Audience (conference):National 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)
French research institutions > Office National d'Etudes et Recherches Aérospatiales - ONERA (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 > Cameleon Software (FRANCE)
Other partners > Université d'Artois (FRANCE)
Laboratory name:
Statistics:download
Deposited By: IRIT IRIT
Deposited On:22 Sep 2015 09:41

Repository Staff Only: item control page