Lifo - Laboratoire d'Informatique Fondamentale d'orléans INSA Centre Val de Loire Université d'Orléans Université d'Orléans

Lifo > Les rapports de recherche du LIFO en 2001

 English Version



Contact

LIFO - Bâtiment IIIA
Rue Léonard de Vinci
B.P. 6759
F-45067 ORLEANS Cedex 2

Email: contact.lifo
Tel: +33 (0)2 38 41 99 29
Fax: +33 (0)2 38 41 71 37



Accéder aux Rapports de l'année : 1998 1999 2000 2001 2002 2003 2004 2005 2006 2007 2008 2009 2010 2011 2012 2013 2014 2015 2016 2017 2018

Les rapports de recherche du LIFO en 2001


RR-2001-01 Cartographie de textes, une nouvelle approche pour l'exploration sémantique des corpus homogènes de grande dimension
I. DEBOURGES, S. GUILLORE-BILLOT, C. VRAIN
Date : 2001-03-07
Résumé Télécharger

RR-2001-02 Net Juggler Guide
J. ALLARD, L. LECOINTRE, V. GOURANTON, E. MELIN, B. RAFFIN
Date : 2001-06-15
Résumé Télécharger

RR-2001-03 Chordal embeddings of planar graphs
V. BOUCHITTE, F. MAZOIT, I. TODINCA
Date : 2001-10-04
Résumé Télécharger

RR-2001-04 On treewidth approximations
V. BOUCHITTE, D. KRATSCH, H. MULLER, I TODINCA
Date : 2001-10-17
Résumé Télécharger

RR-2001-05 Theoretical foundations of value withdrawal explanations in constraints solving by domain reduction
G. FERRAND, W. LESAINT, A. TESSIER
Date : 2001-11-22
Résumé Télécharger

RR-2001-06 Learning Constraints between Variables in Inductive Logic Programming
A. BRAUD, C. VRAIN
Date : 2001-12-21
Résumé Télécharger

RR-2001-07 Equational Unification, Rewrite Reachability, and Labelled Dag Automata
S. ANANTHARAMAN, P. NARENDRAN, M. RUSINOWITCH
Date : 2001-12-27
Résumé Télécharger


Résumés des rapports de recherche


RR-2001-01 Cartographie de textes, une nouvelle approche pour l'exploration sémantique des corpus homogènes de grande dimension
I. DEBOURGES, S. GUILLORE-BILLOT, C. VRAIN
Résumé : Nous présentons les avancées d'un projet dans un thème que nous qualifions de Cartographie de Textes (ou Text Mapping) qui permet à un utilisateur novice d'explorer un nouveau domaine par navigation au sein d'un corpus homogène grâce à des cartes conceptuelles interactives. Une carte est composée de concepts pertinents relativement à la requête initiale et à son évolution, au sein du corpus; des relations sémantiques ou lexicales, extraites du corpus, les lient aux mots clés de la requête. Des techniques d'Apprentissage Automatique sont combinées avec des heuristiques statistiques de Traitement Automatique des Langues pour la mise en évidence de collocations afin de construire les cartes. Un prototype implantant ces idées a été écrit et les expérimentations menées sur différents corpus de langues anglaise et francaise montrent des résultats encourageants.
Mot(s) Clé(s) : Cartographie de Textes; Recherche Documentaire; Extraction d'Information; Apprentissage Automatique

RR-2001-02 Net Juggler Guide
J. ALLARD, L. LECOINTRE, V. GOURANTON, E. MELIN, B. RAFFIN
Résumé : Net Juggler est une librairie permettant d'exécuter l'environnement de réalité virtuelle VR Juggler sur des grappes. Le Guide Net Juggler détaille l'installation, l'utilisation et la programmation de Net Juggler.
Mot(s) Clé(s) :

