DECIDABILITY AND INDEPENDENCE OF CONJUGACY PROBLEMS
IN FINITELY PRESENTED MONOIDS

arXiv:1703.00027v1 [] 28 Feb 2017

JOÃO ARAÚJO, MICHAEL KINYON, JANUSZ KONIECZNY, AND ANTÓNIO MALHEIRO

Abstract. There have been several attempts to extend the notion of conjugacy from groups to
monoids. The aim of this paper is study the decidability and independence of conjugacy problems
for three of these notions (which we will denote by ∼p , ∼o , and ∼c ) in certain classes of finitely
presented monoids. We will show that in the class of polycyclic monoids, p-conjugacy is “almost”
transitive, ∼c is strictly included in ∼p , and the p- and c-conjugacy problems are decidable with
linear compexity. For other classes of monoids, the situation is more complicated. We show that
there exists a monoid M defined by a finite complete presentation 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.
2010 Mathematics Subject Classification: 68Q42, 20F10, 3D35, 3D15.
Keywords and phrases: Conjugacy; finitely presented monoids; polycyclic monoids; decision problem; decidability; independence; complexity.

1. Introduction
The well-known notion of conjugacy from group theory can be extended to monoids in many
different ways. The authors dealt with four notions of conjugacy in monoids in [1, 2]. The present
paper can be considered an extension of this work. Any generalization of the conjugacy relation to
general monoids must avoid inverses. One of the possible formulations, spread by Lallement [20] for
a free monoid M , was the following relation:
(1.1)

a ∼p b ⇔ ∃u,v∈M a = uv and b = vu.

(Lallement credited the idea of the relation ∼p to Lyndon and Schützenberger [22].) If M is a free
monoid, then ∼p is an equivalence relation on M [20, Corollary 5.2], and so it can be regarded as
a conjugacy in M . In a general monoid M , the relation ∼p is reflexive and symmetric, but not
transitive. The transitive closure ∼∗p of ∼p has been defined as a conjugacy relation in a general
semigroup [13,18,19]. (If a ∼p b in a general monoid, we say that a and b are primarily conjugate [19],
hence our subscript in ∼p ).
Another relation that can serve as a conjugacy in any monoid is defined as follows:
(1.2)

a ∼o b ⇔ ∃g,h∈M ag = gb and bh = ha.

This relation was defined by Otto for monoids presented by finite Thue systems [30], but it is an
equivalence relation in any monoid. Its drawback – as a candidate for a conjugacy for general monoids
– is that it reduces to the universal relation M × M for any monoid M that has a zero.
To remedy the latter problem, three authors of the present paper introduced a new notion of
conjugacy [2], which retains Otto’s concept for monoids without zero, but does not reduce to M × M
if M has a zero. The main idea was to restrict the set from which conjugators can be chosen. For a
monoid M with zero and a ∈ M \ {0}, let P(a) be the set {g ∈ M : (∀m ∈ M ) mag = 0 ⇒ ma = 0},
and define P(0) to be {0}. If M has no zero, we agree that P(a) = M , for every a ∈ M . Following [2],
we define a relation ∼c on any monoid M by
(1.3)

a ∼c b ⇔ ∃g∈P(a) ∃h∈P(b) ag = gb and bh = ha.

The relation ∼c is an equivalence relation on an arbitrary monoid M . Moreover, if M is a monoid
without zero, then ∼c = ∼o ; and if M is a free monoid, then ∼c = ∼o = ∼p . In the case when M has
1

a zero, the conjugacy class of 0 with respect to ∼c is {0}. Throughout the paper we shall refer to ∼i ,
where i ∈ {p, o, c}, as i-conjugacy.
The aim of this paper is to study the decidability and independence of the i-conjugacy problems
in some classes of finitely presented monoids.
It is well-known that the conjugacy problem for finitely presented groups is undecidable; that is,
there exists a finitely presented group for which the conjugacy problem is undecidable [27]. The
relations ∼p , ∼o , and ∼c reduce to group conjugacy when a monoid is a group. It follows that the iconjugacy problem, for i ∈ {p, o, c}, is also undecidable. However, it is of interest to study decidability
of the i-conjugacy problems in particular classes of finitely presented monoids.
First, we consider the class of polycyclic monoids, which are are finitely presented monoids with
zero. The polycyclic monoids Pn , with n ≥ 2, were first introduced by Nivat and Perrot [26], and
later rediscovered by Cuntz in the context of the theory of C ∗ -algebras [11, Section 1]. (Within the
theory of C ∗ -algebras, the polycyclic monoids are often referred to as Cuntz inverse semigroups.) The
polycyclic monoids appear to be related to the idea of self-similarity [14]. For example, the polycyclic
monoid P2 can be represented by partial injective maps on the Cantor set: its two generators, p1
and p2 , map, respectively, the left and right hand sides of the Cantor set, to the whole Cantor set.
These monoids can also be characterized as the syntactic monoid of the restricted Dyck language on
a set of cardinality n, that is, the language that consists of all correct bracket sequences of n types of
brackets. The study of representations of the polycyclic monoids naturally connects with the study
of its conjugacy relations [17, 21]. In [21], the classification of the ‘proper closed inverse submonoids’
of Pn depends on the study of its conjugacy classes.
In Section 3, we characterize p-conjugacy and c-conjugacy in the polycyclic monoids, and conclude
that ∼c ⊂ ∼p . (For sets A and B, we write A ⊂ B if A is a proper subset of B.) We then show
that the p-conjugacy and c-conjugacy problems are decidable for polycyclic monoids, and that, given
words a and b, testing whether or not a ∼i b, for i ∈ {p, c}, can be done linearly on the lengths of a
and b. Note that in a polycyclic monoid Pn , the relation ∼o is universal since Pn has a zero.
These positive results obtained for polycyclic monoids concerning the decidability and complexity
of the conjugacy problems cannot be extended to the general finitely presented monoids.
In Section 4, we study decidability results. In particular, we show that there exists a monoid M
defined by a finite complete presentation such that the c-conjugacy problem for M is undecidable
(Proposition 4.2).
In Section 5, we study independence results. The word problem for groups is undecidable [23, 28,
31]. However, for groups, the word problem is reducible to the conjugacy problem [30, page 225],
hence if the conjugacy problem for a group G is decidable, then the word problem for G is also
decidable. Therefore, the word problem and the conjugacy problem for groups are not independent.
The situation for monoids is different. Osipova [29] has proved that for finitely presented monoids,
the word problem, the p-conjugacy problem, and the o-conjugacy problem are pairwise independent.
We show that for finitely presented monoids, the word problem and the c-conjugacy problem are
independent (Theorem 5.2), and that the p-conjugacy problem and the c-conjugacy problem are also
independent (Theorem 5.3). We do not know if the c-conjugacy problem and the o-conjugacy problem
are independent.
We conclude the paper with Section 6 that lists open problems regarding the conjugacies under
discussion.

