Commutativity in Free inverse monoids

Christian Choffrut

L.I.T.P., Institut Blaise Pascal, Université Paris 7

Flavio D’Alessandro

Dipartimento di Matematica ed Applicazioni, Universitá degli Studi “Federico II” di Napoli and LIAFA, Institut Blaise Pascal, Université Paris 7

Abstract This article characterizes the solutions of the commutativity equation xy = yx in free inverse monoids. The main result implies the following interesting property that is the natural generalization to free inverse monoids of the solutions of the same equation in free monoids. Let x and y be non-idempotent elements of a free inverse monoid such that xy = yx. Then there exist some elements χ and z such that x and y are conjugate by χ to some positive powers of z, namely xχ = χz^{n} and yχ = χz^{m}, with n, m ≥ 1. We also show that the centralizer of a given non idempotent element is a rational, non recognizable subset of the free inverse monoid.

1 Introduction

This paper is mainly concerned with the commutativity equation xy = yx in free inverse monoids. In free monoids, two words x and y commute if and only if they are powers of a unique word z. A similar result holds in free groups (cf. [12]). The monoids where this equation has been studied are relatively rare.

In contrast to free monoids, free inverse monoids are not cancellative which makes it difficult to solve equations. In particular, there is no reason why solutions could be described by “parametric expressions” as understood in [11] for instance. Instead, we can try to design procedures that generate all solutions of a given equation as simply as possible. This is what we achieve here.

It is easy to solve the commutativity equation when x is supposed to be idempotent. Since two idempotents commute in inverse monoids, the only interesting case is when y is non idempotent. Denoting by u the canonical image of y in the free group, and assuming x fixed, we prove that there exists an element y_{u} such that xy = yx holds if and only if y = ey_{u} for some idempotent e^{2} = e (in other words, the set of solutions is an ideal relative to the natural order relation in free inverse semigroups, cf. [8], p. 137).

We tackle then the case where both x and y are non-idempotent. Elementary computations show that in free inverse monoids over one generator, the same pattern of solutions as in free monoids holds, namely xy = yx if and only if x and y belong to the submonoid generated by one element. However, this is no longer valid when the free inverse monoid has two or more generators. Our main result is rather technical, but has an interesting consequence that can be understood in this informal exposition and that should be viewed as the natural extension of the condition for free monoids. If xy = yx holds, then there exist two elements χ and z and two positive integers n and m, such that

xχ = χz^{n}  and  yχ = χz^{m}.

is satisfied. Borrowing the terminology of groups, the latter is equivalent to saying that x and y are conjugate via a common element χ to two positive powers of a third element z. This is a weaker condition than the one that holds in free monoids, but it does not seem easy to improve it (see, e.g., Example 4.1). Also, it is worthwhile noticing that the necessary condition we get is of the same flavour as many other results in different areas of non commutative algebra, e.g., in the algebra of polynomials, [1] (resp. of formal power series, [3]), the centralizer of an element is isomorphic to the subalgebra generated by a polynomial (resp. a formal series) in one variable. A similar result holds in matrix algebras, under an hypothesis on the characteristic polynomial of the matrix (cf. [6], Section VIII). More recently, other structures were proved to enjoy the very same property [7], Thm 15.5.

The basic idea of the proof is to transform the commuting elements x and y by simultaneous conjugation (i.e., through a common factor), to two commuting elements x′ and y′ that have such a simple form that they can be treated like words in a free monoid. It then suffices to apply Fine and Wilf’s famous Theorem, [5].

As already said, we were not able to give a purely algebraic characterization of the pairs of commuting elements and actually we doubt very much that it exists. All we could do is, starting from two powers of some element, give conditions on how to reverse the above procedure in order to guarantee that the pairs of elements thus obtained commute.

We use two main tools for studying commutativity: Munn’s characterization of the elements of the free inverse monoid based on the concept of walks in the Cayley graph of the free group and the notion of canonical factorization which is useful to deal with the elements of these monoids in absence of cancellativity and which is a specialization of the notion of standard decomposition introduced in [2].

We close the present introduction with a short comment on the structure of the article. In Section 2, we recall the main definitions and notions and in particular the valuable representation of the elements of a free inverse monoid due to Munn. We also introduce the notion of canonical factorization. In Section 3 we solve the case of the monogenic free inverse monoid. In Section 4, we characterize the set of pairs of commuting elements. In the last section we prove that the centralizer is a rational subset.

2 Preliminaries

2.1 Free monoids, free groups

In order to make this paper self-contained, we recall all the basic notions that will be used in this work. We follow [9], [14] and [11] for general definitions and concepts concerning semigroups, inverse semigroups and groups, respectively.

In what follows, Σ denotes a finite set or alphabet and Σ^{∗} the free monoid over Σ. The elements of Σ are letters and those of Σ^{∗} words. The identity element of Σ^{∗} is denoted by 1_{Σ^{∗}} or simply by 1 when no confusion may arise.

A word u is a prefix of a word v if there exists w such that v = uw. A subset X of Σ^{∗} is said to be prefix-closed if, for any px ∈ X and p ∈ Σ^{∗} one has p ∈ X. The prefix-closure of X, denoted by Pref(X), is the least prefix-closed subset which contains X.

Let Σ̃ = Σ ∪ \overline{Σ}, where \overline{Σ} is a disjoint copy of Σ. We set \overline{(σ̄)} = σ and we extend this notation to Σ̃^{∗} by setting \overline{1} = 1 and, for all σ in Σ̃ and u in Σ̃^{∗}, by setting \overline{uσ} = σ̄ū.

The free group generated by Σ, denoted by F (Σ), is the quotient of Σ̃^{∗} by the congruence generated by the relation \{σ\overline{σ} = 1 | σ ∈ Σ̃\}. We denote by β : Σ̃^{∗} → F (Σ) the canonical epimorphism associated to F (Σ).