RR-2001-03 Chordal embeddings of planar graphs
V. BOUCHITTE, F. MAZOIT, I. TODINCA
Résumé : Robertson et Seymour ont conjecturé que la largeur arborescente d'un graphe planaire diffère de celle de son dual d'au plus une unité. Lapoire a prouvé cette conjecture, en utilisant des techniques algébriques. Nous donnons ici une preuve beaucoup plus courte de ce résultat.
Mot(s) Clé(s) : graphes planaire ; dualité ; graphes triangulé ; largeur arborescente.

RR-2001-04 On treewidth approximations
V. BOUCHITTE, D. KRATSCH, H. MULLER, I TODINCA
Résumé : Nous introduisons une heuristique naturelle pour approximer la largeur arborescente des graphes. Nous montrons que, pour les graphes ayant un nombre astéroïde borné, cette heuristique produit une approximation de la largeur arborescente à une constante multiplicative près. Par une technique complètement différente, nous donnons un algorithme qui approxime la largeur arborescente des graphes quelconques à un facteur O(log OPT) de l'optimum.
Mot(s) Clé(s) : largeur arborescente ; nombre astéroïde ; algorithmique des graphes ; algorithmes d'approximation

RR-2001-05 Theoretical foundations of value withdrawal explanations in constraints solving by domain reduction
G. FERRAND, W. LESAINT, A. TESSIER
Résumé : La programmation par contrainte est un important paradigme de programmation de ces dernières années. Elle combine déclarativité et efficacité grâce à des solveurs de contraintes implantés pour des domaines spécifiques. Nous nous intéressons ici au cas de la réduction de domaines finis. Dans ce papier, elle est formalisée par des itérations chaotiques d'opérateurs monotones. Une première notion d'explication, qui a été prouvée très utile dans de nombreuses applications, est défini de façon déclarative en terme de clôtures. Un ensemble explicatif pour un retrait de valeurs est un ensemble d'opérateurs qui retireront toujours cette valeur quelque-soit l'ordre d'application de ceux-ci. Un opérateur peut toujours être défini par un ensemble de règles (dans le sens des définitions inductives d'Aczel). De plus, le papier montre que pour des notions classiques de consistance locale, un tel système de règles peut s'exprimer de façon naturelle. Elles expriment le retrait de valeurs comme conséquences d'autres retraits de valeurs. Une notion d'explication plus précise peut alors être obtenu: l'enchainement de ces règles permet de définir inductivement des arbres de preuves. Un tel arbre exprime clairement le retrait d'une valeur (sa racine) par le solveur, il est alors appelé explication du retrait de cette valeur. Les explications sont l'essence de la réduction de domaine.
Mot(s) Clé(s) : CSP; programmation par contraintes; réduction de domaines; explication

RR-2001-06 Learning Constraints between Variables in Inductive Logic Programming
A. BRAUD, C. VRAIN
Résumé : Un des points critiques de la Programmation Logique Inductive est la complexité des algorithmes, inhérente aux représentations en logique du premier ordre. Une solution intéressante à ce problème, appelée propositionnalisation, consiste à reformuler un problème relationnel en un problème attribut-valeur. Un schéma décrivant la forme générale des règles est donné ou appris, et le système le spécialise en apprenant soit des constantes symboliques, comme par exemple des relations d'égalité entre variables, soit des contraintes numériques. Nous proposons d'utiliser une approche génétique pour spécialiser de tels schémas. Dans cet article, nous nous intéressons à l'apprentissage de contraintes d'égalité entre les variables. La principale originalité de notre approche repose sur le codage de ces contraintes et les opérateurs génétiques correspondants. Au lieu de coder dans un individu si les paires de variables sont égales ou non, nous représentons les classes d'équivalence induites, et appliquons des opérateurs basés sur la théorie des ensembles pour produire de nouveaux individus.
Mot(s) Clé(s) : Programmation Logique Inductive ; Propositionnalisation ; Algorithmes Génétiques

RR-2001-07 Equational Unification, Rewrite Reachability, and Labelled Dag Automata
S. ANANTHARAMAN, P. NARENDRAN, M. RUSINOWITCH
Résumé :
Mot(s) Clé(s) :