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 1998

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

Les rapports de recherche du LIFO en 1998


RR-1998-01 Designing FPLA combinatorial circuits by conditional rewriting
N. ANDRIANARIVELO, W. BOUSDIRA, J. CHABIN, Z. MAAZOUZI
Date : 1998-09-22
Résumé Télécharger

RR-1998-02
G. FERRAND, A. TESSIER
Date : 1998-00-00
Résumé Télécharger

RR-1998-03 Translating view updates using inversion of relational algebra
F. BENTAYEB, D. LAURENT
Date : 1998-00-00
Résumé Télécharger

RR-1998-04 A conditional rewrite-based method for designing combinational logic circuits
N. ANDRIANARIVELO, W. BOUSDIRA, J. CHABIN, Z. MAAZOUZI
Date : 1998-11-12
Résumé Télécharger

RR-1998-06 Graphs with chordless cycles of bounded length
I. RUSU
Date : 1998-00-00
Résumé Télécharger

RR-1998-07 A System for the High-Level Parallelization and Cooperation of Constraint Solvers
L. GRANVILLIERS, G. HAINS, Q. MILLER, N. ROMERO
Date : 1998-09-21
Résumé Télécharger

RR-1998-08 Demand-driven search in functional logic programs
M. HANUS, P. RETY
Date : 1998-09-10
Résumé Télécharger

RR-1998-09 An introduction to BS-lambda
F. LOULERGUE, G. HAINS
Date : 1998-09-15
Résumé Télécharger

RR-1998-10 Recognizing i-triangulated graphs in O(mn)
F. ROUSSEL, I. RUSU
Date : 1998-09-21
Résumé Télécharger

RR-1998-11 A linear algorithm to color i-triangulated graphs
F. ROUSSEL, I. RUSU
Date : 1998-11-30
Résumé Télécharger

RR-1998-12 A New Result about the Decidability of the Existential One-step Rewriting Theory
S. LIMET, P. RETY
Date : 1998-12-18
Résumé Télécharger


Résumés des rapports de recherche


RR-1998-01 Designing FPLA combinatorial circuits by conditional rewriting
N. ANDRIANARIVELO, W. BOUSDIRA, J. CHABIN, Z. MAAZOUZI
Résumé : Nous presentons une methode de conception de circuits combinatoires fondee sur la reecriture conditionnelle. La methode s'appuie sur la strategie unitaire maximale et elle utilise des algebres predefinies. Les operations de base sur les entiers naturels et les booleens sont effectuees de facon efficace. Le formalisme des contraintes est utilise ainsi que des strategies et des heuristiques dirigees par le but qui sont correctes et efficaces. Une version experimentale de notre methode, appelee CDR (Circuit Design by Rewriting) est en developpement. Une breve description de CDR et quelques resultats sont egalement presentes dans ce papier.
Mot(s) Clé(s) : réécriture conditionnelle; contraintes; algèbres prédéfinies; conception de circuits combinatoires; stratégies; systême expert

RR-1998-02
G. FERRAND, A. TESSIER
Résumé : Ce rapport propose une reformulation de la semantique des programmes logiques avec contraintes en termes de semantique positive et semantique negative dans un cadre inductif uniforme. Dans ce cadre, les resultats de correction et completude s'expriment de maniere naturelle et elegante. En particulier, nous montrons un resultat de completude de la semantique negative en utilisant des ensembles infinis de contraintes. Ce cadre theorique est une extension originale de la vision grammaticale de la programmation logique.
Mot(s) Clé(s) : semantique, programmation logique avec contraintes, correction, completude, induction, co-induction.

RR-1998-03 Translating view updates using inversion of relational algebra
F. BENTAYEB, D. LAURENT
Résumé : Les vues relationnelles ont fait l'objet de plusieurs etudes depuis plusieurs annees. Parmi ces etudes, la traduction des mises a jour de vues en termes de mises a jour sur les relations de la base et la maintenance de vues materialisees , ont motive plusieurs chercheurs. De nos jours, les vues materialis ees accusent un essort consid erable dans le domaine du data warehousing. Dans ce papier, nous etudions le processus de traduction de mises a jour au travers de vues. Nous proposons une methode qui caracterise ces traductions. Cette methode est bas ee sur la notion d'inverse d'une expression relationnelle. De plus, nous caracterisons deux sortes de mises a jour : (1) des mises a jour deterministes independamment de l' etat de la base, et (2) des mises a jour deterministes par rapport a un etat donne de la base.
Mot(s) Clé(s) : vues relationnelles; traductions de mises a jour au travers de vues; inverses; images reciproques; mises a jour fortement deterministes; mises a jour faiblement deterministes

RR-1998-04 A conditional rewrite-based method for designing combinational logic circuits
N. ANDRIANARIVELO, W. BOUSDIRA, J. CHABIN, Z. MAAZOUZI
Résumé : Nous presentons une methode fondee sur la reecriture conditionnelle pour concevoir des circuits logiques combinatoires qui utilisent exclusivement des elements SSI (Small Scale Integrated elements). Nous adaptons la strategie maximale unitaire qui est une methode de preuve en logique de Horn pour definir des clauses contraintes et utiliser des algebres predefinies. Dans ce present travail, les entiers naturels et les booleens sont predefinis. Par ailleurs, l'espace de recherche pour trouver un circuit 'solution' est reduit puisque nous integrons a notre methode des criteres efficaces de suppression de regles redondantes ou inutiles.
Mot(s) Clé(s) : composants electroniques; portes logiques; SSI; reecriture conditionnelle; contraintes; algebres predefinies; conception de circuits combinatoires; strategies; systeme expert;

