Conjugacy in monoids with a special Church-Rosser presentation is decidable (Q801163): Difference between revisions

The paper concerns conjugacy relations on monoids. Direct generalizations introduced for free monoids to an arbitrary monoid are not equivalence relations. For this reason, the author proposes three other definitions of conjugacy for arbitrary monoids. A chain of inclusions of all five conjugacy relations is shown. All these relations coincide for free monoids, for monoids which are groups, and for monoids presented by special Church-Rosser Thue systems. It is shown, that for finitely presented monoids, the word problem and the conjugacy problem are independent, and that there exists a monoid presented by a finite special Thue system such that the conjugacy problem for this monoid is undecidable. In the main result of the paper, the author proves that the conjugacy problem for monoids presented by a finite special Church-Rosser Thue system is decidable. It remains open whether the Church-Rosser property of the Thue system is sufficient for decidability of the conjugacy problem of a monoid.