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 2002

 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 2002


RR-2002-01 Regular Sets of Descendants by some Rewrite Strategies
P. RETY, J. VUOTTO
Date : 2002-01-31
Résumé Télécharger

RR-2002-02 A symbolic cost model for asynchronous parallel programs with structured dependences
E. MELIN, B. RAFFIN, X. REBEUF, B. VIROT
Date : 2002-03-20
Résumé Télécharger

RR-2002-03 ACID-unification, Rewrite Reachability and Set Constraints
S. ANANTHARAMAN, P. NARENDRAN, M. RUSINOWITCH
Date : 2002-03-30
Résumé Télécharger

RR-2002-04 Arbres d'itérations chaotiques pour la résolution des CSPs
J. ARSOUZE, G. FERRAND, A. LALLOUET
Date : 2002-04-18
Résumé Télécharger

RR-2002-05 A Model Theoretic semantics for CSP Consistencies
G. FERRAND, A. LALLOUET
Date : 2002-04-22
Résumé Télécharger

RR-2002-06 The Constraint System of the Grammatical View of (Constraint) Logic Programming
G. FERRAND, A. LALLOUET, J. ARSOUZE
Date : 2002-05-24
Résumé Télécharger

RR-2002-07 Learning Interval Bounds of Indexical-based Solver
M. BERGERE, T. B. H. DAO, A. ED-DBALI, G. FERRAND, A. LALLOUET, A. LEGTCHENKO, L. MARTIN, C. VRAIN
Date : 2002-04-30
Résumé Télécharger

RR-2002-08 Regular sets of descendants by leftmost strategy
P. RETY, J. VUOTTO
Date : 2002-04-29
Résumé Télécharger

RR-2002-09 Correctness of constraint retraction algorithms
R. DEBRUYNE, G. FERRAND, N. JUSSIEN, W. LESAINT, S. OUIS, A. TESSIER
Date : 2002-05-06
Résumé Télécharger

RR-2002-10 Coloring powers of graphs of bounded clique-width
I. TODINCA
Date : 2002-10-07
Résumé Télécharger

RR-2002-11 Unification modulo ACUI plus Homomorphisms/Distributivity
S. ANANTHARAMAN, P. NARENDRAN, M. RUSINOWITCH
Date : 2002-12-30
Résumé Télécharger


Résumés des rapports de recherche


RR-2002-01 Regular Sets of Descendants by some Rewrite Strategies
P. RETY, J. VUOTTO
Résumé : Pour un système de réécriture R basé sur les constructeurs, un ensemble régulier de termes clos E, et supposant certaines restrictions, nous construisons un automate d'arbre qui reconnait les descendants de E, c'est a dire les termes issus de E obtenus par réécriture, selon les stratégies innermost, innermost-leftmost, et outermost.
Mot(s) Clé(s) : réécriture; stratégie; automate d'arbre

RR-2002-02 A symbolic cost model for asynchronous parallel programs with structured dependences
E. MELIN, B. RAFFIN, X. REBEUF, B. VIROT
Résumé : Nous proposons d'associer un coût symbolique à un programme parallèle asynchrone. A contrario des approches classiques, nous prenons en compte tout l'asynchronisme dynamique relatif aux différents environnements initiaux possibles qui sont susceptibles de générer des indépendances dynamiques. Nous introduisons le modèle intermédiaire asynchrone SCP. Il impose uniquement des indépendances statiques offrant ainsi une lecture séquentielle du programme. Afin de calculer le coût symbolique, nous conditionnons l'existence d'une dépendance en l'annotant par un prédicat sur les variables du programme. Pour évaluer le coût dans l'environnement initial, les prédicats sont transformés par une méthode "backward" basée sur le calcul des plus faibles pré-conditions libérales. Le coût résultant est paramétré par l'environnement initial et intègre les dépendances dynamiques.
Mot(s) Clé(s) : Modèle de coût symbolique; calcul des plus petites pré-conditions libérales; Indépendances dynamiques; Langages de Programmation Parallèle

