Complexity results on the conjugacy problem for monoids (Q1073015)

The paper deals with the complexity of the conjugacy problem CP(M) for monoids given by presentation of the form \(M=(A;T)\), where A is some alphabet, and T is a Thue system over A. Here \(CP(M)=\{(u,v)\in A^*\times A^*:\) \(\exists x,y\in A^*\) such that (ux,xv)\(\in T\) and (yu,vy)\(\in T\}\). It is shown that CP(M) is in NTIME(n) if T is finite and Church-Rosser. If, in addition, T is special (i.e. if \(T\subseteq (A^*-\{e\})\times \{e\})\) then CP(M) is decidable in polynomial time. The Church-Rosser property cannot be relaxed: it is shown that CP(M) for a monoid M presented by a finite almost-confluent Thue system may be arbitrarily complex or even undecidable.