Reasoning about Constraint Models

Abstract : We propose a simple but powerful framework for reasoning about properties of models specified in languages like AMPL, OPL, Zinc or Essence. Using this framework, we prove that reasoning problems like detecting symme- tries, redundant constraints or dualities between models are undecidable even for a very limited modelling language that only generates simple problem in- stances. To provide tools to help the human modeller (for example, to identify when a model has a particular symmetry), it would nevertheless be useful to au- tomate many of these reasoning tasks. To explore the possibility of doing this, we describe two case-studies. The first uses the ACL2 inductive prover to prove inductively that a model contains a symmetry. The second identifies a tractable fragment of MiniZinc and uses a decision procedure to prove that a model implies a parameterized constraint.
Type de document :
Communication dans un congrès
PRICAI: Pacific Rim International Conference on Artificial Intelligence, Dec 2014, Gold Coast, Australia. 13th Pacific Rim International Conference on Artificial Intelligence, Gold Coast, QLD, Australia, December 1-5, 2014. Proceedings Pages pp 795-808, LNCS (8862), pp.795-808, 2014, PRICAI 2014: Trends in Artificial Intelligence. 〈10.1007/978-3-319-13560-1_63〉
Liste complète des métadonnées

Littérature citée [25 références]  Voir  Masquer  Télécharger

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01228300
Contributeur : Joël Quinqueton <>
Soumis le : jeudi 12 novembre 2015 - 20:03:42
Dernière modification le : mercredi 28 février 2018 - 10:23:14
Document(s) archivé(s) le : vendredi 28 avril 2017 - 04:58:51

Fichier

pricai14.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Citation

Christian Bessière, Emmanuel Hébrard, George Katsirelos, Zeynep Kiziltan, Nina Narodytska, et al.. Reasoning about Constraint Models. PRICAI: Pacific Rim International Conference on Artificial Intelligence, Dec 2014, Gold Coast, Australia. 13th Pacific Rim International Conference on Artificial Intelligence, Gold Coast, QLD, Australia, December 1-5, 2014. Proceedings Pages pp 795-808, LNCS (8862), pp.795-808, 2014, PRICAI 2014: Trends in Artificial Intelligence. 〈10.1007/978-3-319-13560-1_63〉. 〈lirmm-01228300〉

Partager

Métriques

Consultations de la notice

254

Téléchargements de fichiers

194