Raisonnement à partir d'informations structurées et hiérarchisées : application à l'information archéologique, Reasoning from structured and hierarchized information : application to archeological information

´ ´UNIVERSITE DE LA MEDITERRANEE - U.F.R. SCIENCES
´ ´ECOLE DOCTORALE DE MATHEMATIQUES ET
INFORMATIQUE E.D. 184
`THESE
pr´esent´ee pour obtenir le grade de
´ ´ ´Docteur de l’Universite de la Mediterranee
Sp´ecialit´e : Informatique
par
Mariette SERAYET
Raisonnement `a partir d’informations
structur´ees et hi´erarchis´ees :
Application `a l’information arch´eologique
soutenue le 6 mai 2010 devant le jury compos´e de
Marie-Odile CORDIER Professeur a` l’Universit´e de Rennes 1 (Rapporteur)
Nadia CREIGNOU a` l’Universit´e de la M´editerran´ee (Examinatrice)
´Olivier CURE Maˆıtre de conf´erence `a l’Universit´e Paris-Est (Invit´e)
Pierre DRAP Charg´e de recherche CNRS, LSIS (Co-directeur)
Antoinette HESNARD Directrice de recherche CNRS, CCJ (Examinatrice)
Sylvain LAGRUE Maˆıtre de conf´erence `a l’Universit´e d’Artois (Invit´e)
J´erˆome LANG Directeur de recherche CNRS, LAMSADE (Rapporteur)
Odile PAPINI Professeur a` l’Universit´e de la M´editerran´ee (Directrice)Th`ese pr´epar´ee dans le laboratoire des Sciences de l’Information et des Syst`emes
LSIS - UMR CNRS 6168
au sein de l’universit´e de la M´editerran´ee et de l’universit´e Paul C´ezanne
et financ´ee par le projet europ´een VENUS n˚(IST-034924).A mes parents,Remerciements
En premier lieu, je souhaite remercier Marie-Odile Cordier et J´erˆome Lang pour
l’int´erˆet qu’ils ont port´e a` mon travail mais aussi pour les conseils qu’ils m’ont donn´e
pour l’am´elioration de mon manuscrit. Je remercie ´egalement Nadia Creignou et An-
toinetteHesnardpouravoiraccept´ed’ˆetremembresdujuryquiaexamin´emontravail.
JeremercieOdilePapinietPierreDrapd’avoirdirig´ecetteth`ese,dem’avoirencou-
rag´eeetdem’avoirfaitd´ecouvrirdenouveauxdomaines.Leurrigueuretleurscritiques
m’ont permis de mener `a bien ce travail.
Je tiens `a remercier ´egalement le projet europ´een VENUS dont le financement m’a
permis de r´ealiser cette th`ese. J’en profite a` ce titre pour remercier tous les partenaires
de ce projet. Je remercie Olivier Cur´e pour notre collaboration et sa pr´esence lors de
masoutenance.Jesouhaiteremercier´egalementmongrandfr`eredeth`ese,JulienS.qui
a su parfaitement jouer son rˆole. Quelques lignes ne suffiraient pas pour lui exprimer
toute ma reconnaissance.
Mes prochains remerciements vont `a Salem Benferhat, Sylvain Lagrue et Safa Yahi
duCRILdeLenspournotrecollaborationpendantcetteth`eseainsiquepourlapr´esence
de Sylvain pour ma soutenance.
Je tiens a` remercier ensuite les membres de mon ´equipe (INCA), je n’aurais pu
trouvermeilleurenvironnementdetravail.Jeremercietoutsp´ecialementPhilippepour
la confiance qu’il m’a accord´e lors des enseignements qu’il m’a confi´es pendant ces
ann´ees et Cyril T. qui a toujours ´et´e `a mon ´ecoute en tant que coll`egue et ami. Je
souhaiteremercierR´egisetC´edricP.pouravoirpartag´elebureaupendantcesderniers
moisetenparticulier,merci`aC´edricP.pourlecaf´edumatin.JeremercieEricetJulien
H. pour toutes les discussions enrichissantes que nous avons pu avoir. Travailler avec
vous tous fut un r´eel plaisir.
Lors de mon arriv´ee a` l’ESIL, j’ai ´et´e chaleureusement accueillie par l’´equipe I&M
(remerciement sp´ecial pour Bernard et sa femme) et plus particuli`erement par les
th´esards. Nous avons partag´e des bons moments lors de soir´ees ou de d´ejeuners pour
nousa´ererl’esprit.Lasolidarit´edontvousavezfaitpreuvem’abeaucouptouch´ee:merci
a`Guigui,Greg,Van,Alaa,Thomas,Ludo,Hung,Christophe,FlorianetKheiredine.Je
souhaiterais remercier sp´ecialement Adrien (mon coloc de bureau;-)) et Dimitri pour
tous les bons moments pass´es tous les trois. J’esp`ere garder votre amiti´e longtemps et
on se voit quand vous voulez pour un sandwich a` Montr´eal! Une autre personne m´erite
des remerciements sp´eciaux, V´eronique (surnomm´ee maman V´ero), elle a toujours su8 Remerciements
ˆetre a` mon ´ecoute et m’a consol´ee un nombre de fois impressionnant, elle est devenue
au fil de ces ann´ees une amie tr`es ch`ere. J’en profite´egalement pour remercier Nathalie
et Marie pour leur gentillesse et plus g´en´eralement tout le personnel de l’ESIL.
Mes plus grands remerciements vont a` mes parents. Ils m’ont toujours soutenue
et encourag´ee dans mes choix. Merci de m’avoir transmis cet esprit critique, cette
pers´ev´erance et plein d’autres choses. Un immense merci `a ma soeur, Maud, qui a
toujours su trouv´e les bons mots pour me remotiver. Tu vas enfin pouvoir dire que
ta soeur est docteur! J’en profite pour remercier Nico! Je remercie ´egalement mon
“petit” fr`ere, Cˆome et sa p´etillante Marine pour leur bonne humeur. Un grand merci
a` l’ensemble des autres membres de ma famille ainsi que mon parrain pour avoir ´et´e `a
mes cotˆ ´es.
L’aventure de la th`ese a ´et´e l’occasion de faire de belles rencontres. La plus belle
de ces rencontres reste celle de C´edric. Tu as r´eussi `a me soutenir pendant ces ann´ees
malgr´e les milliers de kilom`etres qui nous s´eparent. Je te remercie pour tout ce que
tu m’apportes. Une nouvelle aventure commence pour nous et je sais que gracˆ e a` ton
soutien, ce sera une autre belle r´eussite. J’en profite ´egalement pour remercier toute
ma belle famille, les week-ends ni¸cois ´etaient un bol d’air a` chaque fois, merci a` Jean-
Claude, Lyliane et Cynthia pour ces bons moments. Je n’oublie pas le clan des Nˆımois
pour m’avoir accueillie et divertie lors de week-ends sympathiques et inoubliables!
J’ai toujours pu compter sur mes ami(e)s qui ont su me soutenir chacun a` leur
mani`ere pendant ces ann´ees de th`ese. Corinne qui a sans cesse pris de mes nouvelles
alors que je croulais sous le travail. Je remercie ´egalement Manu, Romain, Schnob’ et
C´ecilepourtouteslesfoisou`ilsm’ont´ecout´eeetsoutenueparMSNouparmail!Merci`a
R´emi pour les bons restos que l’on a d´ecouvert sur Marseille, c’´etait un plaisir a` chaque
fois. Etant pass´e par l`a, tu m’as toujours ´ecout´ee et conseill´ee dans les moments de
doute. Un grand merci `a Claire et Elodie qui malgr´e la distance ont toujours su trouver
les mots pour m’encourager jusqu’`a la fin. Enfin, je voudrais remercier la Shrink family
sur qui j’ai toujours pu compter : Raf, Flo, Jean-Luc, Emilie, Fiona et Jack merci pour
les soir´ees, les r´eveillons, les concerts, les pique-niques, les anniversaires, ... et pour
tous les bons moments a` venir!
La derni`ere personne que je souhaite remercier est ma marraine. Elle a ´et´e pa-
radoxalement la plus pr´esente dans mes pens´ees lorsque la solitude et les doutes se
faisaient trop lourds, marraine, je ne t’oublie pas et j’esp`ere que de l`a-haut, tu es fi`ere
de moi.Table des mati`eres
Introduction 15
I Pr´eliminaires 21
1 Outils 23
1.1 Notations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
1.2 Logique propositionnelle . . . . . . . . . . . . . . . . . . . . . . . . . . 24
1.2.1 Le langage de la logique propositionnelle . . . . . . . . . . . . . . 24
1.2.2 Aspect axiomatique de la logique propositionnelle . . . . . . . . 24
1.2.3 Aspect s´emantique de la logique propositionnelle . . . . . . . . . 26
1.3 Logique des pr´edicats . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
1.3.1 Le langage de la logique des pr´edicats . . . . . . . . . . . . . . . 28
1.3.2 Aspect axiomatique de la logique des pr´edicats . . . . . . . . . . 30
1.3.3 Aspect s´emantique de la logique des pr´ . . . . . . . . . . . 31
1.4 Programmation logique avec s´emantique de mod`eles stables . . . . . . . 34
1.4.1 Programme logique normal . . . . . . . . . . . . . . . . . . . . . 34
1.4.2 basique . . . . . . . . . . . . . . . . . . . . . . . . . 34
1.4.3 avec s´emantique de mod`eles stables . . . . . . . . . . 35
1.4.4 Les solveurs ASP . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
II Etat de l’art 37
2 Restauration de la coh´erence 39
2.1 Pr´eliminaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
2.1.1 Ordres et pr´eordres. . . . . . . . . . . . . . . . . . . . . . . . . . 40
2.1.2 Bases de croyances . . . . . . . . . . . . . . . . . . . . . . . . . . 41
2.2 Sous-bases coh´erentes pr´ef´er´ees . . . . . . . . . . . . . . . . . . . . . . . 41
2.2.1 Base de croyances non ordonn´ees . . . . . . . . . . . . . . . . . . 42
2.2.2 Base de croyances totalement pr´eordonn´ees . . . . . . . . . . . . 42
2.2.3 Base de croyances partiellement pr´eordonn´ees . . . . . . . . . . . 44
2.3 Minimisation de l’incoh´erence . . . . . . . . . . . . . . . . . . . . . . . . 4610 Table des mati`eres
2.3.1 Restauration de la coh´erence et diagnostic . . . . . . . . . . . . . 46
2.3.2 de la coh´ et sous-formules minimales incon-
sistantes (MUS) . . . . .