2. Background
In this section we will formulate the main concepts needed in the following sections. For further
background on the free monoid, see [15]; for presentations, see [12, 32]; and, for rewriting systems,
see [7].
Alphabets and words. Let Σ be a non-empty set, called an alphabet. We denote by Σ∗ the set of
finite strings (called words) of elements of Σ, including the empty word 1. For w ∈ Σ∗ and a ∈ Σ, we
denote by |w| the length of the word w and by |w|a the number of occurrences of a in w. For example,
if Σ = {a, b, c} and w = aabba ∈ Σ∗ , then |w| = 5, |w|a = 3, and |w|c = 0.
2

A non-empty word z is said to be a factor of w ∈ Σ∗ if w = uzv, for some words u, v ∈ Σ∗ . If w,
u, and v are words with w = uv, then u is called a prefix of w and v a suffix of w; the word u is said
to be a proper prefix of w if v is non empty (the notion of proper suffix is dual). Two words u and v
are said to be prefix-comparable if either u is a prefix of v or v is a prefix of u.
Rewriting systems. Any subset R of Σ∗ × Σ∗ is called a rewriting system (or a Thue system) on
Σ. An element (x, y) of R, also commonly denoted x = y, is called a rewriting rule. If (x, y) ∈ R and
u, v ∈ Σ∗ , we say that uxv reduces to uyv and we write uxv → uyv. A word w is said to be irreducible
∗
if there is no w′ ∈ Σ∗ , such that w → w′ . We denote by → the reflexive and transitive closure of →.
A rewriting system R on Σ is special if every element of R is of the form (x, 1) with x 6= 1; it is
monadic if every element of R is of the form (x, y) with y ∈ Σ ∪ {1} and |x| > |y|; it is length reducing
if |x| > |y| for all (x, y) ∈ R; it is noetherian if there is no infinite sequence w1 , w2 , w3 , . . . of words
∗
∗
in Σ∗ such that w1 → w2 → w3 → · · · ; it is confluent if for all u, v, w ∈ Σ∗ , if u → v and u → w,
∗
∗
then there exists z ∈ Σ∗ such that v → z and w → z; and R is complete if it is both noetherian and
confluent. Note that if R is special or monadic, then it is length reducing, and if R is length reducing,
then it is noetherian.
Monoid presentations. Every rewriting system R on Σ defines a monoid. The set Σ∗ with concatenation of words as multiplication is a monoid, called the free monoid on Σ. Denote by ρR the smallest
congruence on Σ∗ containing R (called the Thue congruence). We denote by M (Σ; R) the quotient
monoid Σ∗/ρR . The elements of M (Σ; R) are the congruence classes [u]M = {w : w ρR u}, where
u ∈ Σ∗ . Whenever possible and when it is clear from the context, we shall omit the brackets to denote
congruence classes, and thus identify words with the elements of the monoid that they represent.
Suppose M is any monoid such that M ∼
= M (Σ; R) (that is, M is isomorphic to M (Σ; R)). Then
the pair (Σ; R) is a presentation of M with generators Σ and defining relations R, and we say that
M is defined by (Σ; R) or simply by R. A presentation (Σ; R) is said to be finite if both Σ and R are
finite. A monoid M defined by a finite presentation is called finitely presented.
Definition 2.1. Let M = M (Σ; R) be a finitely presented monoid, and let ∼i be one of the conjugacy
relations under consideration (i ∈ {p, o, c}). We say that the i-conjugacy problem for M is decidable
if there is an algorithm that given any pair (u, v) of words in Σ∗ , returns YES if [u]M ∼i [v]M and
NO otherwise. If such an algorithm does not exists, we say that the i-conjugacy problem for M is
undecidable. We have an analogous definition of the decidability of the word problem for M , in which
case we check if [u]M = [v]M .
Monoids with zero: rewriting systems and presentations. Consider a rewriting system R
defined on a set Σ0 = Σ ∪ {0}, where 0 is a symbol not in Σ, and a set R0 of rewriting rules of the
form (x0, 0), (0x, 0) and (00, 0), for any x ∈ Σ. The monoid T = M (Σ0 ; R ∪ R0 ) is a monoid with
zero [0]T . For simplicity, we refer to the pair (Σ0 ; R) as a monoid-with-zero presentation of T . Notice
that the monoid presentation (Σ0 ; R ∪ R0 ) is finite or monadic when (Σ0 ; R) is finite or monadic,
respectively.
If a monoid M is defined by a presentation (Σ; R) then the monoid M 0 , obtained from M by adding
a zero element, is defined by the monoid-with-zero presentation (Σ; R). Observe that [0]M 0 is the zero
in M 0 and that M 0 6= {[0]M 0 }. Regarding these presentations, we can deduce by [3, Proposition 3.1]
that if the rewriting system R on Σ is complete, then so is the new rewriting system R ∪ R0 on Σ0 .
Throughout the text we refer to a presentation as noetherian, confluent, complete, monadic, etc.,
whenever the associated rewriting system has the respective property.
3. Conjugacy in the polycyclic monoids
In this section, we study p-conjugacy and c-conjugacy in the class of polycyclic monoids, an important class of inverse monoids. A monoid M is called an inverse monoid if for every a ∈ M , there
exists a unique a−1 ∈ M (an inverse of a) such that aa−1 a = a and a−1 aa−1 = a−1 [15, p. 145].
In general, p-conjugacy is not transitive in inverse semigroups. For instance, by [9, Proposition 4.2],
p-conjugacy is not transitive in free inverse monoids. We will show that in the polycyclic monoids,
p-conjugacy is transitive for the elements not ∼p -related to zero, and that ∼c ⊂ ∼p .
We note that in the polycyclic monoids, ∼o is the universal relation since every polycyclic monoid
has a zero.
3

