Infinite String Rewrite Systems and Complexity

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 theworkof a derivation (defined as the sum of the lengths of all the rules used in the derivation, with multiplicity). The following results are proved: