j-C. Birget Infinite string rewrite systems and complexity Cet article étudie la relation entre la complexité temporelle et le travail de dérivation pour le problème du mot dans les semigroupes et les groupes infiniment présentés. La notion de travail d'une dérivation est introduite (définie comme la somme des longueurs des règles utilisées dans la dérivation, avec mul­ tiplicité); pour les présentations infinies, ceci est une meilleure mesure que le nombre de règles utilisées. Dans le con­ texte de la complexité déterministe, nous remplaçons le problème du mot par le problème du calcul d'un fonction de représentants (qui produit un représentant unique pour chaque classe de congru­ ence). Nous démontrons entre autres les résultats suivants : Un semigroupe finiment engendré S admet une fonction de représentants, de longueur au plus linéaire et calculable en temps déterministe . TO(1) , si et seulement si S peut être in­ clus dans un semigroupe ayant une présentation complète (conflu­ ente et terminante) où A est fini, R est rationnel (calculable par un transducteur fini), où chaque dérivation a un travail . TO(1) , et où la réduction n'accroît pas les longueurs de façon plus que linéaire. Le problème du mot d'un semigroupe (ou groupe) finiment engen­ dré S est décidable en temps non déterministe . TO(1) si et seulement si S a une présentation (de groupe) où A est fini, R est l'intersection de deux langages contextuels déterministes, et le travail de dérivation minimal entre deux mots équivalents x, y est . T(|x | + |y |)O(1) . (Ceci renforce un résultat de Madlener et Otto.) Un semigroupe finiment engendré S admet une fonction de représentants définie par minimisation sur un ordre de réduction et calculable en temps déterministe . TO(1) si et seulement si S admet une présentation (de groupe) où A est fini, R est une fonction calculable en temps déterministe linéaire (avec la longueur totale entrée-sortie comme paramètre), et le travail de chaque dérivation gloutonne à gauche est . TO(1) . We study the relation between time complexity and derivation work for the word problem of infinitely presented semigroups and groups. We introduce the notion of work of a derivation (defined as the sum of the lengths of the rules used in the derivation, with multiplicity); for infinite presentations, this is a better measure than the number of derivation steps. In the context of deterministic complexity, we replace the word problem by the problem of computing a representative function (which yields one representative for each congruence class). The following results, among others, are proved: A finitely generated semigroup S has a representative func­ tion, with linear upper-bound on the length, and computable in deterministic time . TO(1) if and only if S is embeddable in a semigroup with a complete (i.e., confluent and terminating) pre­ sentation where A is finite, R is rational (i.e., R is computed by a finite transducer), every derivation has work . TO(1) , and the reduction does not increase lengths more than linearly. The word problem of a finitely generated semigroup (or group) S is decidable in non deterministic time . TO(1) if and only if S has a (group) presentation where A is finite, R is the intersection of two deterministic context-free languages, and the minimum derivation work between equivalent words x, y is . T(|x | + |y |)O(1) . (This strengthens a result of Madlener and Otto.) A finitely generated semigroup S has a representative func­ tion, defined by minimization over a reduction order, and com­ putable in deterministic time . TO(1) if and only if S has a (group) presentation where A is finite, R is a func­ tion computable in linear deterministic time (with the total in­ put-output length as parameter), and the work of every greedy left-most derivation is . TO(1)