A word in Σ̃^{∗} is reduced if it does not contain factors of the form σ\overline{σ}, with σ ∈ Σ̃. Furthermore, a reduced word in Σ̃^{∗} is cyclically reduced if it is not of the form σv\overline{σ}, with σ ∈ Σ̃. It is a well-known fact that every element w in Σ̃^{∗} is congruent to a unique reduced word, denoted by ρ(w). The mapping ρ : Σ̃^{∗} → Σ̃^{∗} is the Dyck reduction. Since ρ(w) = ρ(v) implies β(w) = β(v), there exists a (unique) injective mapping ι : F (Σ) → ρ(Σ̃^{∗}) such that ι ∘ β = ρ, that is ι(u) is the (unique) reduced word in the class β^{−1}(u). In the sequel, we find it convenient to identify an arbitrary element x of F (Σ) with the word ι(x) and more generally, any subset X of F (Σ) with the subset ι(X). In this sense, the elements of F (Σ) can be considered as (reduced) words of Σ̃^{∗}. A subset X of F (Σ) is said to be prefix-closed if ι(X) is itself prefix-closed and the prefix-closure of X is the image by β of the prefix-closure of ι(X). Finally, an element v ∈ F (Σ) is a prefix of an element u of F (Σ) if ι(v) is a prefix of ι(u). Equivalently, v is a prefix of u if and only if ι(v)ι(v^{−1}u) = ι(u) if and only if there exists an element w such that vw = u where the product vw is without cancellation. For instance, the prefixes of a^{−1}ba^{−1}b^{−1} are 1, a^{−1}, a^{−1}b, a^{−1}ba^{−1} and a^{−1}ba^{−1}b^{−1}.

Let M be an arbitrary monoid. An element t ∈ M is said to be primitive if t = u^{n} implies that n = 1. It is well-known that all elements different from 1 ∈ Σ^{∗} (resp. 1 ∈ F (Σ)) are powers of a unique primitive element called its root.

2.2 The Free Inverse Monoid

2.2.1 General definitions

We now introduce the definition and some properties of the free inverse monoid. The free inverse monoid generated by Σ, denoted by F IM(Σ), is the quotient of Σ̃^{∗} by the congruence generated by the relation {xx̄x = x | x ∈ Σ̃^{∗}} ∪ {xx̄yȳ = yȳxx̄ | x, y ∈ Σ̃^{∗}}. We denote by γ the canonical epimorphism of Σ̃^{∗} onto F IM(Σ).

For every u and v ∈ Σ̃^{∗} the condition γ(u) = γ(v) implies β(u) = β(v), so there exists a (unique) surjective morphism α : F IM(Σ) → F (Σ) such that β = α ∘ γ.

[figure: Σ̃^{∗}; γ; F IM(Σ); α; F (Σ); Fig. 1]

2.2.2 Munn’s representation

Munn provided a very useful description of geometrical nature of the free inverse monoid ([13] Theorem 2.8, see also [14], [15], [16]). This description is based on the Cayley graph Γ(Σ) of the free group F (Σ). We recall that the vertices of Γ(Σ) are labelled by the elements of F (Σ) and are therefore represented by reduced words (over Σ̃).

Since most of our examples are considered in the free inverse monoid F IM(Σ) over the two-letter alphabet Σ = {a, b}, we shall consider the Cayley graph Γ of the free group F ({a, b}). For this reason, we fix here a graphical convention to represent Γ. Consider the vertex of Γ labelled by the non-empty reduced word u. It has 4 direct neighbors labelled by ρ(ud), with d ∈ Σ̃ arranged in the 4 cardinal directions east, north, west and south. For example, the vertex in Γ with label u = ab has the 4 direct neighbors respectively labelled by aba, abb, abā, and a.

[figure: abā; ab; aba; abb; a; Fig. 2]

Also, it is possible to consider the graph Γ as a tree where the root is the vertex labelled by 1 ∈ F (Σ). The root has 4 descendants labelled by a, b, ā, b̄. Any other vertex labelled by u ≠ 1 say, has 3 descendants labelled by uc where c̄ is an arbitrary letter different from the last letter of u. In the sequel, for the sake of simplicity, the labels of the vertices of Γ will be omitted.

For every word u ∈ Σ̃^{∗}, the Munn tree T (u) is the (finite) subtree of Γ(Σ) specified by the (unique) walk spelled by u which starts from the origin of Γ(Σ), i.e. the vertex labelled by 1_{F (Σ)}, and ends in β(u). T (u) is then a connected subgraph of Γ(Σ) which contains the origin of Γ(Σ) and, thus, it is represented by a prefix-closed subset of F (Σ). The following characterization is crucial, [13], Thm VIII, 1.5.

Theorem 1 (Munn, 1974) For any u and v in Σ̃^{∗} the following holds:

γ(u) = γ(v)  if and only if  (T (u), β(u)) = (T (v), β(v))

Conversely, for every pair (T, w) where T ⊆ F (Σ) is prefix-closed and w ∈ T there exists a word u ∈ Σ̃^{∗} such that T (u) = T and β(u) = w

As a result, every class of the congruence γ^{−1} ∘ γ, that is every element x in F IM(Σ), is uniquely determined by a finite prefix-closed subset of F (Σ), denoted by T (x), which stands for the common images T (u) of all possible representatives u of the class x, along with an element of F (Σ) which is in T (x), namely α(x). The pair (T (x), α(x)) is a rooted tree.

In terms of this representation, the product of two elements x = (T (x), α(x)) and y = (T (y), α(y)) is represented by

xy = (T (x) ∪ α(x)T (y), α(xy)) (1)

where the product α(x)T (y) is understood in F (Σ).

As a consequence, every element x = (T (x), α(x)) in F IM(Σ) will be graphically represented as shown in the following example.

Example 2.1

Let x = γ(āb̄ābb̄abbb̄aaābabbb̄a) be in F IM(a, b). Then x is represented by the rooted tree

[figure: Fig. 3]

The origin of the walk is represented by an incoming and the last visited vertex by an outgoing arrow. By convention the letters a and ā are represented by horizontal segments and the letters b and b̄ by vertical segments (the orientations of the edges are omitted) □

Theorem 1 helps interpret certain properties of free inverse monoids, e.g.

x is idempotent if and only if α(x) = 1 (2)

Convention In order to simplify notations it is often convenient to identify an element u of F (Σ) with its image γ(ι(u)) in F IM(Σ). Thus if u ∈ F (Σ) and x ∈ F IM(Σ) we will indulge in writing ux instead of the more correct form γ(ι(u))x. With this identification, the Munn tree associated with an element u of the free group is simply a path connecting the vertices labelled by 1 and u without visiting twice the same vertex.

As an application of Munn’s representation let us establish the following useful result.

Lemma 2.1 Let x ∈ F IM(Σ) and g, h ∈ F (Σ). Then x ∈ gF IM(Σ)h if and only if g and α(x)h^{−1} belong to T (x)