3.1. General properties of the polycyclic monoids. Let n ≥ 2. Consider a set An = {p1 , . . . , pn }
−1
−1
−1
and denote by A−1
n a disjoint copy {p1 , . . . , pn }. Let Σ = An ∪ An . Given any x ∈ Σ, we define
−1
−1
−1
−1
x to be pi if x = pi ∈ An , and to be pi if x = pi ∈ An . This notation can be extended to Σ∗
by setting (xw)−1 = w−1 x−1 , for every x ∈ Σ and w ∈ Σ∗ , and 1−1 = 1.
Denote by R the set of rewriting rules on Σ0 = Σ ∪ {0} of the form p−1
i pi = 1, for i ∈ {1, . . . , n},
and of the form p−1
p
=
0,
for
i,
j
∈
{1,
.
.
.
,
n}
and
i
=
6
j.
Consider
the monoid Pn defined by
j
i
the monoid-with-zero presentation (Σ0 ; R). The monoid Pn is called the polycyclic monoid on n
generators. Notice that the given presentation of Pn is monadic, and thus length reducing.
An irreducible element (with respect to R) cannot have a factor of the form p−1
i pj , for any i, j ∈
{1, . . . , n}. Thus, irreducible elements have the form yx−1 , where y, x ∈ A∗n , or the form 0. It is
well known (e.g., [21, subsection 9.3]) that every nonzero element w of Pn has a unique irreducible
representation w of the form yx−1 with y, x ∈ A∗n . Therefore, irreducible elements are in one-to-one
correspondence with elements of the polycyclic monoid. We deduce the following:
Lemma 3.1. The monoid-with-zero presentation (Σ0 ; R) of the polycyclic monoid Pn is finite and
complete.
Whenever we write a = yx−1 , it will be understood that x, y ∈ A∗n . Hereafter, we shall identify
irreducible elements with the elements of the polycyclic monoid that they represent.
We will frequently use the following lemma, which follows from the unique representation of the
nonzero elements of Pn .
Lemma 3.2. Consider nonzero elements yx−1 and vu−1 of Pn . Then:
(1) yx−1 · vu−1 6= 0 iff x and v are prefix-comparable;
(2) if yx−1 · vu−1 6= 0, then
(
yzu−1
if v = xz ,
−1
−1
yx · vu =
y(uz)−1 if x = vz .
(3) y = v in Pn iff y = v in A∗n , and x−1 = u−1 in Pn iff x = u in A∗n .
An irreducible word is said to be cyclically reduced if it is empty or zero, or if its first letter c
and its last letter d satisfy c 6= d−1 . Every nonzero irreducible word can be written in the form
ryx−1 r−1 , with r ∈ A∗n and yx−1 a cyclically reduced word. From any irreducible word a we compute
a cyclically reduced word e
a in the following way: if a is cyclically reduced, we let e
a be equal to a;
otherwise, a = ryx−1 r−1 as above, so we let e
a be the (possibly empty) cyclically reduced word yx−1 .
We obtain the following fact for any nonzero irreducible word a ∈ Pn :
(3.4)

a = re
ar−1 for some word r ∈ A∗n .

For each nonzero element a = yx−1 ∈ Pn , denote by ρ(a) the irreducible word obtained from x−1 y.
We also set ρ(0) = 0. Let a = yx−1 ∈ Pn . We record the following facts about e
a and ρ(a):
(a)
(b)
(c)
(d)

ρ(a) is x−1 y reduced in Pn ;
e
a is x−1 y reduced in (Σ, R1 ), where R1 = {(p−1
i pi , 1) : i ∈ {1, . . . , n};
ρ(a) is cyclically reduced;
∗
ρ(a) = e
a ∈ A∗n if x is a prefix of y; ρ(a) = e
a ∈ (A−1
a) = 0
n ) if y is a prefix of x; and ρ(a) = ρ(e
otherwise.

−1
For example, if a = p1 p2 p−1
a = p2 p−1
3 p1 , then e
3 and ρ(a) = 0.
The following lemma can be easily deduced.

Lemma 3.3. For all a = pq −1 · rs−1 ∈ Pn ,

lt


 g

tl−1
g
−1
 lt



(lt)−1

the cyclically reduced word e
a is given by
if
if
if
if

r = qt
r = qt
q = rt
q = rt
4

and
and
and
and

p = sl ,
s = pl ,
p = sl ,
s = pl .

3.2. p-conjugacy in Pn . We first observe that for every a ∈ Pn , a ∼p e
a and a ∼p ρ(a) (by the
definitions of e
a and ρ(a).
Lemma 3.4. Let a ∈ Pn . Then a ∼p 0 if and only if ρ(a) = 0.

Proof. Suppose that a ∼p 0. If a = 0 then ρ(a) = 0. Suppose a 6= 0. Then 0 6= a = pq −1 · rs−1
and 0 = rs−1 · pq −1 , for some p, q, r, s ∈ A∗n . The latter equality implies that p and s are not prefixcomparable (by Lemma 3.2). And the former implies that r = qt or q = rt, for some t ∈ A∗n . Hence,
a = pts−1 (if r = qt) or a = p(st)−1 (if q = rt). Suppose that a = pts−1 . If pt is a prefix of s, then
also p is a prefix of s; and if s is a prefix of pt, then either s is a prefix of p or p is a prefix of s. It
follows that neither pt is a prefix of s nor s is a prefix of pt, which implies ρ(a) = 0. By a similar
argument, we obtain ρ(a) = 0 if a = p(st)−1 . The converse follows from the fact that a ∼p ρ(a). 
Lemma 3.5. Let a and b be nonzero elements of Pn with ρ(a) = ρ(b) = 0. Then a ∼p b if and only
if e
a = eb.

Proof. Suppose that a ∼p b. Then there exist elements x, y, u, v ∈ A∗n such that a = yx−1 · vu−1 and
b = vu−1 · yx−1 . Since a 6= 0, we know that x and v are prefix-comparable. Similarly, since b 6= 0, u
and y are prefix-comparable.
Suppose first that x is a prefix of v and u is a prefix of y, that is, v = xp and y = uq for some
p, q ∈ A∗n . Hence a = uqx−1 xpu−1 = uqpu−1 , and so ρ(a) = qp 6= 0, which is a contradiction.
Similarly, we obtain a contradiction if we assume that v is a prefix of x and y is a prefix of u.
Suppose that x is a prefix of v and that y is a prefix of u, that is, v = xp and u = yq for some
p, q ∈ A∗n . Then a = yx−1 xpq −1 y −1 = y(pq −1 )y −1 and b = xpq −1 y −1 yx−1 = x(pq −1 )x−1 . Thus
−1 = e
]
e
a = pq
b as required. In a similar way we obtain the intended result if v is a prefix of x and u is
a prefix of y.
The converse follows easily by first noticing that a = re
ar−1 and b = sebs−1 , for some r, s ∈ A∗n by
−1
e
(3.4). If e
a = b we get the required result since a = re
as · sr−1 and b = sr−1 · rebs−1 .

The following theorem characterizes p-conjugacy in Pn .

Theorem 3.6. Let a, b ∈ Pn . Then a ∼p b if and only if one of the following conditions is satisfied:
(a) a = ρ(b) = 0 or ρ(a) = b = 0;
(b) ρ(a) = ρ(b) = 0 and e
a = eb;
∗
e
e
a ∼p b in the free monoid A∗n ; or
(c) e
a, b ∈ An and e
∗
∗
a ∼p eb in the free monoid (A−1
(d) e
a, eb ∈ (A−1
n ) .
n ) and e

Proof. Suppose that a ∼p b. If a = 0 or b = 0, then (a) holds by Lemma 3.4. Now assume that a and
b are nonzero elements. Then, there are p, q, r, s ∈ A∗n such that a = pq −1 · rs−1 and b = rs−1 · pq −1 .
By Lemma 3.3, we have: if r = qt and p = sl, then e
a = lt and eb = tl, so (c) holds; if q = rt and s = pl,
g
−1 ; and if q = rt and
then e
a = (lt)−1 and eb = (tl)−1 , so (d) holds; if r = qt and s = pl, then e
a = eb = tl
g
−1
e
e
p = sl, then e
a = b = lt . In the last two cases, we have e
a = b, and so ρ(a) = ρ(b). Thus, in those
cases, either (c) or (d) holds (if ρ(a) = ρ(b) 6= 0), or (b) holds by Lemma 3.5 (if ρ(a) = ρ(b) = 0).
Conversely, if (a) holds then a ∼p b by Lemma 3.4; and if (b) holds then a ∼p b by Lemma 3.5.
Suppose that (c) holds and let e
a = uv and eb = vu, where u, v ∈ A∗n . Then a = puvp−1 and b = qvuq −1
∗
for some p, q ∈ An by (3.4). Hence a = puq −1 · qvp−1 and b = qvp−1 · puq −1 , and so a ∼p b as required.
The proof in the case when (d) holds is similar.

It is worth noting that the nonzero idempotents of Pn form a single p-conjugacy class. Indeed, the
nonzero idempotents have the form xx−1 , and e
a = 1 if and only if a is an idempotent. So, they form
a single p-conjugacy class by Theorem 3.6.
We recall that ∼p is transitive in any free monoid. For the polycyclic monoid, we have the following
result.
Theorem 3.7. In the polycyclic monoid Pn , we have:
(1) for all a, b, c ∈ Pn with b 6= 0, if a ∼p b and b ∼p c, then a ∼p c;
(2) ∼p ◦ ∼p = ∼∗p .
5

Proof. To prove (a), let a, b, c ∈ Pn with b 6= 0. Suppose that a ∼p b ∼p c. If ρ(b) 6= 0 then, by
∗
Theorem 3.6, either e
a, eb, e
c ∈ A∗n or e
a, eb, e
c ∈ (A−1
n ) , and a ∼p c follows since ∼p is transitive in the
free monoid. Suppose that ρ(b) = 0. Then, by Theorem 3.6, ρ(a) = ρ(c) = 0. Thus, if a = 0 or c = 0,
then a ∼p c. Suppose that a 6= 0 and c 6= 0. Then, by Theorem 3.6, e
a = eb = e
c, and so, again by
Theorem 3.6, a ∼p c.
Statement (2) follows from (1).

The relations ∼p and ∼∗p are not equal in Pn . For example, consider the polycyclic monoid P2 with
A2 = {x, y}. Then, for a = xx−1 and c = yy −1 in P2 , a ∼p 0 ∼p c, so a ∼∗p c, but (a, c) ∈
/ ∼p by
Theorem 3.6.
3.3. c-conjugacy in Pn . Referring to the definition of ∼c , we begin with a description of the set
from which the conjugators must be chosen.
Lemma 3.8. For all x, y ∈ A∗n , P(yx−1 ) = {rs−1 : r is a prefix of x}.
Proof. Let rs−1 ∈ P(yx−1 ). Then yx−1 · rs−1 6= 0, and so r and x are prefix-comparable. Suppose
that x is a proper prefix of r, that is, r = xpi t for some pi ∈ An = {p1 , . . . , pn } and t ∈ A∗n .
Let j ∈ {1, . . . , n} with j 6= i. Then (ypj )−1 · yx−1 = (xpj )−1 6= 0, while (ypj )−1 · yx−1 · rs−1 =
(xpj )−1 · rs−1 = 0 since neither xpj is a prefix of r, nor r is a prefix of xpj . This contradicts the
hypothesis that rs−1 ∈ P(yx−1 ). Therefore, r is a prefix of x.
Now, let rs−1 be an element of Pn and assume that r is a prefix of x. Then x = rz for some z ∈ A∗n ,
which gives yx−1 · rs−1 = y(sz)−1 . Thus, for every vu−1 ∈ Pn , vu−1 · yx−1 · rs−1 = vu−1 · y(sz)−1 = 0
iff vu−1 · yx−1 = 0 (see Lemma 3.2). Thus rs−1 ∈ P(yx−1 ).

The following theorem characterizes c-conjugacy in Pn .
Theorem 3.9. Let a, b ∈ Pn . Then a ∼c b if and only if one of the following conditions is satisfied:
(a) a = b = 0;
(b) e
a = eb; or
∗
∗
(c) e
a, eb ∈ (A−1
a ∼p eb in the free monoid (A−1
n ) .
n ) and e

Proof. Suppose that a ∼c b. If a = 0 or b = 0, then (a) holds since [0]c = {0}. Suppose a, b 6= 0.
Then, there exist x, y, u, v ∈ A∗n such that a = yx−1 and b = vu−1 ; and there exist r, s ∈ A∗n such
that rs−1 ∈ P(yx−1 ) and yx−1 · rs−1 = rs−1 · vu−1 . By Lemma 3.8, x = rz for some z ∈ A∗n . By
Lemma 3.2, s and v are prefix-comparable.
Suppose v = sw for some w ∈ A∗n . Then, yx−1 · rs−1 = yz −1 r−1 rs−1 = y(sz)−1 and rs−1 · vu−1 =
−1
rs swu−1 = rwu−1 . Thus, since yx−1 ·rs−1 = rs−1 ·vu−1 , we have y(sz)−1 = rwu−1 , and so y = rw
and u = sz. Hence, a = yx−1 = rw(rz)−1 = r(wz −1 )r−1 and b = vu−1 = sw(sz)−1 = s(wz −1 )s−1 ,
and so (b) holds.
Suppose s = vw for some w ∈ A∗n . Then, yx−1 · rs−1 = y(sz)−1 (as in the previous case) and
−1
rs · vu−1 = rw−1 v −1 vu−1 = r(uw)−1 . Thus, y(sz)−1 = r(uw)−1 , and so y = r and sz = uw.
Since s = vw, we have vwz = uw, which implies that u = vt for some t ∈ A∗n . Thus, uw = vtw,
which implies vwz = vtw, and so wz = tw. By [20, Corollary 5.2], tw = wz implies t ∼p z in A∗n .
−1 = r(rz)
^
−1 = rz^
−1 r−1 = z −1 and e
−1 = v(vt)
^
−1 = vt^
−1 v −1 = t−1 . Hence
]
]
Further, e
a = yx
b = vu
−1 ∗
∗
−1
−1
−1 ∗
e
e
a, b ∈ (An ) . Since t ∼p z in the free monoid An , we have z ∼p t in (An ) , and so e
a ∼p eb in
−1 ∗
(An ) . Hence (c) holds.
Conversely, if (a) holds, then clearly a ∼c b. Suppose that (b) holds, that is, e
a = eb. Let r, s ∈ A∗n
be such that a = re
ar−1 and b = sebs−1 . Then, by Lemma 3.8, rs−1 ∈ P(a), sr−1 ∈ P(b), and
a · rs−1 = re
ar−1 rs−1 = re
as−1 = rs−1 se
as−1 = rs−1 · b ,
b · sr−1 = sebs−1 sr−1 = sebr−1 = sr−1 rebr−1 = sr−1 · a .

