Four notions of conjugacy for abstract semigroups

There have been several attempts to extend the notion of conjugacy from groups to semigroups. One notion, which we will denote byp, was originally introduced for free semigroups and popularized by Lallement's book. In a general semigroup, �p is reflexive and symmetric, but not transitive. However, one may consider the transitive closure � � ofp, which is an equivalence relation in any semigroup. Another notion of conjugacy, which we will denote byo, was introduced by Otto for monoids presented by finite Thue systems. The relationo is an equivalence relation in any semigroup, but it reduces to the universal relation if a semigroup has a zero; since there is a precise sense in which almost all finite semigroups have a zero, it follows thato is not useful for almost all finite semigroups. Three authors of the present paper introduced another notion of conjugacy, denoted byc, which is an equivalence relation in any semigroup; in addition, if a semigroup S does not have a zero, thenc = �o in S, butc does not reduce to the universal relation when a semigroup has a zero. In order to decide which notion is the most satisfactory, in the sense that it allows the extension of the classic conjugacy results in groups and hence leads to strong and elegant results with interconnections with other parts of mathematics, it is necessary to carry out a deep study comparing and separating these three notions of conjugacy. This is the aim of our paper. First, we study the decidability and independence of the conjugacy problems for certain classes of finitely presented monoids. We show that there exists a monoid M defined by a finite complete rewriting system such that the c-conjugacy problem for M is undecidable, and that for finitely presented monoids, the c-conjugacy problem and the word problem are independent, as are the c-conjugacy and p-conjugacy problems. As an especially interesting test case, we describec andp in the class of polycyclic monoids, and show that in this class, the p-conjugacy is "almost" transitive and thatc is strictly included inp. We also characterizec in the symmetric inverse monoid I(X) for a countable set X, and comparec andp in that monoid. We then generalize an outstanding theorem proved by Kudryavtseva, showing that relationp is transitive in a variety of semigroups that contains all completely regular semigroups and their variants. Althougho andc coincide for semigroups without zero, they differ in the most extreme way in some semigroups with zero. We present an infinite family of semigroups with zero divisors in whicho is universal whilec is the identity. We prove that commutative semigroups are precisely those where �p is the identity, and commutative and cancellative semigroups are those whereo is the identity. We also show that a semigroup in whichp is universal is necessarily simple. Moreover, if a semigroup S has an idempotent, we conclude that S is a rectangular band if and only ifp is the universal relation. The paper ends with a fairly large section of open problems.