Proof. If x = gyh then we have T (x) = T (g) ∪ gT (y) ∪ gα(y)T (h). Since g ∈ T (g) we obtain g ∈ T (x). Now, gα(y) ∈ T (x) and gα(y)h = α(x), thus α(x)h^{−1} ∈ T (x). Conversely, observe that g^{−1}T (x) is prefix-closed. Indeed, if uv ∈ g^{−1}T (x) where the product uv is with no cancellation, then guv ∈ T (x). If the product (gu)(v) is with no cancellation, then gu ∈ T (x), i.e., u ∈ g^{−1}T (x). Now if (gu)(v) is with cancellation, then g = g_{1}u^{−1}. Because of g ∈ T (x) we have g_{1} = gu ∈ T (x), thus u ∈ g^{−1}T (x). Furthermore, g^{−1}T (x) contains g^{−1}α(x)h^{−1}. By Theorem 1 there exists y ∈ F IM(Σ) with T (y) = g^{−1}T (x) and α(y) = g^{−1}α(x)h^{−1}. Then x = gyh holds since α(gyh) = α(x) and

T (gyh) = T (g) ∪ gT (y) ∪ α(x)h^{−1}T (h) = T (x)

This last equality follows from 1) g ∈ T (x) implies T (g) ⊆ T (x), 2) gT (y) = T (x) and 3) α(x)h^{−1} ∈ T (x) ⊆ Pref (α(x)h^{−1})

In the sequel we will indifferently denote the inverse of every element x of the free group F (Σ) by x̄ or by x^{−1}. This convention will be also used to denote the inverse of every x in F IM(Σ).

2.2.3 Commutation and conjugation

As a conclusion of the present section, we recall some results concerning the so-called conjugacy problem in monoids. Let G be a group. Two elements x and y in G are said to be conjugate if and only if y = gxg^{−1}, for some g ∈ G. In groups, the conjugacy relation is related to commutativity by a well-known fact stating that the index i of the centralizer C_{G}(x) = {y ∈ G | xy = yx} of x in G, i.e. the cardinality of the set G/C_{G}(x), equals the number of distinct conjugates of x, i.e. i = Card({gxg^{−1} | g ∈ G}).

On the other hand, from the condition y = gxg^{−1}, it follows that y = g(xg^{−1}) and x = (xg^{−1})g or, multiplying on the right by g, yg = gx. Then conjugacy in groups is generalized to a monoid M in two different ways. Let x, y in M. Then x and y are said to be transposed, and we write x T y, if and only if there exist u, v ∈ M for which x = uv and y = vu holds. Moreover, x and y are said to be conjugate, and we write x C y, if and only if xz = zy for some z ∈ M. It is easily seen that T is reflexive, symmetric but not necessarily transitive, and that C is reflexive, transitive but not necessarily symmetric. In general the transitive closure of T is contained in C, i.e. T^{∗} = ⋃_{k≥0}T^{k} ⊆ C. In free monoids, the two relations T and C coincide, [9], lemma 5.1. Recently it was shown that in free inverse monoids the condition C = T^{∗} holds, up to a technical restriction, i.e. the equality is valid for non-idempotent elements, [2]. It follows immediately that C is an equivalence relation. Furthermore, the same paper proved the decidability of the conjugacy problem. We finally remark that P. V. Silva extended these last results to a certain class of finitely generated inverse monoids, [17].

3 The case of monogenic free inverse monoids

We shortly recall how to specialize Munn’s representation of the free inverse monoid F IM(a) over one generator, say a (see [14], chapter IX). It provides a useful tool for carrying out computations in this monoid.

Since the free group F (a) over a is isomorphic to the additive group ZZ of integers, in the present case every prefix-closed subset X of F (a) can be viewed as an integer interval containing 0

{i ∈ ZZ | l ≤ i ≤ r} = [l, r] where l ≤ 0 ≤ r

Then the Munn’s representation (T (x), α(x)) of x ∈ F IM(a) can be identified with the triple (l, n, r) with −l, r ∈ IN and l ≤ n ≤ r. The interval [l, r] represents the prefix-closed subset T (x) and n satisfies α(x) = a^{n}.

With respect to such a representation, it is immediate to verify that the product of any two elements

x_{1} = (l_{1}, n_{1}, r_{1}) and x_{2} = (l_{2}, n_{2}, r_{2})

is given by

(min{l_{1}, n_{1} + l_{2}}, n_{1} + n_{2}, max{r_{1}, n_{1} + r_{2}})

(l, n, r)^{k} = \{ \begin{matrix}(l, kn, (k − 1)n + r) & if & k > 0, n > 0 \\ ((k − 1)n + l, kn, r) & if & k > 0, n < 0 \\ (kn + l, kn, r − n) & if & k < 0, n > 0 \\ (l − n, kn, kn + r) & if & k < 0, n < 0 \end{matrix} (3)

In particular we have

x̄ = (l, n, r)^{−1} = (−n + l, −n, r − n). (4)

and for all n > 0

(l, n, r) = (l, 1, 1 + r − n)^{n} (5)

(l, −n, r) = (−1 + n + l, −1, r)^{n}. (6)

Thus, an element x = (l, n, r) of F IM(a) is primitive if and only if n = ±1, that is if and only if α(x) ∈ {a, ā}.

The following settles the commutativity problem in the free inverse monoid with one generator.

Theorem 2 Let x_{1} = (l_{1}, n_{1}, r_{1}) and x_{2} = (l_{2}, n_{2}, r_{2}) be non-idempotents in F IM(a). The following conditions are equivalent

i) x_{1}x_{2} = x_{2}x_{1}

ii)  n_{1}, n_{2} > 0 and l_{1} = l_{2}, r_{1} − n_{1} = r_{2} − n_{2}  (7)

or

n_{1}, n_{2} < 0 and r_{1} = r_{2}, n_{1} − l_{1} = n_{2} − l_{2} (8)

iii) there exists some primitive z such that x_{1}, x_{2} ∈ z^{∗}.

iv) there exist m_{1}, m_{2} > 0 such that x_{1}^{m_{1}} = x_{2}^{m_{2}} Proof. i ⇒ ii. By assumption, we have

min{l_{1}, n_{1} + l_{2}} = min{l_{2}, n_{2} + l_{1}} (9)

and

max{r_{1}, r_{2} + n_{1}} = max{r_{2}, r_{1} + n_{2}} (10)

Assume first that n_{1} > 0. Then by equation (10) we have n_{2} > 0. Thus equation (9) implies l_{1} = l_{2}. But then we obtain r_{2} + n_{1} = r_{1} + n_{2}, i.e., r_{1} − n_{1} = r_{2} − n_{2}.

