@inproceedings{DFJLOT-flairs-03,
author = {Romuald Debruyne and G{\'e}rard Ferrand and Narendra Jussien and
Willy Lesaint and Samir Ouis and Alexandre Tessier},
title = {Correctness of Constraint Retraction Algorithms},
booktitle = {{FLAIRS'03}: Sixteenth international Florida Artificial Intelligence
Research Society conference},
year = {2003},
editor = {Ingrid Russell and Susan Haller},
pages = {172--176},
address = {St Augustin, Florida, USA},
month = {May},
publisher = {AAAI Press},
__markedentry = {[lesaint:3]},
abstract = {In this paper, we present a general scheme for incremental constraint
retraction algorithms that encompasses all existing algorithms. Moreover,
we introduce some necessary conditions to ensure the correctness
of any incremental constraint retraction algorithms. This rather
theoretical work is based on the notion of explanation for constraint
programming and is exemplified within the PALM system: a constraint
solver allowing dynamic constraint retractions.},
key = {DFJLOT 03},
pdf = {http://www.univ-orleans.fr/lifo/Members/lesaint/publis/flairs2003.pdf},
url = {https://hal.archives-ouvertes.fr/hal-00085555}
}
@techreport{DFJLOT-RR2002-09,
author = {Romuald Debruyne and G{\'e}rard Ferrand and Narendra Jussien and
Willy Lesaint and Samir Ouis and Alexandre Tessier},
title = {Correctness of Constraint Retraction Algorithms},
institution = {LIFO, University of Orl{\'e}ans},
year = {2002},
type = {Research Report},
number = {2002-09},
address = {BP 6759, F-45067 Orl{\'e}ans Cedex 2},
month = {May},
__markedentry = {[lesaint:3]},
abstract = {Using a filtering technique is crucial to reduce the search space.
Most of the solvers (CHIP, GNU-Prolog, ILOG Solver, CHOCO) use reduction
operators and a propagation mechanism to enforce a local consistency.
This scheme is quite universally used on static CSPs. But we do not
have such an unanimity when relaxing constraints. Several techniques
have been proposed to deal with dynamicity. The problem we address
here is two-fold. First, we highlight that it is possible to generalize
the proposed techniques to relax constraints. Second, we show a sufficient
work to do in order to incrementally relax a constraint.},
key = {DFJLOTrr 02},
ps = {http://www.univ-orleans.fr/lifo/Members/lesaint/publis/RR2002-09.ps.gz}
}
@techreport{DFJLOT-RREMN-02,
author = {Romuald Debruyne and G{\'e}rard Ferrand and Narendra Jussien and
Willy Lesaint and Samir Ouis and Alexandre Tessier},
title = {Correctness of Constraint Retraction Algorithms},
institution = {{\'E}cole des Mines de Nantes},
year = {2002},
type = {Research Report},
number = {02-6-INFO},
address = {Nantes, France},
__markedentry = {[lesaint:3]},
abstract = {Using a filtering technique is crucial to reduce the search space.
Most of the solvers (CHIP, GNU-Prolog, ILOG Solver, CHOCO) use reduction
operators and a propagation mechanism to enforce a local consistency.
This scheme is quite universally used on static CSPs. But we do not
have such an unanimity when relaxing constraints. Several techniques
have been proposed to deal with dynamicity. The problem we address
here is two-fold. First, we highlight that it is possible to generalize
the proposed techniques to relax constraints. Second, we show a sufficient
work to do in order to incrementally relax a constraint.},
key = {DFJLOT 02},
pdf = {http://www.emn.fr/jussien/publications/debruyne-RR0206.pdf}
}
@inproceedings{DDLP-fg-2010,
author = {{D}uchier, {D}enys and {D}ao, {T}hi-{B}ich-{H}anh and {P}armentier,
{Y}annick and {L}esaint, {W}illy},
title = {{P}roperty {G}rammar {P}arsing {S}een as a {C}onstraint {O}ptimization
{P}roblem},
booktitle = {{P}roceedings of the 15th {I}nternational {C}onference on {F}ormal
{G}rammar ({FG} 2010) {P}roceedings of the 15th {I}nternational {C}onference
on {F}ormal {G}rammar ({FG} 2010)},
year = {2010},
address = {{C}openhagen {D}anemark},
month = {August},
__markedentry = {[lesaint:3]},
abstract = {{B}lache (2000) introduced {P}roperty {G}rammar as a formalism where
linguistic information is represented in terms of non hierarchical
constraints. {T}his feature gives it an adequate expressive power
to handle complex linguistic phenomena, such as long distance dependencies,
and also agrammatical sentences ({B}lache, 2004). {R}ecently, {D}uchier
et al. (2009) proposed a model-theoretic semantics for property grammar.
{T}he present paper follows up on that work and explains how to turn
such a formalization into a constraint optimization problem, solvable
using constraint programming techniques. {T}his naturally leads to
an implementation of a fully constraint-based parser for property
grammars.},
hal_id = {hal-00504684},
key = {DDLPf 2010},
url = {http://hal.archives-ouvertes.fr/hal-00504684/en/}
}
@inproceedings{DDLP-jfpc-2010,
author = {{D}uchier, {D}enys and {D}ao, {T}hi-{B}ich-{H}anh and {P}armentier,
{Y}annick and {L}esaint, {W}illy},
title = {{U}ne mod{\'e}lisation en {CSP} des grammaires de propri{\'e}t{\'e}s},
booktitle = {{S}ixi{\`e}mes {J}ourn{\'e}es {F}rancophones de {P}rogrammation par
{C}ontraintes ({JFPC} 2010) {S}ixi{\`e}mes {J}ourn{\'e}es {F}rancophones
de {P}rogrammation par {C}ontraintes ({JFPC} 2010) },
year = {2010},
address = {{C}aen {F}rance},
month = {June},
__markedentry = {[lesaint:3]},
abstract = {{L}es {G}rammaires de {P}ropri{\'e}t{\'e}s ({GP}) constituent un formalisme
{\`a} base de contraintes capable de d{\'e}crire {\`a} la fois des
{\'e}nonc{\'e}s bien-form{\'e}s et des {\'e}nonc{\'e}s agrammaticaux,
ce qui en fait un formalisme particuli{\`e}rement int{\'e}ressant
pour traiter de la gradience de grammaticalit{\'e}, comme l'a d{\'e}montr{\'e}
{P}rost (2008). {D}uchier et al (2009) ont d{\'e}fini une s{\'e}mantique
des grammaires de propri{\'e}t{\'e}s en th{\'e}orie des mod{\`e}les.
{C}et article poursuit ce travail en montrant comment, {\`a} partir
de cette s{\'e}mantique, d{\'e}finir l'analyse syntaxique en {GP}
sous la forme d'un {P}robl{\`e}me de {S}atisfaction de {C}ontraintes
({CSP}), traitable au moyen de la programmation par contraintes.},
hal_id = {hal-00482680},
key = {DDLPj 2010},
pdf = {http://jfpc2010.greyc.fr/articles/11.pdf},
url = {http://hal.archives-ouvertes.fr/hal-00482680/en/}
}
@inproceedings{FerLesTes-aadebug-00,
author = {G{\'e}rard Ferrand and Willy Lesaint and Alexandre Tessier},
title = {Value Withdrawal Explanation in {CSP}},
booktitle = {Proceedings of the Fourth International Workshop on Automated Debugging},
year = {2000},
editor = {Mireille Ducass{\'e}},
address = {Munich, Germany},
month = {August},
__markedentry = {[lesaint:3]},
abstract = {This work is devoted to constraint solving motivated by the debugging
of constraint logic programs a la GNU-Prolog. The paper focuses only
on the constraints. In this framework, constraint solving amounts
to domain reduction. A computation is formalized by a chaotic iteration.
The computed result is described as a closure. This model is well
suited to the design of debugging notions and tools, for example
failure explanations or error diagnosis. In this paper we detail
an application of the model to an explanation of a value withdrawal
in a domain. Some other works have already shown the interest of
such a notion of explanation not only for failure analysis.},
key = {FLTw 00},
optnote = {http://xxx.lanl.gov/html/cs/0010035},
pdf = {http://www.univ-orleans.fr/lifo/Members/lesaint/publis/aadebug2000.pdf},
url = {https://hal.archives-ouvertes.fr/hal-00459217}
}
@inproceedings{FerLesTes-wflp-02,
author = {G{\'e}rard Ferrand and Willy Lesaint and Alexandre Tessier},
title = {Theoretical Foundations of Value Withdrawal Explanations for Domain
Reduction},
booktitle = {11th International Workshop on Functional and (Constraint) Logic
Programming},
year = {2002},
editor = {Moreno Falashi},
pages = {211--224},
address = {Grado, Italy},
month = {June},
__markedentry = {[lesaint:3]},
abstract = {Solvers on finite domains use local consistency notions to remove
values from the domains. This paper defines value withdrawal explanations.
Domain reduction is formalized with chaotic iterations of monotonic
operators. To each operator is associated its dual which will be
described by a set of rules. For classical consistency notions, there
exists a natural such system of rules. They express value removals
as consequences of other value removals. The linking of these rules
inductively defines proof trees. Such a proof tree clearly explains
the removal of a value (the root of the tree). Explanations can be
considered as the essence of domain reduction.},
key = {FLTw 02},
optnote = {Research Report UDMI/18/2002/RR, Universit{\`a} degli Studi di Udine},
pdf = {http://www.univ-orleans.fr/lifo/Members/lesaint/publis/wflp2002.pdf},
url = {https://hal.archives-ouvertes.fr/hal-00459199}
}
@inproceedings{FerLesTes-jfplc-04,
author = {G{\'e}rard Ferrand and Willy Lesaint and Alexandre Tessier},
title = {Explications pour Comprendre la Trace d'un Solveur de Contraintes
sur Domaines Finis},
booktitle = {Treizi{\`e}mes Journ{\'e}es Francophones de Programmation en Logique
et de programmation par Contraintes},
year = {2004},
editor = {Fr{\'e}d{\'e}ric Mesnard},
pages = {37--53},
address = {Angers, France},
month = {June},
publisher = {HERMES},
__markedentry = {[lesaint:3]},
abstract = {Certains travaux en cours sur les solveurs de contraintes dans les
domaines finis concernent l'implantation d'une trace XML du calcul,
selon la DTD OADymPPaC (par exemple en GNU-Prolog, PaLM, CHIP). A
cause de la grande taille des traces, m{\^e}me pour de petits exemples
jouets, on a besoin d'outils pour comprendre cette trace. Des explications
de retrait de valeurs (ou nogoods) pendant la r{\'e}duction de domaine
sont utilis{\'e}es par certains solveurs en programmation par contraintes
dans l es domaines finis. Dans ce papier, nous utilisons une formalisation
des explications par des arbres de preuve dans un cadre point fixe
bas{\'e} sur l'it{\'e}ration d'op{\'e}rateurs monotones de consistance
locale. Les arbres de preuve donnent une vue d{\'e}clarative des
calculs par propagation de contrainte. Nous montrons comment des
explications peuvent {\^e}tre extraites de fa\c{c}on naturelle du
format de trace OADymPPaC. Les explications permettent une meilleure
compr{\'e}hension des r{\'e}ductions de domaine dans la trace.},
key = {FLTj 04},
pdf = {http://www.univ-orleans.fr/lifo/Members/lesaint/publis/jfplc2004.pdf},
url = {https://hal.archives-ouvertes.fr/hal-00085554}
}
@inproceedings{FerLesTes-wlpe-04,
author = {G{\'e}rard Ferrand and Willy Lesaint and Alexandre Tessier},
title = {Explanations to Understand the Trace of a Finite Domain Constraint
Solver},
booktitle = {14th Workshop on Logic Programming Environments},
year = {2004},
editor = {Susana Mu{\~n}oz-Hern{\'a}ndez and Jos{\'e} Manuel G{\'o}mez-P{\'e}rez
and Petra Hofstedt},
pages = {19--33},
address = {Saint-Malo, France},
month = {September},
__markedentry = {[lesaint:3]},
abstract = {Some works in progress on finite domain constraint solvers concern
the implementation of a XML trace of the computation according to
the OADymPPaC DTD (for example in GNU-Prolog, PaLM, CHIP). Because
of the large size of traces, even for small toy problems, some tools
are needed to understand this trace. Explanations of value withdrawal
(or nogoods) during domain reduction are used by some solvers in
finite domain constraint programming. In this paper, we use a formalization
of explanations by proof trees in a fixpoint framework based on iteration
of monotonic local consistency operators. Proof trees provide a declarative
view of the computations by constraint propagation. We show how explanations
may be naturally extracted from the OADymPPaC trace format. Explanations
allow a better understanding of the domain reductions in the trace.},
key = {FLT 04},
pdf = {http://www.univ-orleans.fr/lifo/Members/lesaint/publis/wlpe2004.pdf},
url = {https://hal.archives-ouvertes.fr/hal-00085550}
}
@inproceedings{FerLesTes-aadebug-03,
author = {G{\'e}rard Ferrand and Willy Lesaint and Alexandre Tessier},
title = {Towards Declarative Diagnosis of Constraint Programs over Finite
Domains},
booktitle = {Proceedings of the Fifth International Workshop on Automated Debugging,
AADEBUG2003},
year = {2003},
editor = {Michiel Ronsse},
pages = {159--170},
address = {Ghent, Belgium},
month = {September},
__markedentry = {[lesaint:3]},
abstract = {The paper proposes a theoretical approach of the debugging of constraint
programs based on a notion of explanation tree. The proposed approach
is an attempt to adapt algorithmic debugging to constraint programming.
In this theoretical framework for domain reduction, explanations
are proof trees explaining value removals. These proof trees are
defined by inductive definitions which express the removals of values
as consequences of other value removals. Explanations may be considered
as the essence of constraint programming. They are a declarative
view of the computation trace. The diagnosis consists in locating
an error in an explanation rooted by a symptom.},
key = {FLT 03},
pdf = {http://www.univ-orleans.fr/lifo/Members/lesaint/publis/aadebug2003.pdf},
url = {https://hal.archives-ouvertes.fr/hal-00459189}
}
@inproceedings{FerLesTes-exact-05,
author = {G{\'e}rard Ferrand and Willy Lesaint and Alexandre Tessier},
title = {Explanations and Proof Trees},
booktitle = {International Symposium on Explanation-Aware Computing, ExaCt 2005},
year = {2005},
editor = {Thomas R. Roth-Berghofer and Stefan Schultz and Andrea Woody},
pages = {76--85},
address = {Washington, D.C., USA},
month = {November},
publisher = {AAAI Press},
__markedentry = {[lesaint:3]},
abstract = {This paper proposes a model for explanations in a set theoretical
framework using the notions of closure or fixpoint. In this approach,
sets of rules associated with monotonic operators allow to define
proof trees. The proof trees may be considered as a declarative view
of the trace of a computation. We claim they are explanations of
the result of a computation. First, the general scheme is given.
Then, it is applied to Constraint Logic Programming, next to Constraint
Satisfaction Problems.},
key = {FLTe 05},
pdf = {http://www.univ-orleans.fr/lifo/Members/lesaint/publis/exact2005.pdf},
url = {https://hal.archives-ouvertes.fr/hal-00085549}
}
@article{FerLesTes-cai-06,
author = {G{\'e}rard Ferrand and Willy Lesaint and Alexandre Tessier},
title = {Explanations and Proof Trees},
journal = {Computing and Informatics},
year = {2006},
volume = {25},
pages = {1001--1021},
number = {2-3},
__markedentry = {[lesaint:3]},
abstract = {This paper proposes a model for explanations in a set theoretical
framework using the notions of closure or fixpoint. In this approach,
sets of rules associated with monotonic operators allow to define
proof trees. The proof trees may be considered as a declarative view
of the trace of a computation. We claim they are explanations of
the results of a computation. This notion of explanation is applied
to constraint logic programming, and it is used for declarative error
diagnosis. It is also applied to constraint programming, and it is
used for constraint retraction.},
key = {FLT 06},
pdf = {http://www.univ-orleans.fr/lifo/Members/lesaint/publis/cai2006.pdf},
url = {https://hal.archives-ouvertes.fr/hal-00085545}
}
@unpublished{FerLesTes-oadimpac-03,
author = {G{\'e}rard Ferrand and Willy Lesaint and Alexandre Tessier},
title = {Explanations and Error Diagnosis},
note = {Outils pour l'Analyse Dynamique et la mise au Point de Programmes
avec Contraintes (r{\'e}alisation d3.2.2)},
month = {March},
year = {2003},
__markedentry = {[lesaint:3]},
abstract = {The report proposes a theoretical approach of the debugging of constraint
programs based on the notion of explanation tree (D1.1.1 and D1.1.2
part 2). The proposed approach is an attempt to adapt algorithmic
debugging to constraint programming. In this theoretical framework
for domain reduction, explanations are proof trees explaining value
removals. These proof trees are defined by inductive definitions
which express the removals of values as consequence of other value
removals. Explanations may be considered as the essence of constraint
programming. They are a declarative view of the computation trace.
The diagnosis consists in locating an error in an explanation rooted
by a symptom.},
key = {FLTo 03},
pdf = {http://www.univ-orleans.fr/lifo/Members/lesaint/publis/d3-2-2.pdf},
type = {R{\'e}alisation OADymPPaC}
}
@article{FerLesTes-entcs-02,
author = {G{\'e}rard Ferrand and Willy Lesaint and Alexandre Tessier},
title = {Theoretical Foundations of Value Withdrawal Explanations for Domain
Reduction},
journal = {Electronic Notes in Theoretical Computer Science},
year = {2002},
volume = {76},
month = {November},
__markedentry = {[lesaint:3]},
abstract = {Solvers on finite domains use local consistency notions to remove
values from the domains. This paper defines value withdrawal explanations.
Domain reduction is formalized with chaotic iterations of monotonic
operators. To each operator is associated its dual which will be
described by a set of rules. For classical consistency notions, there
exists a natural such system of rules. They express value removals
as consequences of other value removals. The linking of these rules
inductively defines proof trees. Such a proof tree clearly explains
the removal of a value (the root of the tree). Explanations can be
considered as the essence of domain reduction.},
key = {FLT 02},
optnote = {http://www.elsevier.com/gej-ng/31/29/23/126/23/26/76008.pdf},
pdf = {http://www.univ-orleans.fr/lifo/Members/lesaint/publis/entcs2002.pdf},
publisher = {Elsevier},
url = {https://hal.archives-ouvertes.fr/hal-00514500}
}
@unpublished{FerLesTes-oadimpac-02,
author = {G{\'e}rard Ferrand and Willy Lesaint and Alexandre Tessier},
title = {Un Mod{\`e}le Complet pour la Propagation et le Labeling},
note = {Outils pour l'Analyse Dynamique et la mise au Point de Programmes
avec Contraintes (r{\'e}alisation d1.1.2-part2)},
month = {February},
year = {2002},
__markedentry = {[lesaint:3]},
abstract = {Ce rapport a pour but de fournir un modèle théorique
pour la propagation et le labeling. Ce modèle est adapté
aux solveurs sur domaines finis utilisés par chacun des partenaires
du projet: GNU-Prolog (INRIA), CHIP (Cosytec) et Choco (EMN). Un
calcul est formalisé par un arbre dans lequel chaque branche
correspondà une itération chaotique d'opérateurs
et où chaque feuille peut-être décrite en terme
de clôture. Ce modèle est bien adapté aux notions
d'explications qui seront utiles pour la mise au point de programmes
avec contraintes. Ce rapport fait suite à la réalisation
d1.1.1 qui traitait de la réduction de domaine. Il sera étendu
pour inclure un langage hôte dans la prochaine réalisation.},
key = {FLTo 02},
pdf = {http://www.univ-orleans.fr/lifo/Members/lesaint/publis/d1-1-2.pdf},
type = {R{\'e}alisation OADymPPaC}
}
@unpublished{FerLesTes-oadimpac-01,
author = {G{\'e}rard Ferrand and Willy Lesaint and Alexandre Tessier},
title = {A Model of Constraint Solvers by Chaotic Iteration Adapted to Value
Withdrawal Explanations},
note = {Outils pour l'Analyse Dynamique et la mise au Point de Programmes
avec Contraintes (r{\'e}alisation d1.1.1)},
month = {July},
year = {2001},
__markedentry = {[lesaint:3]},
abstract = {The aim of this report is to provide the theoretical foundations of
domain reduction. The model is well suited to the solvers on finite
domains which are used on the respective platforms of each partner
of the project: GNU-Prolog (INRIA), CHIP (COSYTEC) and PaLM (EMN).
A computation is formalized by a chaotic iteration of operators and
the result is described as a closure. The model is well suited to
the definition of traces and explanations which will be useful for
the debugging of constraint programs. This report only deals with
the reduction stage. It will be extended to the labeling and the
host language in next reports.},
key = {FLTo 01},
pdf = {http://www.univ-orleans.fr/lifo/Members/lesaint/publis/d1-1-1.pdf},
type = {R{\'e}alisation OADymPPaC}
}
@techreport{FerLesTes-RR2001-05,
author = {G{\'e}rard Ferrand and Willy Lesaint and Alexandre Tessier},
title = {Theoretical Foundations of Value Withdrawal Explanations in Constraints
Solving by Domain Reduction},
institution = {LIFO, University of Orl{\'e}ans},
year = {2001},
type = {Research Report},
number = {2001-05},
address = {BP 6759, F-45067 Orl{\'e}ans Cedex 2},
month = {November},
__markedentry = {[lesaint:3]},
abstract = {Constraint programming is an important programming paradigm of the
last years. It combines declarativity and efficiency thanks to constraint
solvers which are implemented for specific domains. We are interested
here in the case of reduction of finite domains. In the paper, it
is formalized with chaotic iterations of monotonic operators. A first
notion of explanation, which have been proved very useful in many
applications, is then defined in a declarative way in terms of closure.
An explanation set for a value removal is a set of operators which
always remove this value whatever the order of application of these
operators is. A monotonic operator can always be defined by a set
of rules (in the sense of inductive definition of Aczel). Furthermore,
the paper shows that for classical notions of local consistency,
such a system of rules can be expressed in a natural way. They express
value removals as consequences of other value removals. So, a more
precise notion of explanation can be obtained: the linking of these
rules allows to inductively define proof trees. Such a proof tree
clearly explains the removal of a value (the root of the tree) by
the solver, it is then called an explanation for this value withdrawal.
Explanations are the essence of domain reduction.},
key = {FLTrr 01},
ps = {http://www.univ-orleans.fr/lifo/Members/lesaint/publis/RR2001-05.ps.gz}
}
@techreport{FerLesTes-RR2000-09,
author = {G{\'e}rard Ferrand and Willy Lesaint and Alexandre Tessier},
title = {Value Withdrawal Explanation in {CSP}},
institution = {LIFO, University of Orl{\'e}ans},
year = {2000},
type = {Research Report},
number = {2000-09},
address = {BP 6759, F-45067 Orl{\'e}ans Cedex 2},
month = {May},
__markedentry = {[lesaint:3]},
abstract = {This work is devoted to constraint solving motivated by the debugging
of constraint logic programs a la GNU-Prolog. The paper focuses only
on the constraints. In this framework, constraint solving amounts
to domain reduction. A computation is formalized by a chaotic iteration.
The computed result is described as a closure. This model is well
suited to the design of debugging notions and tools, for example
failure explanations or error diagnosis. In this paper we detail
an application of the model to an explanation of a value withdrawal
in a domain. Some other works have already shown the interest of
such a notion of explanation not only for failure analysis.},
key = {FLTrr 00}
}
@conference{Langevine2005,
author = {Langevine, L. and Deransart, P. and Fages, F. and Fekete, J.-D. and
Ghoniem, M. and Jussien, N. and Ducassé, M. and Jahier, E. and Tessier,
A. and Lesaint, W. and Ferrand, G. and Ed-Dbali, A.},
title = {Gentra4cp: A generic trace format for constraint programming},
year = {2005},
volume = {3668},
pages = {433-434},
note = {cited By (since 1996)0},
__markedentry = {[lesaint:6]},
document_type = {Conference Paper},
journal = {Lecture Notes in Computer Science},
owner = {lesaint},
pdf = {http://www.univ-orleans.fr/lifo/Members/lesaint/publis/iclp05-poster.pdf},
source = {Scopus},
timestamp = {2014.11.12},
url = {http://www.scopus.com/inward/record.url?eid=2-s2.0-27144489063&partnerID=40&md5=d45bc4110a239eea0ca3b822ec151af6}
}
@inproceedings{Lesaint-wlpe-02,
author = {Willy Lesaint},
title = {Value Withdrawal Explanations: a Theoretical Tool for Programming
Environments},
booktitle = {12th Workshop on Logic Programming Environments},
year = {2002},
editor = {Alexandre Tessier},
pages = {17--33},
address = {Copenhagen, Denmark},
month = {July},
__markedentry = {[lesaint:3]},
abstract = {Constraint logic programming combines declarativity and efficiency
thanks to constraint solvers implemented for specific domains. Value
withdrawal explanations have been efficiently used in several constraints
programming environments but there does not exist any formalization
of them. This paper is an attempt to fill this lack. Furthermore,
we hope that this theoretical tool could help to validate some programming
environments. A value withdrawal explanation is a tree describing
the withdrawal of a value during a domain reduction by local consistency
notions and labeling. Domain reduction is formalized by a search
tree using two kinds of operators: for local consistency notions
and for labeling. These operators are defined by sets of rules. Proof
trees are built with respect to these rules. For each removed value,
there exists such a proof tree which is the withdrawal explanation
of this value.},
key = {Les 02},
optnote = {http://xxx.lanl.gov/html/cs/0207052},
pdf = {http://www.univ-orleans.fr/lifo/Members/lesaint/publis/wlpe2002.pdf},
url = {https://hal.archives-ouvertes.fr/hal-00459195}
}
@phdthesis{Lesaint-phd-03,
author = {Willy Lesaint},
title = {Explications de Retraits de Valeurs en Programmation par Contraintes
et Application au Diagnostic D{\'e}claratif},
school = {Universit{\'e} d'Orl{\'e}ans},
year = {2003},
month = {Novembre},
__markedentry = {[lesaint:3]},
abstract = {Depuis quelques ann{\'e}es, la programmation par contraintes a montr{\'e}
son efficacit{\'e} pour traiter les probl{\`e}mes difficiles, tant
au point de vue de leur mod{\'e}lisation que de leur r{\'e}solution.
Quand les domaines sont finis, les probl{\`e}mes ainsi mod{\'e}lis{\'e}s
sont appel{\'e}s probl{\`e}mes de satisfaction de contraintes. Les
solveurs utilis{\'e}s pour obtenir leurs solutions m{\^e}lent des
techniques de retraits de valeurs par des notions de consistance
(la r{\'e}duction de domaine) {\`a} des techniques de recherche syst{\'e}matique
(l'{\'e}num{\'e}ration). R{\'e}cemment diff{\'e}rentes notions d'explications
ont {\'e}t{\'e} introduites, que ce soit pour am{\'e}liorer l'efficacit{\'e}
des m{\'e}thodes de l'{\'e}num{\'e}ration ou pour traiter les probl{\`e}mes
sur-contraints ou dynamiques. L'id{\'e}e est d'enregistrer de l'information
expliquant les retraits de valeurs afin de pouvoir l'utiliser, pour
{\'e}viter d'explorer tout l'arbre de recherche lors de l'{\'e}num{\'e}ration,
pour choisir une contrainte {\`a} relaxer quand un probl{\`e}me est
sur-contraint ou encore pour r{\'e}introduire des valeurs dans les
domaines quand une contrainte est relax{\'e}e. Cette th{\`e}se propose
trois contributions au domaine de la programmation par contraintes.
Tout d'abord la r{\'e}duction de domaine est formalis{\'e}e en terme
ensembliste et vue comme un calcul de point fixe. Ce cadre g{\'e}n{\'e}ral,
dans lequel l'{\'e}num{\'e}ration s'int{\`e}gre ais{\'e}ment, s'applique
{\`a} tout type de solveur effectuant de la r{\'e}duction de domaine.
De plus, il permet une d{\'e}finition naturelle d'une notion g{\'e}n{\'e}rale
d'explication: les arbres explicatifs. Ces arbres de preuve sont
inductivement d{\'e}finis par des r{\`e}gles exprimant le retrait
d'une valeur comme cons{\'e}quence d'autres retraits. Les notions
existantes d'explications peuvent ais{\'e}ment en {\^e}tre extraites.
Enfin, la structure arborescente des arbres explicatif est utilis{\'e}e
pour adapter le diagnostic d{\'e}claratif de r{\'e}ponse manquante
{\`a} la programmation par contrainte. En effet, les arbres explicatifs
peuvent {\^e}tre consid{\'e}r{\'e}s comme une trace d{\'e}clarative
du calcul du solveur et peuvent donc aider {\`a} la compr{\'e}hension
de l'absence d'une r{\'e}ponse.},
key = {Les 03},
pdf = {http://www.univ-orleans.fr/lifo/Members/lesaint/publis/these.pdf}
}
@techreport{Lesaint-dea-99,
author = {Willy Lesaint},
title = {Simplification de Contraintes sur les Domaines Finis},
institution = {LIFO, University of Orl{\'e}ans},
year = {1999},
type = {M{\'e}moire de DEA},
address = {BP 6759, F-45067 Orl{\'e}ans Cedex 2},
month = {Septembre},
__markedentry = {[lesaint:3]},
key = {Les 99}
}
This file was generated by bibtex2html 1.96.