Lifo - Laboratoire d'Informatique Fondamentale d'orléans INSA Centre Val de Loire Université d'Orléans Université d'Orléans

Lifo > LIFO Research Report for Year 2002

Site en Français



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



Go to Research Reports of Year : 1998 1999 2000 2001 2002 2003 2004 2005 2006 2007 2008 2009 2010 2011 2012 2013 2014 2015 2016 2017 2018

LIFO Research Report for Year 2002


RR-2002-01 Regular Sets of Descendants by some Rewrite Strategies
P. RETY, J. VUOTTO
Date : 2002-01-31
Abstract Download

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

RR-2002-03 ACID-unification, Rewrite Reachability and Set Constraints
S. ANANTHARAMAN, P. NARENDRAN, M. RUSINOWITCH
Date : 2002-03-30
Abstract Download

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

RR-2002-05 A Model Theoretic semantics for CSP Consistencies
G. FERRAND, A. LALLOUET
Date : 2002-04-22
Abstract Download

RR-2002-06 The Constraint System of the Grammatical View of (Constraint) Logic Programming
G. FERRAND, A. LALLOUET, J. ARSOUZE
Date : 2002-05-24
Abstract Download

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

RR-2002-08 Regular sets of descendants by leftmost strategy
P. RETY, J. VUOTTO
Date : 2002-04-29
Abstract Download

RR-2002-09 Correctness of constraint retraction algorithms
R. DEBRUYNE, G. FERRAND, N. JUSSIEN, W. LESAINT, S. OUIS, A. TESSIER
Date : 2002-05-06
Abstract Download

RR-2002-10 Coloring powers of graphs of bounded clique-width
I. TODINCA
Date : 2002-10-07
Abstract Download

RR-2002-11 Unification modulo ACUI plus Homomorphisms/Distributivity
S. ANANTHARAMAN, P. NARENDRAN, M. RUSINOWITCH
Date : 2002-12-30
Abstract Download

Abstracts of Research Reports


RR-2002-01 Regular Sets of Descendants by some Rewrite Strategies
P. RETY, J. VUOTTO
Abstract : For a constructor-based rewrite system R, a regular set of ground terms E, and assuming some additional restrictions, we build a finite tree automaton that recognizes the descendants of E, i.e. the terms issued from E by rewriting, according to innermost, innermost-leftmost, and outermost strategies.
Keywords : term rewriting; strategy; tree automaton

RR-2002-02 A symbolic cost model for asynchronous parallel programs with structured dependences
E. MELIN, B. RAFFIN, X. REBEUF, B. VIROT
Abstract : We propose to associate a symbolic cost to a asynchronous parallel program. In contrast to classical approaches, we take into account all the dynamic asynchronism related to the different initial states that generate dynamic independences. We introduce an asynchronous intermediate model called SCP{}. It only imposes static independences allowing a sequential lecture of programs. To compute the symbolic cost, we condition the existence of a dependence by annotating it with a predicate on program variables. To evaluate the cost in the initial environment, predicates are transformed by a backward method based on the model Weakest Liberal Preconditions Calculus. The resulting symbolic cost is parameterized by the initial environment and integrates dynamic dependences.
Keywords : Symbolic Cost Model; Weakest liberal preconditions; dynamic independences; Parallel Programming Languages

RR-2002-03 ACID-unification, Rewrite Reachability and Set Constraints
S. ANANTHARAMAN, P. NARENDRAN, M. RUSINOWITCH
Abstract : E-unification problems are central in automated deduction. In this paper, we consider theories that are extensions of the well-known AC or ACU, such as ACID and ACUIHC, and relate their study to set constraints or reachability problems on Minsky machine configurations. We first show that unification modulo the theory ACUIHC - i.e., ACU plus idempotence and a set of commuting homomorphisms - is undecidable. We next consider the ACID-unification problem, i.e., unification modulo AC plus idempotence for a given symbol '+', and distributivity of a given '*' w.r.t '+'. It is shown that this problem is undecidable if equations of associativity-commutativity, or just associativity, on '*' are added on to ACID; but if '*' satisfies no additional identities other than distributivity, ACID-unification is shown to be NEXPTIME-decidable, and DEXPTIME-hard. All these conclusions remain valid also for the ACUID-unification problem, that is when a unit element for '+' which is null for '*', is added on to ACID.
Keywords : E-Unification, Complexity, Rewrite reachability, Minsky machine, Post correspondence problem, Set constraints, Tree automata, Dag automata

RR-2002-04 Arbres d'itérations chaotiques pour la résolution des CSPs
J. ARSOUZE, G. FERRAND, A. LALLOUET
Abstract :
Keywords :

RR-2002-05 A Model Theoretic semantics for CSP Consistencies
G. FERRAND, A. LALLOUET
Abstract :
Keywords :

RR-2002-06 The Constraint System of the Grammatical View of (Constraint) Logic Programming
G. FERRAND, A. LALLOUET, J. ARSOUZE
Abstract :
Keywords :

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
Abstract :
Keywords :

RR-2002-08 Regular sets of descendants by leftmost strategy
P. RETY, J. VUOTTO
Abstract : For a constructor-based rewrite system R, a regular set of ground terms E, and assuming some additional restrictions, we build a finite tree automaton that recognizes the descendants of E, i.e. the terms issued from E by rewriting, according to leftmost strategy.
Keywords : term rewriting; strategy; tree automaton.

RR-2002-09 Correctness of constraint retraction algorithms
R. DEBRUYNE, G. FERRAND, N. JUSSIEN, W. LESAINT, S. OUIS, A. TESSIER
Abstract :
Keywords :

RR-2002-10 Coloring powers of graphs of bounded clique-width
I. TODINCA
Abstract : Given a graph G, the graph G^l has the same vertex set and two vertices are adjacent in G^l if and only if they are at distance at most l in G. The l-coloring problem consists in finding an optimal vertex coloring of the graph G^l, where G the input graph. We show that, for any fixed value of l, the l-coloring problem is polynomial when restricted to graphs of bounded clique-width, if an expression of the graph is also part of the input.
Keywords : clique-width; graph colorings; graph algorithms

RR-2002-11 Unification modulo ACUI plus Homomorphisms/Distributivity
S. ANANTHARAMAN, P. NARENDRAN, M. RUSINOWITCH
Abstract : 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.
Keywords : E-Unification, Complexity; Rewrite reachability; Minsky machine; Post correspondence problem; Set constraints