Let now assume that n_{1} < 0. Equality xy = yx implies x̄ȳ = ȳx̄. By (4), we have x̄ = (−n_{1} + l_{1}, −n_{1}, r_{1} − n_{1}), ȳ = (−n_{2} + l_{2}, −n_{2}, r_{2} − n_{2}) and −n_{1} > 0. Then (8) follows from the previous case. ii ⇒ iii. If (7) holds then let k = r_{1} − n_{1} and let z = (l_{1}, 1, 1 + k). Then by (5), we have x = (l_{1}, n_{1}, n_{1} + k) = z^{n_{1}} and y = (l_{2}, n_{2}, n_{2} + k) = z^{n_{2}}. If (8) holds then via equation (4), for some z we have x̄ = z^{−n_{1}} and ȳ = z^{−n_{2}} and thus x = (l_{1}, n_{1}, n_{1} + k) = t^{n_{1}} and y = (l_{2}, n_{2}, n_{2} + k) = t^{n_{2}} where t = z^{−1}.

iii ⇒ i. Trivial.

iii ⇒ iv. Trivial.

iv ⇒ iii. This is a consequence of equation (3).

Remark 3.1 In free monoids, a stronger property holds, to wit, all solutions of any non trivial equation with two unknowns x and y are cyclic in the sense that there exists z such that x, y ∈ z^{∗}. This is no longer true in the monogenic free inverse monoid. Indeed, consider x = (−1, 1, 2), y = (−1, 1, 1). Then yx = xx holds.

Remark 3.2 The case where one of the elements is idempotent is treated in section 4.2 with the general case since the number of generators does make any difference here.

4 The general case

4.1 A simple necessary condition

The assertion of Theorem 2 does not hold when Σ contains two different letters, i.e., two non idempotent commuting elements in F IM(Σ) are not necessarily powers of a common element. In effect, let us weaken our condition and state the following tentative new one

there exist n, m, p > 0, z ∈ F IM(Σ) and a factorization z_{1}z_{2} = z^{p}
such that x = z_{2}z^{n}z_{1} and y = z_{2}z^{m}z_{1}

Then x and y commute

xy = z_{2}z^{n}z_{1}z_{2}z^{m}z_{1} = z_{2}z^{n+m+p}z_{1} = z_{2}z^{m}z_{1}z_{2}z^{n}z_{1} = yx

The following example however shows that two commuting elements do not necessarily satisfy this simple condition.

Example 4.1 The elements x and y commute, though they do not satisfy the previous condition.

[figure: x; Fig. 4; y]

□

All we can do at this stage, is accomodate the characterization of commuting elements in the free monogenic inverse monoid and state a simple necessary condition for the general case. This requires a definition which can be viewed as an attempt to extend the representation of the monogenic free inverse semigroup to general free inverse semigroups.

Definition 1 Let u ∈ F (Σ) be a primitive element with u = s̄vs where v is cyclically reduced. Consider x ∈ F IM(Σ) − 1 such that α(x) ∈ u^{∗}. Define

i) l_{u}(x) ∈ F (Σ) is the maximal prefix of s̄v̄^{∗} in T (x) ii) r_{u}(x) ∈ F (Σ) is the maximal prefix of s̄v^{∗} in T (x)

Example 4.2 (Example 2.1 continued)

We have u = ba, l_{u}(x) = āb̄ā, r_{u}(x) = baba □

The following can be readily verified where x, y are two elements with α(x) = u^{n} and α(y) = u^{m} for some u ∈ F IM(Σ) and n, m ∈ Z.

l_{u}(xy) is the maximal prefix of s̄v̄^{∗} which is a prefix of l_{u}(x) or α(x)l_{u}(y) (11)

r_{u}(xy) is the maximal prefix of s̄v^{∗} which is a prefix of r_{u}(x) or α(x)r_{u}(y) (12)

The next result uses a natural mapping of F IM(Σ) into the monogenic free inverse monoid.

Proposition 1 Let x, y ∈ F IM(Σ) be two non-idempotent elements that commute. Then there exist u ∈ F (Σ) and n, m > 0 with α(x) = u^{n}, α(y) = u^{m}, l_{u}(x) = l_{u}(y) and u^{−n}r_{u}(x) = u^{−m}r_{u}(y)

Proof. First observe that xy = yx implies that α(x)α(y) = α(y)α(x), so that there exists a (non-empty) primitive element u ∈ F (Σ) satisfying α(x), α(y) ∈ < u >, where < u > denotes the subgroup of F (Σ) generated by u ([12]). Taking, if necessary, the inverse of u, we may assume that α(x) ∈ u^{∗}. Therefore, if x is considered fixed, all elements y that commute with it belong to the inverse subsemigroup S_{u} = α^{−1}(< u >) ⊆ F IM(Σ) of all elements whose image in F (Σ) are powers of u. There exists a natural mapping π_{u} : S_{u} → F IM(a) of the semigroup S_{u} onto F IM(a) defined for every y ∈ S_{u} such that α(y) = u^{n}, n ∈ Z, by π_{u}(y) = (−|l_{u}(y)|, n|u|, |r_{u}(y)|). By equations 11 and 12, π_{u} defines a morphism. We conclude by applying Theorem 2

This leads to the following Definition 2 (with the notations of Definition 1) Given the triple (λ, u, ρ) where u ∈ F (Σ) is a primitive element, λ is a prefix of s̄v̄^{∗} and ρ is a prefix of s̄v^{∗}, the skeleton S(λ, u, ρ) is the subsemigroup of all elements x ∈ F IM(Σ) − 1 with α(x) ∈ u^{∗}, l_{u}(x) = λ and k_{u}(x) = ρ where l_{u}(x) and r_{u}(x) = α(x)k_{u}(x) have the meaning of Definition 1.

Example 4.3 (Example 2.1 continued) The element x belongs to the skeleton S(λ, u, ρ) with u = ab, λ = āb̄ā and ρ = 1. □

4.2 The case where one element is idempotent

It is clear that idempotent and non-idempotent elements have a different status with respect to commutation in free inverse monoids. For instance, any pair of idempotents commute. We first deal with the case where one of the commuting elements, say x, is idempotent and we characterize all the elements y ∈ F IM(Σ) which commute with x.

Theorem 3 Let x be an idempotent and let u ∈ F (Σ) be a fixed element. Let T ⊆ Σ̃^{∗} be the prefix-closure of the set difference between T (x) and uT (x). Then u ∈ T and let y_{u} be the element of F IM(Σ) represented by the pair (T, u) as is Theorem 1. For all y ∈ F IM(Σ), α(y) ∈ u^{∗}, we have

xy = yx if and only if there exists e = e^{2} with y = ey_{u}

Proof. We first remark that y commutes with x if and only if

