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 the work of a derivation (defined as the sum of the lengths of all the rules used in the derivation, with multiplicity). The following results are proved:
(1)A finitely generated semigroup S has a decidable word problem iff S is embeddable into a finitely generated semigroup with a complete (i.e. confluent and terminating) presentation whose set of rewrite rules forms a finite-state sequential partial function.
A finitely generated semigroup S has a representative function which is computable in deterministic time โค T (.) O(1) and has a linear upper bound on its length, iff S is embeddable in a semigroup with a complete presentation A : R where A is finite, R is a finite-state sequential partial function, every derivation has work โค T (.) O(1) , and reduction does not increase lengths more than linearly.
(2)The word problem of a finitely generated monoid (or group) S is decidable in nondeterministic time โค T (.) O(1) iff S has a (group) presentation A : R 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.)
We also give results that relate the deterministic computational complexity of a representative function and the work of derivations in a finitely generated infinite presentation.
(3)Every deterministic Turing machine with time complexity O(T ) is equivalent to a deterministic Turing machine which halts after O(T ) steps, no matter what configuration this machine starts in. (This is a complexity version of a theorem by Martin Davis, which plays a key role in the connection between complexity and string rewriting.)