∗
−1
Hence a ∼c b. Now, suppose that (c) holds. Since e
a, eb ∈ (A−1
=e
a and z −1 = eb
n ) , then letting t
−1 −1
−1
−1 −1
−1
∗
we have a = yt y = y(yt) and b = vz v = v(vz) for some y, v ∈ An . Moreover, we have
6

∗
∗
′
′
e
a ∼p eb in the free monoid (A−1
n ) , and so t ∼p z in An as well. Hence tw = wz and w t = zw for
′
∗
′ −1
−1
some w, w ∈ An . By Lemma 3.8, y(vw ) ∈ P(a) and v(yw) ∈ P(b). Further,

a · y(vw′ )−1 = y(yt)−1 y(vw′ )−1 = yt−1 (vw′ )−1 = y(vw′ t)−1 =

= y(vzw′ )−1 = y(w′ )−1 (vz)−1 = y(vw′ )−1 v(vz)−1 = y(vw′ )−1 · b ,
b · v(yw)−1 = v(vz)−1 v(yw)−1 = vz −1 (yw)−1 = v(ywz)−1 =
= v(ytw)−1 = vw−1 (yt)−1 = v(yw)−1 y(yt)−1 = v(yw)−1 · a .
Hence a ∼c b, which concludes the proof.



As for p-conjugacy, the nonzero idempotents form a single c-conjugacy class (see Theorem 3.9 and
the paragraph after Theorem 3.6). Moreover, we have the following strict inclusion between ∼c and
∼p .
Corollary 3.10. In the polycyclic monoid Pn , ∼c ⊂ ∼p .
Proof. The inclusion ∼c ⊆ ∼p follows by Theorems 3.6 and 3.9. To show that ∼c is properly contained
in ∼p , consider two distinct generators x and y in An . Let a = xxyx−1 and b = yyxy −1 in Pn . Then
e
a = xy and eb = yx. Hence e
a ∼p eb in the free monoid A∗n , and so a ∼p b in Pn by Theorem 3.6. On
the other hand, none of (a), (b), or (c) of Theorem 3.9 holds for a and b, and so a 6∼c b in Pn .

