Complexity results on the conjugacy problem for monoids

The complexity of the conjugacy problem CP_M for monoids given by presentations of the form (Σ; T) is investigated. Here T denotes a (possibly infinite) Thue system over the alphabet Σ. The following results are obtained: 1. (1) If T is finite and Church-Rosser, then CP_M is in NTIME(n). If in addition T is special, then CP_M is in P. 2. (2) If T is infinite and Church-Rosser, but of the form ∩_iε{lunate}ID_i × {r₁}, where I is finite and each D_i is in NP, then CP_M is in NP. However, if I is infinite, then CP_M can be undecidable, even if T is recursive. 3. (3) If T is finite and almost-confluent, then CP_M can be decidable with any degree in the Grzegorczyk hierarchy, or it can be undecidable with any recursively enumerable degree of unsolvability.