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 2000

 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 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