Pseudo-natural algorithms for the word problem for finitely presented monoids and groups

For a string rewriting system T on a finite alphabet ∑, the word problem is the following decision problem:INSTANCE: Two words u, υ蜒∑*.QUESTION:Are the words u, and υ congruent modulo T, i.e . can the word υ be derived from u in T?An algorithm φ for solving this problem is called a pseudo-natural algorithm, if on input u, υ蜒∑*, / actually computes a derivation of v from a in T in case a and v are congruent modulo T.For many classes of monoids and groups, that are given through presentations involving finite string rewriting systems, the word problems are solved by pseudo-natural algorithms . Here, the following results concerning this class of algorithms are obtained:1 . The degree of complexity of a pseudo-natural algorithm for solving the word problem for a finitely presented monoid is independent of the actually chosen finite presentation.2. There exists a finitely presented monoid (in fact, even a group) such that every pseudonatural algorithm for solving the word problem for this monoid is of a high degree of complexity, although this problem is easily decidable.3. Each finitely generated group G, the word problem for which is decidable, can be embedded in a finitely presented group H such that the word problem for H can be solved by a pseudo-natural algorithm that is of the same degree of complexity as the word problem for G