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