T (x) ∪ T (y) = T (y) ∪ uT (x) (13)

Consider this condition as a set equation in the (set)-unknown A , where A stands for a prefix-closed subset of F (Σ): T (x) ∪ A = A ∪ uT (x). It is clear that A is a solution if and only if it comprises the closure of the set-difference T (x)ΔuT (x)

A ⊇ Pref(T (x)ΔuT (x)) (14)

Now observe that Pref(T (x)ΔuT (x)) contains u. Indeed, if u^{n} is the maximal power of u contained in T (x), then u^{n+1} ∈ uT (x) − T (x), and thus by prefix-closure, u ∈ Pref(T (x)ΔuT (x)). As a consequence of Theorem 1, there exists y_{u} ∈ F IM(Σ) such that T (y_{u}) = Pref(T (x)ΔuT (x)) and α(y_{u}) = u. Now, if we interpret A as an element y ∈ F IM(Σ), α(y) = u, condition (14) is equivalent to saying that y = ey_{u} for some idempotent e^{2} = e

Example 4.4 With u = a we have the following pair of elements x^{2} = x and y_{u}.

[figure: x; y_{u}]
□

4.3 The case where both elements are non-idempotents

The technique used here is in the vein of that used in [2] and we describe it intuitively now. It has potential applications to other equations though we have not exploited this idea in any other context. Assume xy = yx holds. By taking the image of the equation in the free group, we know that α(x) = u^{n} and α(y) = u^{m} holds for some u ∈ F (Σ) and some integers n, m ∈ Z. To fix idea, assume α(x) = u^{2} and α(y) = u^{3}. Then for some idempotents e_{0}, e_{1}, e_{2} and f_{0}, f_{1}, f_{2}, f_{3} we have x = e_{0}ue_{1}ue_{2} and y = f_{0}uf_{1}uf_{2}uf_{3}. The initial equation reduces to

e_{0}ue_{1}ue_{2}f_{0}uf_{1}uf_{2}uf_{3} = f_{0}uf_{1}uf_{2}uf_{3}e_{0}ue_{1}ue_{2}

If we could define a condition on the idempotents so as to guarantee the uniqueness of their sequence and to prevent any interference between the e_{i}’s and the f_{j}’s, then solving xy = yx would be equivalent to determining under which conditions the two sequences (of length 6) e_{0}, e_{1}, e_{2}f_{0}, f_{1}, f_{2}, f_{3} and f_{0}, f_{1}, f_{2}, f_{3}e_{0}, e_{1}, e_{2} are equal. But this is essentially a problem on words which we can solve. Unfortunately, the two sequences of idempotents do interfere, so we are not left with words. The idea is then to transform x and y into two elements x′ and y′ that commute if and only if x and y commute and that have decompositions e′_{0}, e′_{1}, e′_{2} and f′_{0}, f′_{1}, f′_{2}, f′_{3} where the idempotents do not interfere when concatenating x′ and y′. In other words, we want to achieve two goals: maintain the commutativity of x and y and simplify them. More technically, we require that the following two conditions be satisfied

(x, x′) and (y, y′) are simultaneously conjugate, i.e., for some t ∈ F IM(Σ) (15)
xt = tx′ and yt = ty′ holds
xy = yx if and only if x′y′ = y′x′  (16)

As said in section 2.2 in order to simplify notations and unless otherwise stated, we identify every element u of F (Σ) with the element γ(ι(u)). With this convention, the Munn tree associated with an element of the free group is reduced to a path connecting the first and the last visited vertices without visiting twice the same vertex.

The simplification process of x and y is achieved by Propositions 2, 4, 5. These Propositions define each a transformation rule that is a step in the simplification process.

The first transformation rule yields a simultaneous shift of the first and last visited vertices, leaving the tree globally unchanged (see Example 4.5). The resulting pair (x′, y′) satisfy l_{u}(x′) = l_{u}(y′) = 1.

Proposition 2 Let u = s̄vs where v is cyclically reduced. Assume x, y ∈ F IM(Σ) belong to the skeleton S(λ, u, ρ) with λ = s̄v̄^{l}v̄_{1} where v̄_{1} is a proper prefix of v̄ and l ≥ 0. Set

g = s̄v̄^{l}v̄_{1}. If g ≠ 1, define (x, y) →_{R_{1}}(x′, y′) where x′ = ḡxg and y′ = ḡyg.

Then conditions (15) and (16) hold and x′ and y′ belong to S(1, w, ρ′) where w is a cyclically reduced conjugate of u.

Let us first prove

Lemma 4.1 Let M be an inverse monoid and g ∈ M. The mapping x → τ_{g}(x) = ḡxg defines a one-to-one morphism of the subsemigroup gMḡ onto the subsemigroup ḡMg.

Proof. Indeed, let us first observe that for every x in gMḡ and x′ in ḡMg we have

x = gḡx = xgḡ and x′ = ḡgx′ = x′ḡg′ (17)

Now let x′ = ḡzg. Then x′ = τ_{g}(gx′ḡ) holds hence τ_{g} is surjective. Because of equation (17) we have gτ_{g}(x)ḡ = x and thus τ_{g} is injective. Moreover, we have

τ_{g}(x)τ_{g}(y) = ḡxgḡyg = ḡ(xgḡ)yg = ḡxyg = τ_{g}(xy),

which proves that τ_{g} is a morphism.

Let us return to the proof of Proposition 2. We first check that x ∈ gF IM(Σ)ḡ (the proof carries over to y ∈ gF IM(Σ)ḡ), i.e., by Lemma 2.1 that g, α(x)g ∈ T (x). Since g ∈ T (x) holds by definition of g, we only need verify α(x)g ∈ T (x). However, α(x)g = s̄v^{n−l}v̄_{1} is either a prefix of u^{n} or of ū^{l}. Thus x and y belong to gF IM(Σ)ḡ, in particular x = gḡx and y = gḡy, i.e., condition (15) holds. The fact that condition (16) holds immediately follows from Lemma 4.1.

We are left with computing the skeleton to which x′ belongs. Set w = v_{1}v_{2} where v = v_{2}v_{1} and observe that w is a cyclically reduced conjugate of u. An elementary computation shows that α(x′) = w^{n}. By equality (1) we have

T (x′) = T (ḡ) ∪ ḡT (x) ∪ ḡα(x)T (g)