RR-1998-06 Graphs with chordless cycles of bounded length
I. RUSU
Résumé : La perfection des graphes faiblement triangules, c.a.d. les graphes sans antitrou dont les cycles induits sont isomorphes a C_{3} ou a C_{4}, a ete prouvee par Hayward et a engendre de nombreuses etudes pour resoudre efficacement les problemes NP-complets classiques qui deviennent polynomiaux pour les graphes parfaits. Si on remplace, dans la definition precedente, le C_{4} par un C_{p} arbitraire (p pair, au moins egal a 6), on obtient de nouvelles classes de graphes dont la perfection est montree dans ce papier. En fait, nous prouvons un resultat plus general: pour tout entier pair p>=6, les graphes dont les cycles induits sont isomorphes ou bien a C_{3} ou bien a l'un des C_{p}, C_{p+2},..., C_{2p-6} sont parfaits.
Mot(s) Clé(s) : perfection; graphes faiblement triangules; paire dominante

RR-1998-07 A System for the High-Level Parallelization and Cooperation of Constraint Solvers
L. GRANVILLIERS, G. HAINS, Q. MILLER, N. ROMERO
Résumé : Le système Bs-Solve permet l'écriture de stratégies parallèles de coopération de résolveurs de contraintes. La programmation déclarative des stratégies et la possibilité de réutilisation des résolveurs existants sont illustrées par l'implantation de deux algorithmes classiques : le calcul de bases de Groebner d'ensembles de polynômes et l'algorithme de consistance de Waltz sur des domaines continus.
Mot(s) Clé(s) : résolveurs de contraintes; coopération; stratégies parallèles

RR-1998-08 Demand-driven search in functional logic programs
M. HANUS, P. RETY
Résumé : Dans cet article, nous etudions les avantages des langages de programmation logico-fonctionnelle pour la generation d'espaces de recherche. Nous montrons que l'evaluation paresseuse de ces langages peut etre facilement utilisee pour implanter un solveur qui explore uniquement la partie de l'espace de recherche demandee dynamiquement. Contrairement a la programmation logique pure, l'utilisation de fonctions non deterministes permet une implantation simple et modulaire sans risque d'enlisement. De plus, l'encapsulation locale de la recherche evite l'explosion combinatoire de l'espace de recherche. Les fonctionalites necessaires (paresse, fonctions non deterministes, recherche encapsulee) sont disponibles dans Curry, nouveau langage declaratif concu pour combiner les techniques de programmation logique et fonctionnelle. Nous prouvons l'interet de cet approche par une application musicale implantee en Curry: la generation d'accords bien choisis pour accompagner une melodie donnee.
Mot(s) Clé(s) : Programmation logico-fonctionnelle; evaluation paresseuse; recherche; application pratique

RR-1998-09 An introduction to BS-lambda
F. LOULERGUE, G. HAINS
Résumé : Cet article est une introduction à BS-lambda, un calcul de programmes BSP recursivement parallèles. Le calcul est présenté, sa confluence est établie et des exemples sont donnés en syntaxe ML
Mot(s) Clé(s) : BSP; extension du lambda-calcul; parallélisme récursif spatialement; confluence

RR-1998-10 Recognizing i-triangulated graphs in O(mn)
F. ROUSSEL, I. RUSU
Résumé : On utilise le parcours en largeur lexicographique et les contractions de sous-graphes pour obtenir un nouveau (et meilleur, du point de vue de la complexite) algorithme pour reconnaitre les graphes i-triangules.
Mot(s) Clé(s) : algorithme de reconnaissance; parcours en largeur lexicographique; graphe triangule; graphe i-triangule

RR-1998-11 A linear algorithm to color i-triangulated graphs
F. ROUSSEL, I. RUSU
Résumé : Nous montrons que les graphes i-triangules peuvent etre colories en temps lineaire en appliquant l'algorithme de recherche lexicographique en profondeur et l'algorithme glouton de coloration.
Mot(s) Clé(s) : algorithme glouton; graphe triangule; graphe i-triangule; LexBFS

RR-1998-12 A New Result about the Decidability of the Existential One-step Rewriting Theory
S. LIMET, P. RETY
Résumé : Nous donnons une procedure de decision pour la totalite du fragment existentiel de la theorie du premier ordre de la reecriture en un pas, pour les systemes de reecriture lineaires, sans superpositions gauche-gauche (c.a.d sans paires critiques), et sans superpositions gauche-droite en tete (c.a.d. pas de superposition en tete entre un membre gauche et son membre droit). Cette procedure est definie grace aux grammaires synchronisees de n-uplets d'arbres.
Mot(s) Clé(s) : reecriture en un pas; langages d'arbres