3.4. Decidability and complexity of conjugacy in Pn . It is known that for free monoids, the
p-conjugacy problem is decidable in linear time [4, Theorem 2.5]. We will show that the same result
is true for the p-conjugacy and c-conjugacy problems for the polycyclic monoids.
The following lemma is a special case of [6, Theorem 4.1].

Lemma 3.11. Let (Σ0 ; R) be the monoid-with-zero presentation of Pn , and let w ∈ Σ∗0 . Then the
irreducible element w ∈ Σ∗0 such that w → w in Pn can be computed in time O(|w|).
(For more details on the big-O notation used in Lemma 3.11, and more generally for basic notions
on complexity theory, see [33, Section 7].)
Lemma 3.12. Let a be an irreducible word of Pn . Then the words e
a and ρ(a), can be computed in
time O(|a|).

Proof. The result is obvious if a = 0. Let a = yx−1 . To compute e
a proceed as follows:
(1) compute the word x−1 y;
(2) reduce x−1 y to an irreducible word u−1 v in (Σ, R1 ) (see (b) above);
(3) output the word e
a = vu−1 .
To compute ρ(a) proceed in the same way to obtain the word vu−1 , and next proceed as follows:
(4) if v and u are non-empty, then output ρ(a) = 0, otherwise output ρ(a) = e
a.
We show that each stage of this algorithm uses O(|a|) steps, and so the result holds. For the first
stage, it is sufficient to scan through the word yx−1 (from left to right), detect the first symbol in
∗
−1
(A−1
followed by the symbols of y. This requires O(|a|) steps. The
n ) , and output the symbols of x
third stage is similar. For the second stage, since R1 is length reducing, we conclude by [6, Theorem 4.1]
that e
a can be computed in O(|a|) steps. Checking if a word is empty can be done in constant time,
and so ρ(a) can be computed in linear time as well.


Theorem 3.13. Let (Σ0 ; R) be the monoid-with-zero presentation of Pn , and let i ∈ {p, c}. Then,
given two words x, y ∈ Σ∗0 , it can be tested in time O(m), where m = max{|x|, |y|}, whether or not
x ∼i y holds in Pn .

Proof. Let x, y ∈ Σ∗0 . By Lemma 3.11, the irreducible words x = a and y = b can be computed in
time O(m), where m = max{|x|, |y|}. Note that |a| ≤ |x| and |b| ≤ |y|. By Lemma 3.12, each of the
words e
a, eb, ρ(a), and ρ(b) can be computed in time O(m).
According to Theorems 3.6 and 3.9, in order to check whether or not x ∼i y holds it suffices to
compute a, b, e
a, eb, ρ(a), and ρ(b), and check whether or not they are equal (as words) or p-conjugate
(in the free monoid). Since the p-conjugacy problem in the free monoids is decidable in linear time,
we deduce the desired result.

