- Renseignements pratiques
- Enseignement
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
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
Université d'Orléans | INSA Centre Val de Loire
LIFO - Laboratoire d'Informatique Fondamentale d'Orléans 