Let us consider the first and third terms of the union. Since T (ḡ) = Pref(v_{1}v^{l}s) = Pref((v_{1}v_{2})^{l}v_{1}s) and ḡα(x)T (g) = (v_{1}v_{2})^{l+n}v_{1}sPref(s̄v̄_{1}(v̄_{2}v̄_{1})^{l}) ⊆ Pref(v_{1}v_{2})^{l+n}v_{1}s, the maximal prefix of w̄^{∗} in T (ḡ) ∪ ḡα(x)T (g) is 1. Consider now the second term of the union. Let z ∈ T (x) satisfy w^{l}v_{1}sz = w̄^{p}w̄_{1} where w̄_{1} is a prefix of w̄ and p ≥ 0. We have z = s̄v̄^{l+p}v̄_{1}w̄_{1} ∈ T (x). Since either w̄_{1} is a prefix of v̄_{2} or has v̄_{2} as a prefix, by definition of g we have l + p = l, i.e., p = 0 and w̄_{1} = 1 completing the proof.

Example 4.5 (Example 2.1 continued)

Applied to the element of Example 2.1, the previous rule results in the following

[figure: Fig. 5]
□

4.4 The canonical factorization in free inverse monoids

The aim of this section is to introduce the notion of canonical factorization akin to the standard decomposition of [2].

Here we let u be a fixed cyclically reduced element of F (Σ) and we consider the subsemigroup L_{u} of all elements x ∈ F IM(Σ) such that α(x) ∈ u^{∗} and l_{u}(x) = 1. The idea is to write x = x_{0}ux_{1}ux_{2} ⋯ ux_{n+k}ū^{k} where the x_{i}’s are idempotents for i = 0, …, n+k, and to impose some conditions in such a way that two elements in L_{u} are equal if and only if they have the same sequence of idempotents. We write x ≤ y whenever T (y) ⊆ T (x), i.e., whenever x belongs to the right ideal generated by y.

Proposition 3 (Existence and uniqueness of the canonical factorization)

Let x be in F IM(Σ) and u ∈ F (Σ) − 1 such that α(x) = u^{n}, l_{u}(x) = 1, and r_{u}(x) = u^{n+k}u_{1} where u_{1} is a proper prefix of u, n > 0 and k ≥ 0. Then there exists exactly one sequence of idempotents x_{0}, x_{1}, …, x_{n}, …, x_{n+k}, for which the following hold:

i) x = x_{0}ux_{1}ux_{2} … ux_{n+k}ū^{k} ii) for every i = 0, 1, ..., n + k, then x_{i} ≰ u and x_{i} ≰ c̄ where c is the last letter of u.

Proof. For i = 0, …, n + k we denote by T_{i} the set of elements w ∈ F (Σ) in T (x) that have u^{i} but not u^{i+1} as a prefix. We have T (x) = ⋃_{0≤i≤n+k} T_{i}. Clearly, the union is disjoint.

Let x_{i} be the idempotent satisfying T (x_{i}) = u^{−i}T_{i}, i = 0, 1, ..., n + k. By l_{u}(x) = 1 the conditions of ii) hold and

T (x_{0}ux_{1}ux_{2} … ux_{n+k}ū^{k}) = ⋃_{0≤i≤n+k} u^{i}T (x_{i}) = ⋃_{0≤i≤n+k} T_{i}

completing the proof

Example 4.6 (Example 4.5 continued)

We have the canonical factorization x_{0}ux_{1}ux_{2}ux_{3}ū where u = ab, x_{0} = bb̄aā, x_{1} = bb̄a^{2}ā^{2}, x_{2} = aā and x_{3} = bb̄aā

□

In order to simplify the computations, we will consider each element of L_{u} as an infinite sequence of idempotents in the following way. Extend the submonoid E of idempotents of F IM(Σ) by adjoining a new symbol ⊥: E′ = E ∪ {⊥} and set: e⊥ = ⊥e = e for all e ∈ E′. Then with the canonical factorization x_{0}ux_{1}u … ux_{n}u … ux_{n+k}ū^{k} of x we associate the infinite distinguished sequence …, x_{−1}, \underline{x_{0}}, x_{1}, …, \underline{x_{n}}, x_{n+1} … of elements in E′ where x_{i} = ⊥ whenever i < 0 or i > n + k.

Example 4.7 (Example 4.6 continued)

x = …, ⊥, …, ⊥, \underline{bb̄aā}, bb̄a^{2}ā^{2}, \underline{aā}, bb̄aā, ⊥, …, ⊥, …
□

The following is straightforward Property 4.1 Let …, x_{−1}, \underline{x_{0}}, x_{1}, …, \underline{x_{n}}, x_{n+1}, … and …, y_{−1}, \underline{y_{0}}, y_{1}, …, \underline{y_{m}}, y_{m+1}, … be the distinguished sequences associated with x, y ∈ L_{u}. Then

…, x_{−1}y_{−1−n}, \underline{x_{0}y_{−n}}, x_{1}y_{1−n}, …, \underline{x_{n+m}y_{m}}, x_{n+m+1}y_{m+1}, …

is the distinguished sequence associated with the product xy.

The second transformation rule insures that T (x) and T (y) have no unnecessary powers of u.

Proposition 4 Let x, y ∈ F IM(Σ) belong to the skeleton S(1, u, u^{k}u_{1}), where u_{1} is a proper prefix of u and k ≠ 0, and let x_{0}ux_{1}u … ux_{n}u … ux_{n+k}ū^{k} and y_{0}uy_{1}u … uy_{m}u … uy_{m+k}ū^{k} be their canonical factorizations. Assume x_{0} = y_{0} and (xy)_{n+m} = (yx)_{n+m} and set

(x, y) →_{R_{2}}(x′, y′) where

x′ = x_{1}u … ux_{n}x_{0}ux_{n+1}u … ux_{n+k}ū^{k−1}, y′ = y_{1}u … uy_{m}y_{0}uy_{m+1}u … uy_{m+k}ū^{k−1}

Then conditions (15) and (16) hold.

Proof. Indeed, considering the infinite distinguished sequences associated with x, y, x′ and y′ the claim follows from the equalities (xy)_{n+m} = y_{m}, (yx)_{n+m} = x_{n}, and from the computations