7

4. Decidability in finitely presented monoids
In this section, we discuss the decidability of i-conjugacy problems in some classes of finitely
presented monoids.
Separation of conjugacies. Let M be a monoid without zero. Consider the monoid M 0 obtained
from M by adjoining a zero element. It is immediate that ∼o is the universal relation in M 0 , while ∼c
is not universal in M 0 . Now, M 0 has no zero divisors, and hence any two given elements a and b of
0
M are c-conjugate in M 0 if and only if they are o-conjugate in M . Therefore, ∼M
= ∼oM ∪{(0, 0)}
c
0
0
M
M
in M . Similarly, for p-conjugacy we have ∼p = ∼p ∪{(0, 0)}. Thus, if we identify a monoid M
for which ∼o 6= ∼p in M , we then immediately obtain an example of a monoid M 0 where ∼c 6= ∼p ,
∼o 6= ∼p , and ∼o 6= ∼c . To find such a monoid (within a certain class of rewriting systems), consider
the following example from [30, Example 2.2].
Example 4.1. Let M be the monoid defined by the monadic and confluent presentation (Σ; R) with
Σ = {a, b, c} and R = {(ab, b), (cb, b)}. As explained in [30, Example 2.2], we have bac ∼p ba, but
clearly bac and ba are not o-conjugate. Therefore, ∼o 6= ∼p in M , and hence the relations ∼o , ∼p and
∼c are pairwise distinct in M 0 .
We deduce that for monoids defined by monadic presentations, the relations ∼c , ∼p and ∼o may
be different, even when such systems are also finite and confluent.
Finite complete presentations. Narendran and Otto [25, Lemma 3.6] constructed a finite complete
presentation (Σ; R) such that the o-conjugacy problem is undecidable for the monoid M = M (Σ; R).
Using the above observation, we obtain the following result.
Proposition 4.2. There is a monoid defined by a finite complete presentation for which the cconjugacy problem is undecidable.
Proof. Consider the monoid M 0 obtained from the monoid M defined by Narendran and Otto in
[25, page 35] which has undecidable o-conjugacy problem. Since M is defined by a finite complete
presentation, the monoid M 0 is also defined by a finite complete presentation by [3, Proposition 3.1]. It
0
= ∼oM ∪{(0, 0)}, and hence M 0 has undecidable
can be seen that M does not have a zero. Thus ∼M
c
c-conjugacy problem.

Special presentations. It is easy to see that a monoid defined by a special presentation has a zero
if and only if it is trivial. Hence, within this class we have ∼c = ∼o . Zhang [34, Theorem 3.2]
proved that in every monoid M defined by a special presentation, the relations ∼p and ∼o also
coincide. Otto [30, Theorem 3.8] proved that if M is a monoid defined by a finite, special, and
confluent presentation, then the o-conjugacy problem for M is decidable (and so the p-conjugacy and
c-conjugacy problems are also decidable for M ).
One-relator monoids. A monoid M is called a one-relator monoid if it admits a finite presentation
with one defining relation, which we will write as (Σ; u = v) instead of (Σ, {(u, v)}). Many decision
problems have been studied in the class of one-relator monoids. For example, it is decidable whether a
one-relator monoid has a zero [8, Proposition 14]. Moreover, a one-relator monoid M containing a zero
admits a presentation ({a}; ak+1 = ak ), where k is a positive integer [8, the proof of Proposition 14].
It is easy to check that in this monoid ∼p = ∼c = {(x, x) : x ∈ M } and ∼o = M × M .
By the foregoing argument, if M is a one-relator monoid with a zero, then the c-conjugacy and oconjugacy problems for M are decidable. If M has no zero, then ∼c = ∼o . Therefore, the c-conjugacy
problem for such an M is decidable if and only if the o-conjugacy problem for M is decidable.
Some specific results concerning the decidability of the o-conjugacy problem for this class can be
found in [34, 35].
5. Independence in finitely presented monoids
In this section, we prove that for finitely presented monoids, the word problem and the c-conjugacy
problem are independent, and that the p-conjugacy problem and the c-conjugacy problem are independent.
8

Definition 5.1. Decision problems P1 and P2 are independent if there exist finitely presented monoids
M1 and M2 such that for M1 , P1 is decidable and P2 is undecidable; and for M2 , P2 is decidable and
P1 is undecidable.
Theorem 5.2. For finitely presented monoids, the word problem and the c-conjugacy problem are
independent.
Proof. First, there are finitely presented groups with decidable word problem but undecidable conjugacy problem [5, 10]. Let G be a finitely presented group. A finite group presentation of G can be
effectively converted to a finite (special) monoid presentation (Σ; R) such that G ∼
= M (Σ; R). It follows that there is a monoid M defined by a finite presentation for which the word problem is decidable
and the c-conjugacy problem is undecidable.
We will construct a finitely presented monoid for which the converse is true. Let G = M (Σ; R)
be a finitely presented group with undecidable word problem (see [28]), where (Σ; R) is a monoid
presentation. Let a and b be symbols not in Σ, and let M = M (A; T ) be the monoid defined by the
presentation (A; T ), where
A = Σ ∪ {a, b} ,
T = R ∪ {(xa, ax) : x ∈ Σ} ∪ {(bx, b) : x ∈ Σ ∪ {a}} ∪ {(xb, b) : x ∈ Σ} ∪ {(aa, a)} .
Notice that G is a subgroup of M . The word problem for M is undecidable (since otherwise it would
be decidable for G). It is easy to see that M has no zero and that each congruence class [u] = [u]M
has a representative of the form bp , aw, abp , or w, where p is a positive integer and w ∈ Σ∗ .
Observe that whenever a rewriting rule from T is applied to a word in A∗ , the number of occurrences
of b does not change. Thus, for all u1 , u2 ∈ A∗ , if [u1 ] = [u2 ], then |u1 |b = |u2 |b . Let [u], [v] ∈ M .
Suppose [u] ∼c [v]. Then [u][t] = [t][v] for some t ∈ A∗ . Thus [ut] = [tv], and so |u|b = |v|b by the
foregoing observation.
Conversely, suppose |u|b = |v|b . If |u|b = |v|b = 0, then [u] ∼c [v] since [u][ab] = [ab] = [ab][v] and
[v][ab] = [ab] = [ab][u]. Suppose |u|b = |v|b = p > 0. If [u] = [v], then [u] ∼c [v]. Suppose [u] 6= [v].
Then [u] = [bp ] and [v] = [abp ], or vice versa. We may assume that [u] = [bp ] and [v] = [abp ]. Then
[u] ∼c [v] since [u][b] = [bp+1 ] = [b][v] and [v][a] = [abp ] = [a][u].
We have proved that for all u, v ∈ A∗ , [u] ∼c [v] if and only if |u|b = |v|b . Hence the c-conjugacy
problem for M is decidable.

