Infinite string rewrite systems and complexity

j-C. Birget

IBP-Litp 1995/45: Rapport de Recherche Litp / Litp research reports
43 pages - Octobre/October 1995 - Document en anglais.

PostScript : Ko /Kb

Titre / Title: Infinite string rewrite systems and complexity

Résumé : 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 multiplicité); pour les présentations infinies, ceci est une meilleure mesure que le nombre de règles utilisées. Dans le contexte 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 congruence).
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 inclus dans un semigroupe ayant une présentation complète (confluente 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 engendré 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) .

Abstract : 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 function, 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) presentation 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 function, defined by minimization over a reduction order, and computable in deterministic time ¾ TO(1) if and only if S has a (group) presentation where A is finite, R is a function computable in linear deterministic time (with the total input-output length as parameter), and the work of every greedy left-most derivation is ¾ TO(1)

Publications internes Litp 1995 / Litp research reports 1995