(x′y′)_{i} = \{ \begin{matrix}⊥ & if i < 0 or i ≥ n + m + k \\ (xy)_{i+1} & if 0 ≤ i ≤ n + m + k − 1 and i ≠ n + m − 1 \\ (xy)_{n+m}y_{0} & otherwise \end{matrix}

and

(y′x′)_{i} = \{ \begin{matrix}⊥ & if i < 0 or i ≥ m + n + k \\ (yx)_{i+1} & if 0 ≤ i ≤ m + n + k − 1 and i ≠ m + n − 1 \\ (yx)_{m+n}x_{0} & otherwise \end{matrix}

Example 4.8 (Example 4.5 continued)

Applied once to x the transformation yields the following

[figure: Fig. 6]

□

The last transformation rule guarantees that the last idempotent of x and y are the identity, simplifying thus the concatenation of x and y.

Proposition 5 Let x, y ∈ F IM(Σ) belonging to the skeleton S(1, u, u_{1}), where u_{1} is a proper prefix of u. Let x = x_{0}ux_{1}u … ux_{n} and y_{0}uy_{1}u … uy_{m} be their canonical factorizations and assume x_{0} = y_{0} and x_{n} = y_{m} ≠ 1. Set (x, y) →_{R_{3}}(x′, y′) where

x′ = x_{1}u … ux_{n}x_{0}u and y′ = y_{1}u … uy_{m}y_{0}u

Then conditions (15) and (16) hold.

Proof.

Set x′′ = x_{1}u … ux_{n} and y′′ = y_{1}u … uy_{m}. We have x = x_{0}ux′′, y = y_{0}uy′′, x′ = x′′x_{0}u, and y′ = y′′y_{0}u. Since x_{0} = y_{0} condition (15) is satisfied.

That condition (16) holds follows from the computations

(x′y′)_{i} = \{ \begin{matrix}(xy)_{i+1} & if 0 ≤ i < n + m \\ 1 & if i = n + m \end{matrix}

and

(y′x′)_{i} = \{ \begin{matrix}(yx)_{i+1} & if 0 ≤ i < n + m \\ 1 & if i = n + m \end{matrix}

We are now ready to prove our main result, to wit

Theorem 4 Let the relation →_{R} on F IM(Σ) be the reflexive and transitive closure of →_{R_{1}} ∪ →_{R_{2}} ∪ →_{R_{3}}. Let x, y be two non-idempotent elements of F IM(Σ). Then xy = yx holds

if and only if there exist z ∈ F IM(Σ) and n, m > 0 such that (x, y) →_{R}(z^{n}, z^{m})

Proof. The condition is clearly sufficient since by Propositions 2, 4 and 5, for all x, y, x′, y′ and (x, y) →_{R}(x′, y′) we have xy = yx if and only if x′y′ = y′x′.

Conversely, assume that xy = yx holds. Let us apply the reduction rules as much as we can, and observe that they can be applied in the order, first →_{R_{1}} at most once, then →_{R_{2}}

a finite number of times, then →_{R_{3}} at most once. Let (x′, y′) be the result of this process.

We have i) xy = yx if and only if x′y′ = y′x′, ii) there exists t ∈ F IM(Σ) such that xt = tx′ and yt = ty′ , and finally iii) the canonical factorizations of x′ and y′ are of the form x′ = x_{0}ux_{1}ux_{2} … ux_{n−1}u and y′ = y_{0}uy_{1}uy_{2} … uy_{m−1}u. Now, compute

x′y′ = x_{0}ux_{1}ux_{2} … ux_{n−1}uy_{0}uy_{1}uy_{2} … uy_{m−1}u

and

y′x′ = y_{0}uy_{1}uy_{2} … uy_{m−1}ux_{0}ux_{1}ux_{2} … ux_{n−1}u

By the condition ii) of Proposition 3, the previous are canonical factorizations, thus x′y′ = y′x′ reduces to the equality of the two sequences

x_{0}, x_{1}, x_{2} …, x_{n−1}, y_{0}, y_{1}, y_{2}, …, y_{m−1} and y_{0}, y_{1}, y_{2} …, y_{m−1}, x_{0}, x_{1}, x_{2}, …, x_{n−1}

Let p be the the greatest common divisor of n and m. By Fine and Wilf’s theorem there exists a sequence z_{0}, z_{1}, z_{2}, …, z_{p−1} of idempotents such that (considered as elements of the free monoid E^{∗}), x_{0}x_{1}x_{2} … x_{n−1} = (z_{0}z_{1}z_{2} … z_{p−1})^{n/p} and y_{0}y_{1}y_{2} … y_{m−1} = (z_{0}z_{1}z_{2} … z_{p−1})^{m/p}. Setting z = z_{0}uz_{1}uz_{2}u … uz_{p−1}u this means that x′ = z^{n/p} and y′ = z^{m/p} completing thus the proof

Corollary 6 Let x, y be two non-idempotent elements of F IM(Σ). If xy = yx holds, then there exist z, χ ∈ F IM(Σ) and n, m > 0 such that

xχ = χz^{n}, xχ = χz^{m}

5 Centralizers

Given a monoid M two families of subsets of M are of particular interest, [4]. The family RatM of rational subsets is the least family F of subsets that contains the singletons and that is closed under union, product and star, i.e, X, Y ∈ F implies X ∪ Y ∈ F, X, Y ∈ F implies XY = {xy ∈ M | x ∈ X, y ∈ Y } ∈ F and X ∈ F implies ∪_{i≥0}X^{i} ∈ F. A subset is recognizable if the congruence defined by x ∼_{X} y if and only if for all z, t ∈ M zxt ∈ X ⇔ zyt ∈ X has finite index. The family of recognizable subsets is denoted by RecM. It is well known that for all finitely generated monoids, all recognizable subsets are rational.

The purpose of this section is to show that the centralizer of a nonidempotent element x in a free inverse monoid: C(x) = {y ∈ F IM(Σ) | xy = yx} is a rational subset of F IM(Σ) and is never recognizable.

Theorem 5 The centralizer of a non idempotent element of F IM(Σ) is a rational, non recognizable subset of F IM(Σ) .

Proof. Rational and recognizable subsets are closed under one to one morphisms. Via Lemma 4.1, we may thus assume that α(x) = u^{n}, n > 0, where u is cyclically reduced. By Theorem 3, the set of idempotents that commute with x is finite so we may assume that y is non idempotent and that it satisfies l_{u}(x) = l_{u}(y) = 1, i. e., x and y belong to the subsemigroup L_{u} as defined in section 4.4. Consider the canonical factorizations

x = x_{0}ux_{1}u … ux_{n}u … ux_{n+k}ū^{k}, y = y_{0}uy_{1}u … uy_{m}u … uy_{m+k}ū^{k}

Then equality xy = yx can be expressed as a system of n + m + k + 1 equations. The first min{n, m} equations are

x_{i} = y_{i} i = 0, …, min{n, m} − 1

the last min{n, m} are

y_{i−n} = x_{i−m} i = n + m + k + 1 − min{n, m}, …, n + m + k

The remaining ones are of one of the following forms

