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 2000
RR-2000-01
Confluence of the BSlambda_p calculus
F. LOULERGUE
Date : 2000-00-00
Résumé
RR-2000-03
A symmetric frequency-adaptative join algorithm for Shared Nothing machines
M. BAMHA, G. HAINS
Date : 2000-02-22
Résumé Télécharger
RR-2000-04
Chaotic iterations for constraint propagation and labeling
J. ARSOUZE, G. FERRAND, A. LALLOUET
Date : 2000-03-23
Résumé Télécharger
RR-2000-05
An optimal and skew-insensitive join algorithm for Shared Nothing machines
M. BAMHA
Date : 2000-04-21
Résumé Télécharger
RR-2000-06
Partitionable graphs arising from near-factorizations of finite groups
A. PECHER
Date : 2000-04-27
Résumé Télécharger
RR-2000-07
Titre a venir
F. MOAL
Date : 2000-00-00
Résumé Télécharger
RR-2000-08
Located concurrent constraint programming
N. ROMERO
Date : 2000-05-16
Résumé Télécharger
RR-2000-09
Value withdrawal explanation in CLP
G. FERRAND, W. LESAINT, A. TESSIER
Date : 2000-05-17
Résumé Télécharger
RR-2000-10
Actes des journées de vérification formelle
Pierre RETY (editor)
Date : 2000-06-08
Résumé Télécharger
RR-2000-11
Cayley partitionable graphs
A. PECHER
Date : 2000-09-18
Résumé Télécharger
RR-2000-12
About facets of the stable set polytope of a graph
A. PECHER
Date : 2000-09-18
Résumé Télécharger
RR-2000-13
A condition for a graph to contain k independent edges
A. P. WOJDA
Date : 2000-09-20
Résumé Télécharger
RR-2000-14
On self-complementary supergraphs of (n,n) graphs
A. P. WOJDA, M. WOZNIAK, I. A. ZIOLO
Date : 2000-09-20
Résumé Télécharger
RR-2000-15
Une version parallèle extensible de l'algorithme Particle Mesh Ewald
S. DROURI, G. HAINS
Date : 2000-10-10
Résumé Télécharger
RR-2000-16
Synchronized Tree Languages Revisited and New Applications
V. GOURANTON, P. RETY, H. SEIDL
Date : 2000-10-24
Résumé Télécharger
RR-2000-17
Weakly Regular Relations and Applications
S. LIMET, P. RETY, H. SEIDL
Date : 2000-12-05
Résumé Télécharger
Résumés des rapports de recherche
RR-2000-01 Confluence of the BSlambda_p calculus
F. LOULERGUE
Résumé :
Mot(s) Clé(s) :
RR-2000-03 A symmetric frequency-adaptative join algorithm for Shared Nothing machines
M. BAMHA, G. HAINS
Résumé :
Mot(s) Clé(s) :
RR-2000-04 Chaotic iterations for constraint propagation and labeling
J. ARSOUZE, G. FERRAND, A. LALLOUET
Résumé : Ce papier a pour but de définir un cadre sémantique uniforme pour la résolution de contraintes basé sur les itérations chaotiques et les opérateurs de clôture descendants. Ce cadre permet de prendre en compte à la fois la propagation et le labeling. Nous étendons le formalisme de Montanari et Rossi cite{MontanariR:AI91} grâce à deux types de règles plus générales: les règles de relaxation qui parcourent l'espace de recherche en préservant les solutions et de nouvelles règles de restriction qui coupent l'espace de recherche afin de l'explorer par morceaux. Nous montrons que le résultat d'indépendance de l'approximation calculée s'étend en présence du labeling. De plus, ce cadre permet de modéliser différentes approches déjà existantes telle que l'approche glass-box utilisée pour résoudre les contraintes sur les domaines finis dans Gnu-Prolog.
Mot(s) Clé(s) : propagation; labeling; itérations chaotiques; co-induction; sémantique
RR-2000-05 An optimal and skew-insensitive join algorithm for Shared Nothing machines
M. BAMHA
Résumé :
Mot(s) Clé(s) :
RR-2000-06 Partitionable graphs arising from near-factorizations of finite groups
A. PECHER
Résumé : Comme un contre-exemple à la Conjecture Forte des Graphes Parfaits serait un graphe partitionnable, toute 'nouvelle' construction de graphes partitionnables a de l'intérêt. Dans cet article, nous étudions les quasi-factorisations des groupes finis quelconques, et leurs graphes de Cayley associés, qui sont tous partitionnables. En particulier, nous montrons que les quasi-factorisations des groupes diédraux permettent de construire tous les graphes CGPW avec un nombre pair de sommets. Nous présentons des résultats qui impliquent qu'un groupe commutatif possédant une quasi-factorisation (A,B) telle que le cardinal de A soit au plus 4, est nécessairement un groupe cyclique. Un de nos résultats permet d'accéler les calculs exhaustifs par ordinateur. Enfin, nous montrons qu'il n'y a pas de contre-exemple à la Conjecture Forte des Graphes Parfaits associé à une quasi-factorisation d'un groupe commutatif d'ordre pair.
Mot(s) Clé(s) : partitionnable; parfait; graphe; quasi-factorisation; groupe
RR-2000-07 Titre a venir
F. MOAL
Résumé :
Mot(s) Clé(s) :
RR-2000-08 Located concurrent constraint programming
N. ROMERO
Résumé : La Programmation Concurrente Située par Contraintes étend le cadre de la Programmation Concurrente par Contraintes développé par Saraswat avec des primitives prenant en compte la distribution et le temps. Le store global unique est éclaté en plusieurs sites, qui sont constitués d'un store local et des processus associés. Chacun peut être créé dynamiquement et se déplace de son propre chef pour s'interfacer avec d'autres. La prise en compte du temps multiforme apparaît avec la capacité de détecter des modifications du store local, de démarrer et de suspendre des sites. Une syntaxe formelle et la sémantique opérationnelle associée sont définies. Nous présentons ensuite plusieurs exemple pour montrer que ces ajouts créent un cadre de programmation distribuée par contraites puissant.
Mot(s) Clé(s) : Programmation par Contraintes; Programmation Concurrente; Programmation Distribuée; Sémantique opérationnelle.
RR-2000-09 Value withdrawal explanation in CLP
G. FERRAND, W. LESAINT, A. TESSIER
Résumé : Ce travail est consacré à la résolution de contraintes et motivé par le débogage de programmes logiques avec contraintes dans le style GNU-Prolog. Ce papier s'intéresse uniquement à l'aspect contrainte. Dans ce cadre, la résolution de contraintes revient à de la réduction de domaines. Un calcul est formalisé par une itération chaotique. Le résultat calculé est alors décrit comme une clôture. Ce modèle convient bien à la conception d'outils et aux notions de débogage, par exemple explications d'échec ou diagnostic d'erreur. Dans ce papier, nous détaillons une application du modèle à l'explication du retrait d'une valeur d'un domaine. D'autres travaux ont déjà montré l'intérêt de telles notions d'explications pour des applications autres que l'analyse d'échec.
Mot(s) Clé(s) : CSP; débogage; explication; programmation par contrainte
RR-2000-10 Actes des journées de vérification formelle
Pierre RETY (editor)
Résumé :
Mot(s) Clé(s) :
RR-2000-11 Cayley partitionable graphs
A. PECHER
Résumé : Nous étudions dans cet article la classe des graphes de Cayley partitionnables. Cette étude est motivée par la Conjecture Forte des Graphes Parfaits. Les graphes de Cayley partitionnables sont étroitement liés avec les quasi-factorisations des groupes finis. Nous prouvons que toute quasi-factorisation d'un groupe fini doit posséder une structure très particulière. Nous avons utilisé cette propriété de structure pour accélérer nos recherches exhaustives de quasi-factorisations par ordinateur, et avons mis à jour un graphe de Cayley partitionnable avec cinquante sommets, qui n'appartient à aucun des procédés de construction de graphes partitionnables décrits à ce jour.
Mot(s) Clé(s) : partitionnable; parfait; Cayley; graphe; quasi-factorisation; groupe
RR-2000-12 About facets of the stable set polytope of a graph
A. PECHER
Résumé : Aucune caractérisation des graphes produisant une facette de rang n'est connue. En 1977, Balas et Zemel ont donné une condition nécessaire pour qu'un graphe produise une facette de rang, et en 1975, Chvátal a donné une condition suffisante, qui a introduit la classe des graphes critiques. Nous donnons deux améliorations de la condition nécessaire de Balas et Zemel, et une de la condition suffisante de Chvátal.
Mot(s) Clé(s) : graphe; polytope des stables; facette; facette de rang
RR-2000-13 A condition for a graph to contain k independent edges
A. P. WOJDA
Résumé : Soient k, l et n des entiers non négatifs tels que 1 < k < n/2, et soit G un graphe d'ordre n, de degré minimum au moins l. Nous trouvons une fonction F(n,k,l) telle que si la taile de G est superieure ou gale a F(n,k,l) alors G contient le couplage de taille k, ou bien l est inférieur ou égal k-1 et G est un de deux graphes exceptionels. Nous proposons une conjecture correspondante pour les forêts de taille au plus k.
Mot(s) Clé(s) : graphe, sous-graphe, forêt.
RR-2000-14 On self-complementary supergraphs of (n,n) graphs
A. P. WOJDA, M. WOZNIAK, I. A. ZIOLO
Résumé : Nous démontrons que, avec une seule exception, chaque (n,n)-graphe contenu dans son complément, est sous-graphe d'un graphe auto-complémenté.
Mot(s) Clé(s) : graphe, sous-graphe, graphe auto-complémenté
RR-2000-15 Une version parallèle extensible de l'algorithme Particle Mesh Ewald
S. DROURI, G. HAINS
Résumé : Ce rapport décrit les résultats d'une mini-action de validation applicative dans le cadre du programme iHPerf'98. Ce projet a été mené en collaboration avec le CBM (CNRS-Orléans) et financé par le GDR ARP du CNRS. Il traite de l'analyse d'extensibilité et de l'implantation parallèle d'un algorithme fondamental en simulation moléculaire: l'algorithme Particle Mesh Ewald (PME) pour le calcul des interactions électrostatiques. Nous proposons une version parallèle pour de PME pour architectures à mémoire répartie. Il optimise le rapport entre calcul, communication et synchronisation selon le modèle BSP (bulk-synchronous parallelism). Une version parallèle extensible de la transformée de Fourier rapide (FFT) est aussi proposée puisque le calcul de PME fait appel à celui-ci. Nos premiers tests sur une architecture Cray T3E montrent une accélération quasi-linéaire.
Mot(s) Clé(s) : Simulation moléculaire; interactions électrostatiques; algorithme Particle Mesh Ewald; modèle BSP; algorithmes parallèles; extensibilité.
RR-2000-16 Synchronized Tree Languages Revisited and New Applications
V. GOURANTON, P. RETY, H. SEIDL
Résumé : Nous présentons une formulation nouvelle et plus simple des langages synchronisés de n-uplets d'arbres. Ce nouveau formalisme permet de prouver des propriétés structurelles plus fortes. En conséquence, les langages synchronisés donnent lieu à de nouvelles applications : - à la réécriture : étant donné des langages d'arbres L1 (synchronisé), L2 (régulier), Rel(L1) sous-ensemble de L2 est décidable pour plusieurs relations de réécriture Rel. - à la concurrence : nous prouvons la décidabilité de la logique EF sur un calcul de processus permettant la communication sous une forme bornée. Il s'en suit que l'abscence d'interblocages est décidable.
Mot(s) Clé(s) : langage de n-uplets d'arbres; réécriture; concurrence
RR-2000-17 Weakly Regular Relations and Applications
S. LIMET, P. RETY, H. SEIDL
Résumé : Une nouvelle classe de langages de n-uplets d'arbres est introduite : les relations faiblement régulières. Il s'agit d'une extension du cas régulier (relations régulières) et d'une restriction des langages synchronisés de n-uplets d'arbres, qui a toutes les bonnes propriétés usuelles, sauf la cloture par complément. Deux applications sont présentées : à l'unification modulo un système de réécriture, et à la réécriture en un pas.
Mot(s) Clé(s) : langage d'abres; réécriture; unification