Lionel PARIS

Membre de l'équipe INCA   Fonction : Attaché temporaire d'enseignement et de recherche, Post-doctorant (ATER post-doc.) UFR : Université de Provence (U1)   Tél. : 04 91 11 35 47 E-mail : lionelparislsisorg Web : http://www.cmi.univ-mrs.fr/~lparis   Adresse :  LSIS - UMR CNRS 6168 Domaine Universitaire de Saint-Jérôme Avenue Escadrille Normandie-Niemen 13397 MARSEILLE CEDEX 20

	Thèse soutenue vendredi 09 novembre 2007, à 14h30 - CMI, salle C01 Approches pour les problèmes SAT et CSP : ensembles strong backdoor, voisinage consistant et forme normale généralisée

THÈSE

Sujet de thèse : Un cadre théorique unifiant la forme clausale positionnelle et le formalisme des problèmes de satisfaction de contraintes (CSP). Directeur(s) de thèse : Pierre Siegel et Belaid Benhamou Date de début de thèse : octobre 2004 Résumé : Le but du sujet est de fournir un cadre théorique unifiant la logique propositionnelle et le formalisme des CSP. Ce cadre général doit pouvoir prendre en compte les propriétés structurelles des CSP. Il doit aussi pouvoir utiliser les propriétés et les algorithmes efficaces de SAT développés ces dernières années. Il faut donc pouvoir utiliser les deux points forts des deux formalismes. L’approche “contraintes” est un des moyens utilisé pour formaliser et résoudre des problèmes en Intelligence Artificielle. Les CSPs binaires à domaines finis discrets sont un des formalismes les plus utilisés dans ce cadre. On ne perd pas de généralité en théorie, car le problème de décision de consistance de CSP binaires est NP-complet. Mais, cette restriction aux contraintes binaires rencontre ses limites pour la formalisation et la résolution de problèmes réels. La plupart de ces problèmes s’expriment naturellement sous forme de contraintes n-aires quelconques et il est souvent difficile de leur trouver une représentation sous forme de CSP binaires. Le cadre général est plus expressif, mais les outils de résolution de CSPs n-aires sont moins développés et moins efficaces que ceux des CSP binaires. Pour traiter les CSP n-aires, deux solutions ont été proposées. • Transformer les CSPs n-aires en CSPs binaires, et utiliser les outils de CSPs binaires; • Généraliser les techniques de résolution de CSPs binaires aux CSPs n-aires. La deuxième approche est plus prometteuse, mais n’a pas encore donné de résultats satisfaisant. Une troisième voie originale que nous voulons suivre consiste à coder toute instance CSP n-aires en un ensemble de clauses propositionnelles généralisées. Les techniques classiques de SAT peuvent être adaptées à la résolution des instances exprimées dans cette formalisation.

PUBLICATIONS

[ présentation : catégorie > année / année > catégorie / compacte / BibTeX ]