\begin{aligned}x_{i}y_{i−n} & = & y_{i}x_{i−m} \\ x_{i}y_{i−n} & = & x_{i−m} \\ x_{i}y_{i−n} & = & y_{i} \\ x_{i} & = & y_{i}x_{i−m} \\ y_{i−n} & = & y_{i}x_{i−m} \end{aligned}

Since the first n elements y_{i} are given and all further elements y_{i} depend on y_{i−n}, the set of possible m + k + 1-vectors (y_{i})_{0≤i≤m+k} is finite.

Consider a fixed element x ∈ F IM(Σ) and define α(x) = u^{n} and k_{u}(x) = u^{k}. By the above argument, for each integer m there exist a finite number of elements y that commute with x and for which α(y) = u^{m}. It thus suffices to prove that the subset of y that commute with x and that satisfy m > n+k and m = k +p mod n for some 0 < p ≤ n is rational.

By the hypothesis n < n + k < m we have the following equation (cf. Figure 7)

\begin{aligned}x_{i} & = & y_{i}, & 0 ≤ i < n \\ x_{i}y_{i−n} & = & y_{i}, & n ≤ i ≤ n + k \\ y_{i−n} & = & y_{i}, & n + k < i < m \\ y_{i−n} & = & y_{i}x_{i−m}, & m ≤ i ≤ m + k \\ y_{i−n} & = & x_{i−m}, & m + k < i ≤ n + m + k \end{aligned}

0  n  n + k  m  m + k x yyx  Fig. 7

Using the first three above equations, for 0 ≤ i < m we have

y_{i} = ∏ ; \begin{matrix}0 ≤ j ≤ min\{i, n + k\} \\ j = i mod n \end{matrix} x_{j}  (18)

and using the last three equations for k < i ≤ m + k we have

y_{i} = ∏ ; \begin{matrix}max\{0, i + n − m\} ≤ j ≤ n + k \\ j = i − m mod n \end{matrix} x_{j}  (19)

In particular, equation (18) shows that the sequence (y_{i})_{k<i<m} has period n

y_{i} = ∏ ; \begin{matrix}0 ≤ j ≤ n + k \\ j = i mod n \end{matrix} x_{j}

For 0 ≤ i ≤ n + k set

z_{i} = ∏ ; \begin{matrix}0 ≤ j ≤ min\{i, n + k\} \\ j = i mod n \end{matrix} x_{j}  (20)

Clearly, for some integer r we have y_{0} … y_{m} = z_{0}u … z_{k}(uz_{k+1} … uz_{k+n})^{r}. Further, for 0 ≤ i ≤ k set

t_{i} = ∏ ; \begin{matrix}max\{0, i + n − m\} ≤ j ≤ i − m \\ j = i + k mod n \end{matrix} x_{j}  (21)

The set of elements of the centralizer of x for which m > n + k and m = k + p mod n holds is the rational subset

z_{0}u … uz_{k}(uz_{k+1}u … z_{k+n})^{∗}uz_{k+1}u … z_{k+p−1}ut_{k} … ut_{0}ū^{k} (22)

where, by convention, the factor uz_{k+1}u … z_{k+p−1}u equals u whenever p = 1.

It remains to prove that the centralizer C of x can not be recognizable. Based on the form (22) of the set of elements commuting with x consider a fixed integer r and for all 0 < j ≤ r define the elements

λ_{j} = u^{rn+2k}ū^{jn+k}

and the elements

μ_{j} = ū^{(r−j)n+k}z_{0}u … z_{k}(uz_{k+1}u … z_{n+k})^{r}ut_{k} … ut_{0}ū^{k}

Then for all 1 ≤ j′ ≤ j we have

λ_{j}μ_{j′} ∈ C if and only if j = j′

showing that the r elements λ_{j} are pairwise non ∼_{C} congruent.

We may observe in the previous proof that due to equation (19) the sequence (y_{i})_{k<i<m} can equally be expressed as

y_{i} = ∏ ; \begin{matrix}0 ≤ j ≤ n + k \\ j = i − m mod n \end{matrix} x_{j}

Therefore by considering the k elements, z_{k+1}, … z_{k+n} we see that this sequence is equal to its shift modulo m. Since it depends on x only, it implies a condition on the values m. E. g., if n = 3, k = 4 and x = e_{0}ae_{1} … ae_{7}ā^{4} with e_{0} = e_{6} = bb̄ and e_{i} = 1 otherwise, then the sequence equals z_{5} = 1, z_{6} = bb̄, z_{7} = 1. Such a sequence can only be equal to its shift if the m is a multiple of 3.

References

[1] G. M. Bergman. Centralizers in free associative algebras. Trans. Amer. Math. Soc., 137:327–344, 1969.

[2] C. Choffrut. Conjugacy in free inverse monoids. International Journal of Algebra and Computation, 3(2):169–188, 1993.

[3] P. M. Cohn. Free Rings and Their Relations. Academic Press, 1971.

[4] S. Eilenberg. Automata, Languages and Machines, volume A. Academic Press, 1974.

[5] N. J. Fine and H. S. Wilf. Uniqueness theorems for periodic functions. Proc. Am. Math. Soc., 3(2):109–114, 1965.

[6] F.R. Gantmacher. The theory of Matrices, volume 1. Chelsea Publishing Company, 1959.

[7] V. Guba and M. Sapir. Diagram groups. litp 95–22, Institut Blaise Pascal, 1995.

[8] J. M. Howie. An Introduction to Semigroup Theory. Academic Press, 1976.

[9] G. Lallement. Semigroups and combinatorial applications. Wiley, 1979.

[10] Lothaire. Combinatorics on Words, volume 17 of Encyclopedia of Mathematics and its Applications. Addison-Wesley, 1983.

[11] R.C. Lyndon and P.E. Schupp. Combinatorial Group theory. Springer-Verlag, 1977.

[12] R.C. Lyndon and M.P. Schützenberger. The equation a^{m} = b^{n}c^{p} in a free group. Michigan Math. J., 9:289–298, 1962.

[13] W. D. Munn. Free inverse semigroups. Proc. London Math. Soc., 3:385–404, 1974.

[14] M. Petrich. Inverse Semigroups. Wiley, 1984.

[15] H. E. Scheiblich. Free inverse semigroups. Semigroup Forum, 4:351–359, 1972.

[16] H. E. Scheiblich. Free inverse semigroups. Proc. Amer. Math. Soc., 8:1–7, 1973.

[17] P. V. Silva. On free inverse monoid languages. RAIRO, 30:349–378, 1996.