OATAO - Open Archive Toulouse Archive Ouverte Open Access Week

Temporal Constraint Satisfaction Problems and Difference Decision Diagrams: A Compilation Map

Fargier, Hélène and Maris, Frédéric and Roger, Vincent Temporal Constraint Satisfaction Problems and Difference Decision Diagrams: A Compilation Map. (2015) In: 27th IEEE International Conference on Tools with Artificial Intelligence (ICTAI 2015), 9 November 2015 - 11 November 2015 (Vietry sul mare, Italy).

(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.1109/ICTAI.2015.71


The frameworks dedicated to the representation of quantitative temporal constraint satisfaction problems, as rich as they are in terms of expressiveness, define difficult requests - typically NP-complete decision problems. It is therefore adventurous to use them for an online resolution. Hence the idea to compile the original problem into a form that could be easily solved. Difference Decision Diagrams (DDDs) have been proposed by [1] as a possible way to cope with this difficulty, following a compilation-based approach. In this article, we draw a compilation map that evaluates the relative capabilities of these languages (TCSP, STP, DTP and DDD) in terms of algorithmic efficiency, succinctness and expressiveness.

Item Type:Conference or Workshop Item (Paper)
Additional Information:Thanks to IEEE editor. The definitive version is available at http://ieeexplore.ieee.org This papers appears in Tools with Artificial Intelligence. ISSN : 1082-3409 The original PDF of the article can be found at: http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=7372167&tag=1
HAL Id:hal-01303829
Audience (conference):International conference proceedings
Uncontrolled Keywords:
Institution:Université de Toulouse > Institut National Polytechnique de Toulouse - Toulouse INP (FRANCE)
French research institutions > Centre National de la Recherche Scientifique - CNRS (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)
Laboratory name:
Deposited On:16 Mar 2016 16:26

Repository Staff Only: item control page