Theorem 5.3. For finitely presented monoids, the p-conjugacy problem and the c-conjugacy problem
are independent.
Proof. Let M = M (A; T ) be the monoid from the proof of Theorem 5.2. For w ∈ Σ∗ , we will write
[w] = [w]M for the element of the monoid M , and [w]G for the element of the group G.
Let u, v ∈ Σ∗ . Suppose [u] ∼p [v], that is, [u] = [s][t] and [v] = [t][s] for some s, t ∈ A∗ . The
words s and t cannot contain b since in the presentation (A; T ) a word with b cannot be reduced to a
word without b. But then s and t cannot contain a either since a word with a cannot be reduced to
a word without a unless b is also present. It follows that [u]G = [s]G [t]G and [v]G = [t]G [s]G , and so
[u]G ∼p [v]G .
We have proved that for all u, v ∈ Σ∗ , if [u] ∼p [v] in M , then [u]G ∼p [v]G in G. The converse
is clearly true. Since ∼p in G is the group conjugacy and G has undecidable word problem (and so
undecidable conjugacy problem), it follows that the p-conjugacy problem for M is undecidable. We
have already established in the proof of Theorem 5.2 that the c-conjugacy problem for M is decidable.
We will now present a monoid that has decidable p-conjugacy problem and undecidable c-conjugacy
problem. Osipova [29] showed that there exists a finitely presented monoid M that has decidable
p-conjugacy problem and undecidable l-conjugacy problem, where the l-conjugacy stands for the
following relation ∼l : given a, b ∈ M , a ∼l b if and only if there exists g ∈ M such that ag =
gb. Osipova’s proof follows the following steps (we use the original notation): (i) she considers a
finitely presented monoid Π1 = M (U1 ; B0 ) with undecidable p-conjugacy problem; (ii) she extends the
alphabet U1 to U3 = U1 ∪ {c, d, e1 , . . . , em }, where m = |U1 | + 2|B0|, and builds a new finitely presented
monoid Π3 = M (U3 ; B3 ); (iii) she shows [29, Lemma 4] that for all words Q, R ∈ U1∗ , Q ∼p R in Π1 if
and only if there exists X ∈ U3∗ such that XcQd = cRdX in Π3 ; (iv) she concludes [29, Theorem 2]
9

that the l-conjugacy problem for Π3 is undecidable; (v) she shows [29, Theorem 3] that the p-conjugacy
problem for Π3 is decidable.
Now, notice that ∼p is symmetric, and hence, by [29, Lemma 4], for all words Q, R ∈ U1∗ , we have
Q ∼p R in Π1 if and only if there exist X, Y ∈ U3∗ such that XcQd = cRdX and Y cRd = cQdY in
Π3 . Equivalently, Q ∼p R in Π1 if and only if cQd ∼o cRd in Π3 . Therefore, Π3 has undecidable
o-conjugacy problem.
The set B3 of Π3 has rewriting rules of the form (ei cGi , cei ), (ei bj , bj ei ), and (ei d, G′i dei ), where
i = 1, . . . , m and j = 1, . . . , n, the bj are the letters of the alphabet U1 , and the Gi and G′i are fixed
words in U1∗ [29, pages 70 and 71]. From the form of these rules, we can easily deduce that any two
words in U3∗ that are equal in Π3 have the same number of occurrences of the letter c. Therefore, Π3
does not have a zero since the zero element, say [z], would satisfy the identity [z][c] = [z], contradicting
the above observation. Hence ∼o = ∼c , and hence Π3 has undecidable c-conjugacy problem.

We do not know if the c-conjugacy problem and the o-conjugacy problem are independent for
finitely presented monoids. Consider a finitely presented monoid M without zero that has undecidable
c-conjugacy problem. Let M 0 be the monoid M with a zero 0 adjoined. Then M 0 is finitely presented
and the c-conjugacy problem for M 0 is undecidable (since for all a, b ∈ M , a ∼c b in M 0 if and only
a ∼c b in M ). On the other hand, the o-conjugacy problem for M 0 is decidable since ∼o = M 0 × M 0 .
Now, suppose M is a finitely presented monoid that has decidable c-conjugacy problem. Then, if we
could prove that M has a zero, then the algorithm that always says YES would decide if [u]M ∼o [v]M
for all [u]M , [v]M ∈ M . Further, if we could prove that M has no zero, then the algorithm that works
for ∼c would also work for ∼o . However, suppose that the statement “M has a zero” can neither be
proved nor disproved. Then it is conceivable that no algorithm for o-conjugacy problem in M exists,
that is, that o-conjugacy problem is undecidable for M .
6. Open problems
We conclude this paper with some natural questions related to conjugacy and presentations. As we
have noticed in Section 5, the independence of the c-conjugacy and o-conjugacy problems is related to
the decidability of a monoid having a zero. Hence whether the o-conjugacy and c-conjugacy problems
are independent hinges on the answer to the following question.
Problem 6.1. Does there exist a finitely presented monoid M for which it is undecidable if it has a
zero, the o-conjugacy problem for M is undecidable, and the c-conjugacy problem for M is decidable?
The word problem is decidable for certain restricted classes of finitely presented monoids, in particular those admitting a finite complete presentation. It is then natural to consider this property as
a useful tool in proving decidability results. In the class of monoids defined by finite, length-reducing,
and confluent rewriting systems, the o-conjugacy problem is decidable [24, Corollary 2.7]. It is also
decidable if such monoids have a zero. However, the p-conjugacy problem is undecidable in this
class [25, Corollary 2.4].
Problem 6.2. Is the c-conjugacy problem decidable for the class of monoids defined by finite, lengthreducing, and confluent rewriting systems?
This problem could be approached by first considering the class of finite monadic confluent rewriting
systems, as it is the case of polyclyclic monoids.
Problem 6.3. Is the c-conjugacy [p-conjugacy] problem decidable for the class of monoids defined
by finite, monadic, and confluent rewriting systems?
7. Acknowledgments
The first and second authors acknowledge that this work was developed within FCT projects CAUL
(PEst-OE/MAT/UI0143/2014) and CEMAT-CIÊNCIAS (UID/Multi/04621/2013).
The second author was also supported by Simons Foundation Collaboration Grant 359872.
The fourth author was supported by the Fundação para a Ciência e a Tecnologia (Portuguese
Foundation for Science and Technology) through the project UID/MAT/00297/2013 (Centro de
Matemática e Aplicações).
10

