Negation for Free!

Nadjib Lazaar 1 Nourredine Aribi 2 Arnaud Gotlieb 1 Yahia Lebbah 2, 3
1 CELTIQUE - Software certification with semantic analysis
Inria Rennes – Bretagne Atlantique , IRISA-D4 - LANGAGE ET GÉNIE LOGICIEL
3 Laboratoire d'Informatique, Signaux, et Systèmes de Sophia-Antipolis (I3S) / Equipe CEP
Laboratoire I3S - MDSC - Modèles Discrets pour les Systèmes Complexes
Abstract : Global constraint design is a key success of CP for solving hard combinatorial problems. Many works suggest that automaton-based definitions and filtering make easier the design of new global constraints. In this paper, from such a design, we present an approach that gives an automaton-based definition of the NEGATION of a global constraint... for free! For a given global constraint C, the idea lies in giving operators for computing an automaton that recognizes only tuples that are not solution of C, and use the REGULAR global constraint to automatically reason on this automaton. We implemented this approach for automaton-based global constraints, including global contiguity and lex constraints, and got experimental results that show that their automatically computed negation is highly competitive with more syntactic transformations.
Document type :
Reports
Liste complète des métadonnées

Cited literature [18 references]  Display  Hide  Download

https://hal.inria.fr/inria-00629657
Contributor : Nadjib Lazaar <>
Submitted on : Friday, October 7, 2011 - 11:03:21 AM
Last modification on : Sunday, December 16, 2018 - 10:42:02 AM
Document(s) archivé(s) le : Tuesday, November 13, 2012 - 3:26:06 PM

Files

RR-7749.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00629657, version 1

Citation

Nadjib Lazaar, Nourredine Aribi, Arnaud Gotlieb, Yahia Lebbah. Negation for Free!. [Research Report] RR-7749, INRIA. 2011, pp.16. ⟨inria-00629657⟩

Share

Metrics

Record views

590

Files downloads

457