Jean-Yves Marion 
 Titre : ComplexitM-i des algorithmes definis par des systemes de reecriture avec
interpretation polynomiale.
 Abstract :We study deterministic (non-deterministic)algorithms define by mean of
confluent
(resp. non-confluent) rewrite system admitting polynomial interpretation
termination proofs. Data structures of the algorithms include strings,
lists and trees.
We classify them according to the interpretations of constructors
This leads to the definition of six classes,
which turn out to be exactly the deterministic (non-deterministic)
poly-time,
linear exponential-time
and doubly linear  exponential time computable functions
when the class is based on confluent (resp. non-confluent) systems.
Next, we demonstrate that functions with exponential interpretation
termination proofs are super-elementary.

=============================
Laurent Juban (LORIA, Nancy)
Titre: Sur la complexitM-i du calcul de la base de Hilbert
       d'un systM-hme diophantien linM-iaire
(travail commun avec Miki Hermann et Phokion G. Kolaitis)
http://www.loria.fr/~hermann/publications/hilbert3.ps.gz
Resume: 
Dans les domaines de la dM-iduction automatique, de la preuve, de la
rM-isolution des contraintes et de la programmation logique nous sommes
souvent confrontM-is au problM-hme d'unification. En prM-isence des symboles
associatifs-commutatifs (AC), il faut calculer tous les unificateurs
principaux modulo cette thM-iorie M-iquationnelle. Dans le cas de la
theorie M-iquationnelle AC, l'ensemble minimal et complet d'unificateurs
est fini.
Tous les algorithmes d'unification AC reposent sur le
calcul de la base de Hilbert d'un systM-hme diophantien linM-iaire homogM-hne
sur les entiers non-negatifs
Dans notre travail, nous analysons la complexitM-i du calcul
de la base de Hilbert des systM-hmes diophantiens linM-iaires homogM-hnes,
en utilisant la theorie de la complexite des problemes de comptage de
Valiant. Nous dM-iduisons des bornes, infM-irieure et supM-irieure, pour ce
problM-hme, en montrant qu'il est #P-difficile et il appartient M-` la
classe #NP. En plus, nous analysons des cas spM-iciaux que nous obtenons
par restriction du nombre d'M-iquations ou d'occurrences de variables
dans le systM-hme.
======================