In a group, two elements a and b are conjugate if there is some g with gag^-1 = b. Conjugacy is an equivalence relation and can be used to partition a group into equivalence classes whose elements are “similar”; the study of conjugacy classes can thus reveal important features of a group’s structure.

The present paper studies various generalizations of conjugacy that can also be applied to monoids, because they do not rely on the existence of inverses. Previously, conjugacy relations ~p and ~0 were proposed, but ~p is only an equivalence relation on free monoids and ~0 reduces to the universal relation on monoids with zeros. In contrast, the authors propose a relation ~c that is applicable to arbitrary monoids. While the conjugacy problem for finitely presented groups is undecidable, the paper studies the decidability and interdependence properties of the various conjugacy notions in the class of polycyclic monoids. In particular, it is shown that ~c is stronger than ~p, that c- and p-conjugacy are decidable in linear time, and that some decidability problems are independent of each other while others are not.

The paper is of a foundational nature; it widens the knowledge on decidability and complexity in the theory of monoids. Unfortunately, it does not indicate which conjugacy notion is applicable to which kind of application domain and is thus of interest mainly to specialists. Open problems to be addressed include whether the c-conjugacy problem is decidable in certain other monoid classes.