RR-2002-03 ACID-unification, Rewrite Reachability and Set Constraints
S. ANANTHARAMAN, P. NARENDRAN, M. RUSINOWITCH
Résumé :
Mot(s) Clé(s) :

RR-2002-04 Arbres d'itérations chaotiques pour la résolution des CSPs
J. ARSOUZE, G. FERRAND, A. LALLOUET
Résumé :
Mot(s) Clé(s) :

RR-2002-05 A Model Theoretic semantics for CSP Consistencies
G. FERRAND, A. LALLOUET
Résumé :
Mot(s) Clé(s) :

RR-2002-06 The Constraint System of the Grammatical View of (Constraint) Logic Programming
G. FERRAND, A. LALLOUET, J. ARSOUZE
Résumé :
Mot(s) Clé(s) :

RR-2002-07 Learning Interval Bounds of Indexical-based Solver
M. BERGERE, T. B. H. DAO, A. ED-DBALI, G. FERRAND, A. LALLOUET, A. LEGTCHENKO, L. MARTIN, C. VRAIN
Résumé :
Mot(s) Clé(s) :

RR-2002-08 Regular sets of descendants by leftmost strategy
P. RETY, J. VUOTTO
Résumé : Pour un système de réécriture R basé sur les constructeurs, un ensemble régulier de termes clos E, et supposant certaines restrictions, nous construisons un automate d'arbre fini qui reconnait les descendants de E, i.e. les termes issus de E par réécriture, selon une stratégie leftmost.
Mot(s) Clé(s) : réécriture de termes; stratégie; automate d'arbre

RR-2002-09 Correctness of constraint retraction algorithms
R. DEBRUYNE, G. FERRAND, N. JUSSIEN, W. LESAINT, S. OUIS, A. TESSIER
Résumé :
Mot(s) Clé(s) :

RR-2002-10 Coloring powers of graphs of bounded clique-width
I. TODINCA
Résumé : Etant donné un graphe G, le graphe G^l a le même ensemble de sommets, que G et deux sommets sont adjacents dans G^l s'ils se trouvent à distance au plus l dans G. Le problème de la l-coloration consiste à trouver une coloration optimale de G^l, où le graphe en entrée est G. Nous montrons que, pour toute constante l, le problème de la l-coloration est polynomial pour les graphes de largeur de clique bornée, si le graphe en entrée est donné avec une clique-décomposition optimale.
Mot(s) Clé(s) : largeur de clique ; coloration de graphes ; algorithmique des graphes

RR-2002-11 Unification modulo ACUI plus Homomorphisms/Distributivity
S. ANANTHARAMAN, P. NARENDRAN, M. RUSINOWITCH
Résumé : In this paper we consider the unificatiopn problem over theories that are extensions of the well-known ACI or ACUI, obtained by adding finitely many homomorphism symbols, or a symbol '*' that distributes over the ACUI-symbol denoted '+'. We first show that when we adjoin a set of commuting homomorphisms to ACUI, unification is undecidable; this is done by reduction from the reachability problem for Minsky machine configurations. (This is in contrast with the case of non-commuting homomorphisms, which is known to be DEXPTIME-complete). We then consider the ACUID_l-unification problem, i.e., unification modulo ACUI plus left-distributivity of a given '*' w.r.t. '+'; this problem is related to the case of non-commuting homomorphisms; we prove its NEXPTIME-decidability. If we assume the symbol '*' to be 2-sided distributive w.r.t. '+', we get the theory ACUID for which the unification problem turns out to be decidable. Finally we show that, if equations of associativity-commutativity, or just of associativity, on '*' are added on to ACUID, then the unification problem becomes undecidable.
Mot(s) Clé(s) : E-Unification, Complexity; Rewrite reachability; Minsky machine; Post correspondence problem; Set constraints