Skip to Main content Skip to Navigation
New interface
Reports (Research report)

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 (Research report)
Complete list of metadata

Cited literature [18 references]  Display  Hide  Download

https://hal.inria.fr/inria-00629657
Contributor : Nadjib Lazaar Connect in order to contact the contributor
Submitted on : Friday, October 7, 2011 - 11:03:21 AM
Last modification on : Wednesday, October 26, 2022 - 8:16:34 AM
Long-term archiving on: : 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

296

Files downloads

225