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

An algorithm \(\phi\) for solving the word problem for a string rewriting system \(T\) on a finite alphabet \(\Sigma\) is called a pseudo-natural algorithm, if on the input \(u,v\in \Sigma^*\) \(\phi\) actually computes a derivation of \(v\) from \(u\) in \(T\) in case \(u\) and \(v\) are congruent modulo \(T\). The authors obtain the following results: there exists a finitely presented group such that every pseudonatural algorithm for solving the word problem for it is of a high degree of complexity, although this problem is easily decidable; each finitely generated group \(G\) with solvable word problem can be embedded into a finitely presented group \(H\) with word problem solved by a pseudo-natural algorithm of the same degree of complexity as the word problem for \(G\). There are also other assertions in the paper.