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)