Finnaly, the first, second and fourth authors were supported by FCT through project “Hilbert’s
24th problem” (PTDC/MHC-FIL/2583/2014).
References
[1] J. Araújo, M. Kinyon, J. Konieczny, and A. Malheiro, Four notions of conjugacy for abstract semigroups, to appear
in Proc. Roy. Soc. Edinburgh Sect. A.
[2] J. Araújo, J. Konieczny, and A. Malheiro, Conjugation in semigroups, J. Algebra 403 (2014), 93–134.
[3] J. Araújo and A. Malheiro, On finite complete presentations and exact decompositions of semigroups, Comm.
Algebra 39 (2011), 3866–3878.
[4] J. Avenhaus and K. Madlener, String matching and algorithmic problems in free groups, Rev. Columbiana Mat.
15 (1980), 1-16.
[5] L.A. Bokut, Degrees of unsolvability of the conjugacy problem for finitely presented groups, Algebra i Logika 7
(1968), no. 5, 4–70, no. 6, 4–52. (Russian)
[6] R.V. Book, Confluent and other types of Thue systems, J. Assoc. Comput. Mach. 29 (1982), 171–182.
[7] R.V. Book and F. Otto, String-rewriting Systems, Texts and Monographs in Computer Science, Springer-Verlag,
New York, 1993.
[8] A. J. Cain and V. Maltcev, Decision problems for finitely presented and one-relation semigroups and monoids,
Internat. J. Algebra Comput. 19 (2009), 747–770.
[9] C. Choffrut, Conjugacy in free inverse monoids, Internat. J. Algebra Comput. 3 (1993), 169–188.
[10] D. J. Collins, Recursively enumerable degrees and the conjugacy problem, Acta Math. 122 (1969) 115–160.
[11] J. Cuntz, Simple C ∗ -algebras generated by isometries, Comm. Math. Phys. 57 (1977), 173–185.
[12] P.M. Higgins, Techniques of Semigroup Theory, Oxford Science Publications. Oxford University Press, New York,
1992.
[13] P.M. Higgins, The semigroup of conjugates of a word, Internat. J. Algebra Comput. 16 (2006), 1015–1029.
[14] P.M. Hines, An application of polycyclic monoids to rings, Semigroup Forum 56 (1998), 146–149.
[15] J.M. Howie, Fundamentals of Semigroup Theory, Oxford Science Publications, Oxford, 1995.
[16] G. Kudryavtseva, On conjugacy in regular epigroups,
http://arxiv.org/abs/math/0605698.
[17] D.G. Jones and M.V. Lawson, Strong representations of the polycyclic inverse monoids: cycles and atoms, Period.
Math. Hungar. 64 (2012), 53–87.
[18] G. Kudryavtseva and V. Mazorchuk, On conjugation in some transformation and Brauer-type semigroups, Publ.
Math. Debrecen 70 (2007), 19–43.
[19] G. Kudryavtseva and V. Mazorchuk, On three approaches to conjugacy in semigroups, Semigroup Forum 78 (2009),
14–20.
[20] G. Lallement, Semigroups and Combinatorial Applications, John Wiley & Sons, New York, 1979.
[21] M. V. Lawson, Primitive partial permutation representations of the polycyclic monoids and branching function
systems, Period. Math. Hungar. 58 (2009), 189–207.
[22] R.C. Lyndon and M.P. Schützenberger, The equation am = bn cp in a free group, Michigan Math. J. 9 (1962),
289–298.
[23] A. Markov, The impossibility of certain algorithms in the theory of associative systems. II, Doklady Akad. Nauk
SSSR (N.S.) 58 (1947), 353–356. (Russian)
[24] P. Narendran and F. Otto, Complexity results on the conjugacy problem for monoids, Theoret. Comput. Sci. 35
(1985), 227–243.
[25] P. Narendran and F. Otto, The problems of cyclic equality and conjugacy for finite complete rewriting systems,
Theoret. Comput. Sci. 47 (1986), 27–38.
[26] M. Nivat and J.F. Perrot, Une généralisation du monoı̈de bicyclique, C. R. Acad. Sci. Paris Sér. A-B 271 (1970),
A824–A827.
[27] P.S. Novikov, Unsolvability of the conjugacy problem in the theory of groups, Izv. Akad Nauk SSSR. Ser. Mat. 18
(1954), 485–524. (Russian)
[28] P.S. Novikov, On the algorithmic insolvability of the word problem in group theory, American Mathematical Society
Translations, Ser 2 9 (1958), 1–122.
[29] V.A. Osipova, On the conjugacy problem in semigroups, Trudy Mat. Inst. Steklov. 133 (1973), 169–182, 275.
(Russian)
[30] F. Otto, Conjugacy in monoids with a special Church-Rosser presentation is decidable, Semigroup Forum 29
(1984), 223–240.
[31] E.L. Post, Recursive unsolvability of a problem of Thue, J. Symbolic Logic 12 (1947), 1–11.
[32] N. Ruškuc, Semigroup Presentations, Ph.D. Thesis, University of St Andrews, 1995.
[33] M. Sipser, Introduction to the Theory of Computation, International Thomson Publishing, 1996.
[34] L. Zhang, Conjugacy in special monoids, J. Algebra 143 (1991), 487–497.
[35] L. Zhang, On the conjugacy problem for one-relator monoids with elements of finite order, Internat. J. Algebra
Comput. 2 (1992), 209–220.
11

Universidade Aberta, R. Escola Politécnica, 147, 1269-001 Lisboa, Portugal
CEMAT-Ciências Universidade de Lisboa, 1749-016 Lisboa, Portugal
E-mail address: jjaraujo@fc.ul.pt
Department of Mathematics, University of Denver, Denver, CO 80208
E-mail address: mkinyon@du.edu
Department of Mathematics, University of Mary Washington, Fredericksburg, VA 22401.
E-mail address: jkoniecz@umw.edu
Centro de Matemática e Aplicações, Faculdade de Ciências e Tecnologia, Universidade Nova de Lisboa,
2829–516 Caparica, Portugal
Departamento de Matemática, Faculdade de Ciências e Tecnologia, Universidade Nova de Lisboa, 2829–
516 Caparica, Portugal
E-mail address: ajm@fct.unl.pt

12