@inproceedings {Paris08, audience = {nationale}, author = {Lionel Paris}, title = {Approches pour les probl\`{e}mes SAT et CSP : ensembles strong backdoor, voisinage consistant et forme normale g\'{e}n\'{e}ralis\'{e}e}, booktitle = {Acte du 9\`{e}me congr\`{e}s de la soci\'{e}t\'{e} Fran\c{c}aise de Recherche Op\'{e}rationnelle de d'Aide \`{a} la D\'{e}cision (ROADEF'08)}, pages = {355--356}, address = {Clermont-Ferrand, France}, month = {25--27 F\'{e}vrier}, year = {2008}, equipe = {INCA} }

@inproceedings {OstrowskiParis08, audience = {nationale}, author = {Richard Ostrowski and Lionel Paris}, title = {Des cha\^{i}nes d'\'{e}quivalences dans un codage CNF du probl\`{e}me XSAT}, booktitle = {Actes des quatri\`{e}mes Journ\'{e}es Francophones de Programmation par Contraintes (JFPC’2008)}, address = {Nantes, France}, month = {juin}, year = {2008}, equipe = {INCA} }

@inproceedings {ParisOstrowskiSiegelSais07, audience = {internationale}, author = {Lionel Paris and Richard Ostrowski and Pierre Siegel and Lakhdar Sa"Is}, title = {From Horn Strong Backdoor Sets to Ordered Strong BAckdoor Sets}, booktitle = {Proceedings of the 6th Mexican International Conference on Artificial Intelligence (MICAI'07)}, editor = {A. Gelbukh and A.F. Kuri Morales}, series = {LNAI}, volume = {4827}, pages = {105--117}, publisher = {Springer-Verlag}, address = {Aguascalientes, Mexico}, month = {novembre}, year = {2007}, equipe = {INCA} }

@inproceedings {HabetParisBenhamou07, audience = {internationale}, author = {Djamal Habet and Lionel Paris and Belaid Benhamou}, title = {Consistent Neighborhood for the Satisfiability Problem}, booktitle = {Proceedings of the 19th International Conference on Tools with Artificial Intelligence (ICTAI'07)}, pages = {497--501}, publisher = {IEEE}, address = {Patras, Greece}, month = {novembre}, year = {2007}, equipe = {INCA} }

@phdthesis {Paris07, author = {Lionel Paris}, title = {Approches pour les probl\`{e}mes SAT et CSP : ensembles strong backdoor, voisinage consistant et forme normale g\'{e}n\'{e}ralis\'{e}e}, school = {Universit\'{e} de Provence}, month = {9 novembre}, year = {2007}, equipe = {INCA} }

@inproceedings {ParisOstrowski07, audience = {nationale}, author = {Lionel Paris and Richard Ostrowski}, title = {De la sous-formule polynomiale maximale aux ensembles strong backdoors}, booktitle = {Actes des 8e Rencontres des Jeunes Chercheurs en Intelligence Artificielle (RJCIA'07)}, editor = {Bruno Zanuttini}, pages = {163--178}, address = {Grenoble, France}, month = {juillet}, year = {2007}, equipe = {INCA} }

@inproceedings {ParisOstrowskiSiegel07, audience = {nationale}, author = {Lionel Paris and Richard Ostrowski and Pierre Siegel}, title = {Des ensembles Horn strong backdoor aux ensembles ordonn\'{e} strong backdoor}, booktitle = {Actes des troisi\`{e}mes Journ\'{e}es Francophones de Programmation par Contraintes (JFPC’2007)}, pages = {48--57}, address = {Rocquencourt, France}, month = {juin}, year = {2007}, equipe = {INCA} }

@inproceedings {ParisHabetBenhamou07, audience = {nationale}, author = {Lionel Paris and Djamal Habet and Bela\"{i}d Benhamou}, title = {Voisinage consistant pour le probl\`{e}me de satisfaisabilit\'{e}}, booktitle = {Actes des troisi\`{e}mes Journ\'{e}es Francophones de Programmation par Contraintes (JFPC’2007)}, pages = {58--66}, address = {Rocquencourt, France}, month = {juin}, year = {2007}, equipe = {INCA} }

@inproceedings {ParisOstrowskiSaisSiegel06b, audience = {internationale}, author = {Lionel Paris and Richard Ostrowski and Lakhdar Sa\"{i}s and Pierre Siegel}, title = {Computing Horn Strong Backdoor Sets Thanks to Local Search}, booktitle = {Proceedings of the 18th International Conference on Tools with Artificial Intelligence (ICTAI'06)}, pages = {139--143}, publisher = {IEEE Computer Society}, address = {Washington D.C., United States}, month = {november, 13--15}, year = {2006}, equipe = {INCA} }

@inproceedings {Paris06, audience = {nationale}, author = {Lionel Paris}, title = {Calcul et exploitation d’ensembles Horn strong backdoor}, booktitle = {Actes de la 4\`{e}me Manifestation des Jeunes Chercheurs en Sciences et Technologies de l'Information et de la Communication (MajecStic'06)}, pages = {8}, address = {Lorient, France}, month = {november 22--24}, year = {2006}, equipe = {INCA} }

@inproceedings {ParisBenhamouSiegel06, audience = {internationale}, author = {Lionel Paris and Bela\"{i}d Benhamou and Pierre Siegel}, title = {A Boolean encoding including SAT and n-ary CSPs}, booktitle = {Proceedings of The Twelfth International Conference on Artificial Intelligence: Methodology, Systems, Applications (AIMSA 2006)}, editor = {Springer}, series = {LNAI}, number = {4183}, pages = {33--44}, address = {Varna, Bulgaria}, month = {Septembre}, year = {2006}, equipe = {INCA} }

@inproceedings {BenhamouParisSiegel06, audience = {internationale}, author = {Bela\"{i}d Benhamou and Lionel Paris and Pierre Siegel}, title = {Dealing with SAT and CSPs in a single framework}, booktitle = {Proceedings of the The CP 2006 Workshop on the Integration of SAT and CP techniques}, pages = {65--79}, address = {Nantes, France}, month = {September 25}, year = {2006}, equipe = {INCA} }

@inproceedings {ParisOstrowskiSaisSiegel06, audience = {nationale}, author = {Lionel Paris and Richard Ostrowski and Lakhdar Sa\"{i}s and Pierre Siegel}, title = {Approximation d'ensembles Horn strong backdoor par recherche locale}, booktitle = {Actes des deuxi\`{e}mes Journ\'{e}es Francophones de Programmation par Contraintes (JFPC’2006)}, pages = {277--284}, address = {N\^{i}mes, France}, month = {Juin 7--9}, year = {2006}, equipe = {INCA} }

@inproceedings {ParisBenhamouSiegel05a, audience = {nationale}, author = {Lionel Paris and Bela\"{i}d Benhamou and Pierre Siegel}, title = {Un cadre th\'{e}orique et pratique commun aux formalismes SAT et CSP n-aires}, booktitle = {7e Rencontres Jeunes Chercheurs en Intelligence Artificielle (RJCIA'05)}, pages = {169--182}, address = {Nice, France}, month = {juin 1--3}, year = {2005}, equipe = {INCA} }

@inproceedings {ParisBenhamouSiegel05, audience = {internationale}, author = {Lionel Paris and Bela\"{i}d Benhamou and Pierre Siegel}, title = {A Cardinality General Normal Form (CGNF) in propositional logic including n-ary CSPs.}, booktitle = {Joint Annual Workshop of ERCIM/CoLogNet on Constraint Solving and Constraint Logic Programming (CSCLP'05)}, pages = {89--100}, address = {Uppsala, Sweden}, month = {June 20--22}, year = {2005}, equipe = {INCA} }

webmaster