arXiv:1702.04436v1 [] 15 Feb 2017

THE WORD PROBLEM FOR SOME CLASSES OF ADIAN
INVERSE SEMIGROUPS
MUHAMMAD INAM
Abstract. We show that all of the Schützenberger complexes of an
Adian inverse semigroup are finite if the Schützenberger complex of every positive word is finite. This enables us to solve the word problem
for certain classes of Adian inverse semigroups (and hence for the corresponding Adian semigroups and Adian groups).

1. Introduction
Groups and semigroups are often presented by a pair hX|Ri,where X
denotes the set of set of generators and R denotes the set of defining relations. If R = {(u, v)|u, v ∈ X + }, then the presentation hX|Ri is called
a positive presentation. We consider positive presentations throughout this
paper. We can construct two undirected graph corresponding to a positive
presentation hX|Ri. These graphs are called the left graph and the right
graph of the presentation and are denoted by LGhX|Ri and RGhX|Ri respectively. The vertices of the LGhX|Ri and the RGhX|Ri are labeled by
the elements of the set X. In the LGhX|Ri, we obtain an edge by joining
the vertex labeled by the prefix letter of u with the vertex labeled by the
prefix letter of v for all (u, v) ∈ R. The RGhX|Ri is constructed dually
by joining the vertex labeled by the suffix letter of u with the vertex labeled by suffix letter of v for all (u, v) ∈ R. If there is no cycle in the left
and the right graph of a presentation then the presentation is called a cycle
free presentation or an Adian presentation. These presentation were first
studied by S. I. Adian [1], where is shown that the finitely presented Adian
semigroups SghX|Ri embeds in the corresponding Adian GphX|Ri. Latter
in [6] John H. Remmers generalized this result to any Adian presentation
and proved that an Adian semigroup SghX|Ri embeds in the corresponding
Adian group GphX|Ri. Unless stated otherwise, throughout this paper we
consider our presentations to be Adian presentations.
A semigroup S is called an inverse semigroup if for every element a ∈ S
there exists a unique element b ∈ S such that aba = a and bab = b. This
unique element b is called the inverse of a and denoted by a−1 . The natural
partial order on the elements of an inverse semigroup S is defined as a ≤ b
if and only if a = aa−1 b, for some a, b ∈ S. The congruence relation σ
on S is defined as for a, b ∈ S, aσb if and only if there exists an element
Date: April 11, 2018.
1

2

MUHAMMAD INAM

c ∈ S such that c ≤ ab. It turns out that the σ is the minimal group
congruence on S. So, S/σ is the maximal group homomorphic image of S
and if S is presented by a presentation InvhX|Ri, then S/σ is isomorphic
corresponding group GphX|Ri. Detailed proofs of these facts about inverse
semigroups are provided in the text [3]. In order to be consistent with most
of the literature about inverse semigroups, we abuse the notation of σ and
we also denote the natural homomorphism from invhX|Ri to GphX|Ri by
σ. An inverse semigroup S is called E-unitary if σ −1 (1) = {e|e2 = e}.
S

J. B. Stephen [7] introduced the notion of Schützenberger graphs to solve
the word problem for inverse semigroups. If M = InvhX|Ri is an inverse
semigroup then we may consider the corresponding Cayley graph Γ(M, X).
The vertices of this graph are labeled by the elements of M and there exists
a directed edge labeled by x ∈ X ∪ X −1 from the vertex labeled by m1 to
the vertex labeled by m2 if m2 ≡ m1 x. The Cayley graph Γ(M, X) is not
necessarily strongly connected, unless M happens to be a group, therefore
there may not be an edge labeled by x−1 from m2 to m1 . The strongly
connected components of Γ(M, X) are called the Schützenberger graphs of
M . For any word u ∈ (X ∪ X −1 )∗ the strongly connected component of
Γ(M, X) that contains a vertex labeled by u is the Schützenberger graph of
u and it is denoted by SΓ(M, X, u). The vertices of SΓ(M, X, u) are labeled
by the elements of R-class of u, i.e., Ru = {m ∈ M |mm−1 = uu−1 }, because
M

if x ∈ X ∪ X −1 labels an edge from a vertex labeled m ∈ M to a vertex
labeled by mx, then there exists an edge labeled by x−1 from mx to m in
Γ(M, X) if and only if mR(mx).
There exists a natural graph morphism (not necessarily injective) from a
Schützenberger graph of M to the Cayley graph of M . Meakin showed that
each Schützenberger graph of M embeds in the Cayley graph of M if and
only if M is E-unitary.
It is useful to consider Schützenberger automaton (uu−1 , SΓ(M, X, u), u)
with initial vertex uu−1 ∈ M , terminal vertex u ∈ M and set of states are
the vertices of SΓ(M, X, u). The language accepted by this automaton is
L(u) = {v ∈ M |v labels a path from uu−1 to u in SΓ(M, X, u)}.
Here u and v are regarded as elements of both (X ∪ X −1 )∗ and M . So, L(u)
is a subset of M .
The following result of Stephen [7] plays a key role in solving the word
problem for inverse semigroups.
Theorem 1.1. Let M = InvhX|Ri and let u, v ∈ (X ∪ X −1 )∗ Then
(1) L(u) = {v ∈ M |v ≥ u in the natural partial order on M }.
(2) u = v⇔L(u) = L(v) ⇔ u ∈ L(v) and v ∈ L(u)⇔(uu−1 , SΓ(M, X, u),
M

u) and (vv −1 , SΓ(M, X, v), v) are isomorphic as birooted edge-labeled
graphs.

THE WORD PROBLEM FOR SOME CLASSES OF ADIAN INVERSE SEMIGROUPS 3

We briefly describe the iterative procedure described by Stephen [7] for
building a Schützenberger graph. Let InvhX|Ri be a presentation of an
inverse monoid.
Given a word u = a1 a2 ...an ∈ (X ∪ X −1 )∗ , the linear graph of u is the
birooted inverse word graph (αu , Γu , βu ) consisting of the set of vertices
V ((αu , Γu , βu )) = {αu , βu , γ1 , ..., γn−1 }
and edges
(αu , a1 , γ1 ), (γ1 , a2 , γ2 ), ..., (γn−2 , an−1 , γn−1 ), (γn−1 , an , βu ),
together with the corresponding inverse edges.
Let (α, Γ, β) be a birooted inverse word graph over X ∪ X −1 . The following operations may be used to obtain a new birooted inverse word graph
(α0 , Γ0 , β 0 ):
• Determination or folding: Let (α, Γ, β) be a birooted inverse word
graph with vertices v, v1 , v2 , with v1 6= v2 , and edges (v, x, v1 ) and (v, x, v2 )
for some x ∈ X ∪ X −1 .
Then we obtain a new birooted inverse word graph (α0 , Γ0 , β 0 ) by taking
the quotient of (α, Γ, β) by the equivalence relation which identifies the vertices v1 and v2 and the two edges. In other words, edges with the same label
coming out of a vertex are folded together to become one edge.
• Elementary P-expansion: Let r = s be a relation in R and suppose
that r can be read from v1 to v2 in Γ, but s cannot be read from v1 to v2
in Γ. Then we define (α0 , Γ0 , β 0 ) to be the quotient of Γ ∪ (αs , Γs , βs ) by
the equivalence relation which identifies vertices v1 and αs and vertices v2
and βs . In other words. we “sew” on a linear graph for s from v1 to v2 to
complete the other half of the relation r = s.
An inverse word graph is deterministic if no folding can be performed and
closed if it is deterministic and no elementary expansion can be performed
over a presentation hX|Ri. Note that given a finite inverse word graph it is
always possible to produce a determinized form of the graph, because determination reduces the number of vertices. So, the process of determination
must stop after finitely many steps, We note also that the process of folding
is confluent [7] .
If (α1 , Γ1 , β1 ) is obtained from (α, Γ, β) by an elementary P-expansion,
and (α2 , Γ2 , β2 ) is the determinized form of (α1 , Γ1 , β1 ), then we write (α, Γ, β)
⇒ (α2 , Γ2 , β2 ) and say that (α2 , Γ2 , β2 ) is obtained from (α, Γ, β) by a Pexpansion. The reflexive and transitive closure of ⇒ is denoted by ⇒∗ .
For u ∈ (X ∪ X −1 )∗ , an approximate graph of (uu−1 , SΓ(u), u) is a birooted inverse word graph A = (α, Γ, β) such that u ∈ L[A] and y ≥ u for all
y ∈ L[A]. Stephen showed in [7] that the linear graph of u is an approximate
graph of (uu−1 , SΓ(u), u). He also proved the following:
Theorem 1.2. Let u ∈ (X ∪ X −1 ) and let (α, Γ, β) be an approximate
graph of (uu−1 , SΓ(u), u). If (α, Γ, β) ⇒∗ (α0 , Γ0 , β 0 ) and (α0 , Γ0 , β 0 ) is closed
, then (α0 , Γ0 , β 0 ) is the Schützenberger graph of u, (uu−1 , SΓ(u), u).

4

MUHAMMAD INAM

In [7], Stephen showed that the class of all birooted inverse words graphs
over X ∪ X −1 is a co-complete category and that the directed system of
all finite P-expansions of a linear graph of u has a direct limit. Since
the directed system includes all possible P-expansions, this limit must be
closed. Therefore, by 1.2, the Schützenberger graph is the direct limit.
Full P- expansion (a generalization of the concept of Pexpansion): A full P-expansion of a birooted inverse word graph (α, Γ, β)
is obtained in the following way:
• Form the graph (α0 , Γ0 , β 0 ), which is obtained from (α, Γ, β) by performing all possible elementary P-expansions of (α, Γ, β), relative to (α, Γ, β).
We emphasize that an elementary P-expansion may introduce a path labeled by one side of relation in R, but we do not perform an elementary
P-expansion that could not be done to (α, Γ, β) when we do a full Pexpansion.
• Find the determinized form (α1 , Γ1 , β1 ), of (α0 , Γ0 , β 0 ).
The birooted inverse word graph (α1 , Γ1 , β1 ) is called the full P-expansion
of (α, Γ, β). We denote this relationship by (α, Γ, β) ⇒f (α1 , Γ1 , β1 ). If
(αn , Γn , βn ) is obtained from (α, Γ, β) by a sequence of full P-expansions
then we denote this by (α, Γ, β) ⇒∗f (αn , Γn , βn ).
We now expand the notion of Schützenberger graph to the Schützenberger
complexes. The Schützenberger complexes were first defined by Steinberg
in [8]. Later in [4], Steven Linblad made a small modification in Steinberg’s
definition of Schützenberger complexes. In this paper, we are using Linblad’s
definition of Schützenberger complexes. Let M = hX|Ri be an inverse
monoid and m ∈ M . The Schüutzenberger complex SC(m) for m ∈ M is
defined as follows:
(1) The 1-skeleton of SC(m) is the Schützenberger graph SΓ(m).
(2) For each relation (r, s) ∈ R and vertex v, if r and s can be read at v,
then there is a face with boundary given by the pair of paths labeled by r
and s starting from v.
In similar manner, Stephen’s approximate graphs can be viewed as approximate complexes by sewing on a face each time an elementary expansion
is performed, and identifying faces if a determination results in their entire
boundaries being identified.

2. The word problem for Adian semigroups, Adian inverse
semigroups and Adian groups
The following theorem was first proved by Adian in [1] for finite presentations. Later, it was generalized by Remmers to any Adian presentation,
in [6], by using a geometric approach.
Theorem 2.1. An Adian semigroup SghX|Ri embeds in the corresponding
Adian group GphX|Ri.

THE WORD PROBLEM FOR SOME CLASSES OF ADIAN INVERSE SEMIGROUPS 5

From the embedding in Theorem 2.1, we can derive the fact that every
Adian semigroup embeds in an Adian inverse semigroup, as proved in the
following proposition.
Proposition 1. An Adian semigroup S = SghX|Ri embeds in the Adian
inverse semigroup M = InvhX|Ri.
Proof. Let θ : S → M be the natural homomorphism and φ : S = hX|Ri →
G = GphX|Ri be the natural homomorphism. φ is an injective homomorphism by 2.1. Note that φ = σ ◦ θ. Since φ = σ ◦ θ and φ is injective, then
θ must be injective.

Conjecture 2.2. (Adian, 1976) The word problem for Adian semigroups is
decidable.
Remark 1. The word problem for one relation Adian semigroups is decidable. This is because Magnus [5] proved that the word problem for one
relator groups is decidable and by Theorem 2.1, a one relation Adian semigroup embeds in the corresponding one relator Adian group.
Proposition 2. The word problem for an Adian semigroup S = SghX|Ri
and an Adian group G = GphX|Ri is decidable, if:
1. the Adian inverse semigroup M = InvhX|Ri is E−unitary and
2. the word problem for the Adian inverse semigroup M is decidable.
Proof. It immediately follows from (1) that, for any word u ∈ (X ∪ X −1 )∗ ,
u = 1 if and only if u is an idempotent in M . So, if (2) holds, then we can
G

check whether u is an idempotent or not by checking the equality of words
u = u2 .
M

If (2) holds, then by Proposition 1, S embeds in M and so the word
problem for S is also decidable.

The following theorem proved in [2] establishes the first part of the Proposition 2.
Theorem 2.3. (Muhammad Inam, John Meakin, Robert Ruyle) Adian
inverse semigroups are E−unitary.
In order to solve the word problem for the Adian inverse semigroups we
prove the following theorem which enables us to solve the word problem for
some classes of Adian inverse semigroups.
Theorem 2.4. Let M = InvhX|Ri be a finitely presented Adian inverse
semigroup. Then the Schützenberger complex of w is finite for all words
w ∈ (X ∪ X −1 )∗ if and only if the Schützenberger complex of w0 is finite for
all positive words w0 ∈ X + .

6

MUHAMMAD INAM

Remark 2. We observe that if the word problem for a finitely presented
Adian Inverse semigroup InvhX|Ri is decidable then the word problem for
the corresponding Adian semigroup SghX|Ri and the corresponding Adian
group GphX|Ri is also decidable. Because, if the word problem for an Adian
inverse semigroup InvhX|Ri is decidable, then the corresponding Adian
semigroup embeds into the Adian inverse semigroup by Proposition 1. So
the decidability of the word problem for Adian semigroup follows from the
decidability of the word problem of Adian inverse semigroup. We know by
Theorem 2.3 that Adian inverse semigroups are E-unitary. So, if we want to
check whether an element w ∈ (X ∪ X −1 )∗ is equal to the identity element
of an Adian group G = GphX|Ri in G, then we just need to check that
whether w is an idempotent in the corresponding Adian inverse semigroup
InvhX|Ri. Which can be checked immediately if the word problem for the
Adian inverse semigroup is decidable.
3. Main Theorem
Let InvhX|Ri be an inverse semigroup. Then for any word w ∈ (X ∪
the sequence of approximate graphs {(αn , Γn (w), βn )|n ∈ N} obtained by full P-expansion over the presentation hX|Ri, converges to the
Schützenberger graph of w over the presentation hX|Ri. There exist graph
homomorphisms, ψn : Γn (w) → Γn+1 (w), such that ψn (αn ) = αn+1 and
ψn (βn ) = βn+1 , for all n ∈ N. If we attach to Γn (w) 2-cells corresponding
to the relations in the obvious way, we obtain an approximate complex of
SC(w). We use the same notation, so that {(αn , Γn (w), βn )|n ∈ N} becomes a sequence of approximate complexes that converges to SC(w). We
call a 2-cell to be an n-th generation 2-cell if it occurs in (αn , Γn (w), βn ) \
(ψn−1 (αn−1 ), ψn−1 (Γn−1 (w)), ψn−1 (βn−1 )), for all n ∈ N. The following
lemma is due to Steinberg, who gives two slightly deferent proofs, in [8]
and [9]. The proof we present here is very similar to the proof in [9].
X −1 )∗ ,

Lemma 1. Let M = InvhX|Ri be an inverse semigroup and w ∈ (X ∪
X −1 )∗ . Then the Schützenberger complex of w, SC(w), is simply connected.
Proof. We use induction on the sequence of finite approximate complexes
obtained by full P-expansion of w. Since (α0 , Γ0 (w), β0 ) is just a tree, it is
simply connected.
We assume that the the finite approximate complex (αk−1 , Γk−1 (w), βk−1 )
is simply connected and show that (αk , Γk (w), βk ) is simply connected.
Each time we perform an elementary P-expansion on (αk−1 , Γk−1 (w), βk−1 )
we sew on a relation (u, v) ∈ R along with a 2-cell bounded by the path labeled by uv −1 . We are exactly attaching a simply connected space along
a continuous path, the result of which is again simply connected. Thus by induction, all complexes in the sequence of approximate complexes {(αn , Γn (w),
βn ) : n ∈ N} are simply connected. It follows that the limit of SC(w) of
this sequence is simply connected.


THE WORD PROBLEM FOR SOME CLASSES OF ADIAN INVERSE SEMIGROUPS 7

Lemma 2. Let InvhX|Ri be an Adian inverse semigroup and w ∈ (X ∪
X −1 )∗ . Then the Schützenberger complex of w contains no directed cycles
of 1-cells.
Proof. Meakin showed that, if M = InvhX|Ri, is an E-unitary inverse semigroup, then for all words u ∈ (X ∪ X −1 )∗ , the Schützenberger graph of the
word u embeds into the Cayley graph of the maximal group homomorphic
image of M , GphX|Ri. Likewise, the Schützenberger complex of u embeds
in the Cayley complex of the group GphX|Ri. It has been proved in [2] that
Adian inverse semigroups are E-unitary. So SC(w) embeds into the Cayley
complex of the group GphX|Ri.
If SC(w) contains a directed cycle then the Cayley complex of GphX|Ri
contains a directed cycle as well. We assume that that this directed cycle
is labeled by a word x for some x ∈ X + . Then x = 1 so there exists a
G

Van Kampen diagram with boundary labeled by x. But this contradicts
Lemma 2(ii) of [2] which shows that a Van Kampen diagram over an Adian
presentation contains no directed cycles.

The set of all edges (1-cells) of a graph (complex) whose tail vertex lies
on a vertex labeled by v is denoted Staro (v) and the set of all edges(1-cells)
whose tip lies at a vertex v is denoted by Stari (v).
Lemma 3. Let M = InvhX, Ri be an Adian inverse semigroup, w ∈ X + , v
a vertex (0-cell) of an approximate complex (αn , Γn (w), βn ) and let a, b ∈ X
label two distinct edges of StarΓo n+1 (w) (ψn (v)). Then there exists a path in
LGhX|Ri connecting a and b.
A dual statement to the above Lemma also holds for StarΓi n+1 (w) (ψn (v)).
Proof. We use induction on n to prove the above statement. If n = 0, then
there are the following two cases to consider.
Case 1. Let a ∈ StarΓo 0 (w) (v) and b ∈ StarΓo 1 (w) (ψ0 (v))\Starψo 0 (Γ0 (w)) (ψ0 (v
)). Since w ∈ X + , (α0 , Γ0 (w), β0 ) is just a linear automaton with all of its
edges directed towards the vertex labeled by β0 . If there exists an R-word ar
(where a ∈ X and r ∈ X ∗ ) that labels a path of Γ0 (w) from the vertex v to a
vertex v 0 , we can sew on a new path labeled by the other side of the relation
from the vertex v to the vertex v 0 . Note that this is the only way we can
add new edges in StarΓo 0 (w) (v), because if we attach a new path to the linear
automaton (α0 , Γ0 (w), β0 ) from a vertex u to a vertex u0 and some vertex
of this new path gets identified with the vertex v of the linear automaton,
then there will be a new edge in StarΓo 0 (w) (v). But this is impossible unless
u = v because hX|Ri is an Adian presentation, so the first letters of both
the R-words in a relation are different from each other.
As a consequence of attaching a new path starting from the vertex v ,
StarΓo 1 (w) (v) contains more than one element. So, we sew on a path labeled
by the other side of the relation bs (where b ∈ X and s ∈ X ∗ ) from the

8

MUHAMMAD INAM

vertex v to the vertex v 0 , for some (ar, bs) ∈ R. So, there exists an edge
between a and b in LGhX|Ri.
Case 2. Suppose a, b ∈ StarΓo 1 (w) (ψ0 (v)) \ Starψo 0 (Γ0 (w)) (ψ0 (v)). Then,
since (α0 , Γ0 (w), β0 ) is a linear automaton, there exist R-words cs1 and
cs2 (where c ∈ X and s1 , s2 ∈ X ∗ ) labeling two overlapping segments of
Γ0 (w) starting from the vertex labeled by v. This allows us to sew on new
paths labeled by the other sides of the relations ar1 and br2 (where b ∈ X
and r1 , r2 ∈ X ∗ ), respectively, both starting from the vertex labeled by v.
Since, (ar1 , cs1 ), (br2 , cs2 ) ∈ R, thus there exists a path between a and b in
LGhX|Ri.
Now we assume that the above statement is true for n = k and we prove
the above statement for n = k + 1.
If both the edges labeled by a and b belong to the set StarΓo k (w) (v), then
by the induction hypothesis, there exists a path in LGhX|Ri connecting a
and b. So, there is nothing to prove in this case.
Note that hX|Ri is an Adian presentation and therefore SC(w) contains
no positively or negatively labeled directed cycles by Lemma 2. So, if a ∈
StarΓo k (w) (v) and b ∈ StarΓo k+1 (w) (ψk (v)) \ Starψo k (Γk (w)) (ψk (v)), then either
there exists a relation (br, as) ∈ R (where a, b ∈ X and r, s ∈ X ∗ ), where
as labels a path beginning at vertex v in the birooted inverse word graph
(αk , Γk (w), βk ), or it occurs as consequence of sewing on a path labeled by an
R-word starting from a vertex v 0 (where the vertex labeled by v 0 lies before
the vertex labeled by v on a positively labeled path from αk to βk ), of Γk (w)
and then folding edges with the same label and same initial vertices.
The latter case is impossible, because if we read an R-word ct (where
c ∈ X and t ∈ X ∗ ) starting from the vertex labeled by v 0 in the finite
approximate complex (αk , Γk (w), βk ) and we sew on a path labeled by the
other side of the same relation, du (where d ∈ X and u ∈ X ∗ ) to obtain
(αk0 , Γ0k (w), βk0 ), then all the vertices of LGhX|Ri that are labeled by those
letters which also label the edges of the set StarΓo k (w) (v 0 ), are connected by
a path in LGhX|Ri, by our induction hypothesis. Since the edge labeled
d gets identified with one of the pre-existing edges in the set StarΓo k (w) (v 0 ),
therefore there exists a path between c and d in LGhX|Ri. But, we also
have (ct, du) ∈ R, i.e., there exists an edge between c and d. So, there exists
a closed path in LGhX|Ri. This is a contradiction.
Let StarΓo k (w) (v) = {a1 , a2 , ..., am |ai ∈ X for 1 ≤ i ≤ m}, where each ai
labels an edge. Then there are the following two cases to consider:
Case 1. If a ∈ StarΓo k (w) (v) and b ∈ StarΓo k+1 (w) (ψk (v))\Starψo k (Γk (w)) (ψk (
v)). Then a = ai for some i and there exists an R-word as (where a ∈ X
and s ∈ X ∗ ), that labels a path starting from the vertex labeled by v, which
allowed us to sew on a path labeled by the other side of the same relation,
for some relation of the form (br, as) ∈ R (where b ∈ X and r ∈ X ∗ ). So,
there exists an edge between a and b in LGhX|Ri and a is connected to aj

THE WORD PROBLEM FOR SOME CLASSES OF ADIAN INVERSE SEMIGROUPS 9

for all 1 ≤ i 6= j ≤ m by induction hypothesis. Hence, b is connected with
each aj for 1 ≤ j ≤ m by a path in LGhX|Ri.
Case 2. If a, b ∈ StarΓo k+1 (w) (ψk (v)) \ Starψo k (Γk (w)) (ψk (v)). Then there
exist R-words of the form ai s1 and aj s2 (where ai , aj ∈ X and s1 , s2 ∈ X ∗ )
for some i, j ∈ {1, 2, ..., m}, that can be read in the finite approximate
complex (αk , Γk (w), βk ), starting from the vertex labeled by v, that allowed
us to sew on positively labeled paths labeled by the other sides of relations
of the form (ar1 , ai s1 ), (br2 , aj s2 ) ∈ R (where a, b ∈ X and r1 , r2 ∈ X ∗ ).
Hence there exist an edge between a and ai and an edge between b and aj
in LGhX|Ri. So, if i = j , then there exists a path between a and b in
LGhX|Ri and if i 6= j, then ai and aj are distinct edges and ai is connected
with aj in the LGhX|Ri by the induction hypothesis. Hence, a and b are
connected by a path in LGhX|Ri.

The following Corollary of Lemma 3 is not useful for the proof of the
main theorem of this paper. However, it provides some information about
the structure of Adian semigroups.
Corollary 1. Let S = SghX|Ri be an Adian semigroup. Then S has no
idempotent element.
Proof. We assume that S contains an idempotent element w for some w ∈
X + . It follows from the Proposition 1 that S embeds in the corresponding
inverse semigroup M = InvhX|Ri. So w = w2 . It follows from the Theorem
M

1.1 that w2 ∈ L(w). Then there exists a least positive integer n, such that
w2 labels a path from the initial vertex αn to the terminal vertex βn of the
approximate complex (αn , Γn (w), βn ). We assume that a ∈ X is the prefix
letter of w. Then by Lemma 3 there exists a path from a to a in LGhX|Ri.
So LGhX|Ri contains a closed a path. This is a contradiction.

The following lemma shows that if InvhX|Ri is an Adian inverse semigroup, then the construction of the Schützenberger complex of a positive
word only involves the elementary P-expansion process and no folding at
all.
Lemma 4. Let M = InvhX, Ri be an Adian inverse semigroup and w ∈
X + . Then no two edges fold together in the construction of the Schützenberger
complex of w.
Proof. We use induction on n to show that no two edges fold together
in the construction of each finite approximate complex of the sequence
{(αn , Γn (w), βn )|n ∈ N}.
The above statement is true for n = 0, because w ∈ X + , so (α0 , Γ0 (w), β0 )
is just a linear automaton with no two consecutive edges oppositely oriented.
Hence, no two edges fold together in the construction of (α0 , Γ0 (w), β0 ).

10

MUHAMMAD INAM

We assume that the above statement is true for n = k, i.e., no two edges
fold together in the construction of (αk , Γk (w), βk ). We show that the above
statement is also true for n = k + 1. .
We apply an elementary expansion on (αk , Γk (w), βk ) to obtain (αk0 , Γ0k (w),
0
βk ) and then perform folding in (αk0 , Γ0k (w), βk0 ) to obtain (αk+1 , Γk+1 (w), βk+1
) in the full P-expansion. So, for any vertex v of (αk , Γk (w), βk ), if we read
an R-word labeling a path starting from v to a vertex v 0 , then we sew on
a new path labeled by the other side of the same relation from v to v 0 and
then we perform folding if possible. In order to prove the above statement
we just need to show that no two edges fold together in StarΓo 0 (w) (v). The
k

case that no two edges fold together in StarΓi 0 (w) (v)) is dual to the previous
k
case.
Let {ai ∈ X|0 ≤ i ≤ l} be the set of labels of edges in StarΓo k (w) (v)
and let b0 , b1 , ..., bm be the labels of those edges which are in StarΓo 0 (w) (v) \
k
StarΓo k (w) (v). We claim that
1. ai 6= bj for 0 ≤ i ≤ l and 0 ≤ j ≤ m, and
2. bi 6= bj for 0 ≤ i 6= j ≤ m.
To establish our first claim, we assume that ai = bj for some 0 ≤ i ≤ l
and 0 ≤ j ≤ m. It has already been shown in the proof Lemma 3 that
if bj ∈ StarΓo 0 (w) (v) \ StarΓo k (w) (v) then there exists a relation of the form
k
(bj r, cs) ∈ R (where bj , c ∈ X and r, s ∈ X ∗ ) and cs labels a path from the
vertex v to vertex v 0 . It follows that c ∈ {at ∈ X|0 ≤ t ≤ l}. If c = ai , then
(bj r, cs) = (ai r, ai s) ∈ R. This contradicts the fact that hX|Ri is an Adian
presentation.
If c = ah for some h such that 0 ≤ h 6= i ≤ l, then by Lemma 3, ai and ah
are connected by a path p in LGhX|Ri. We also have (bj r, cs) = (ah r, ai s) ∈
R. So, there exists an edge e between ai and ah in LGhX|Ri. If p and e
represent the same path in LGhX|Ri, then the path labeled by bj r from the
vertex v to the vertex v 0 already exists in (αk , Γk (w), βk ), but this contradicts
our earlier assumption that the path labeled by bj r from v to v 0 did not exist
in (αk , Γk (w), βk ). So, p and e represents two different co-terminal paths.
Hence there exists a cycle in LGhX|Ri. This is a contradiction.
To establish our second claim, we assume that bi = bj for some 0 ≤
i, j ≤ m with i 6= j. Note that the paths starting from the vertex v with
initial edges labeled by bi and bj are consequences of relations of the form
(bi ri , ai si ), (bj rj , aj sj ) ∈ R respectively. If ai = aj , then either both of these
relations are same or they are different relations. If both of these relations
are same then this case reduces to the previous case, which has already been
discussed above in the proof of claim 1. If these relations are different from
each other, then there exists a cycle in LGhX|Ri, which is a contradiction.
So, ai 6= aj . But then by lemma 3, there exists a path connecting ai with aj
in LGhX|Ri. Also, there exist edges from ai to bi and aj to bj in LGhX|Ri,
corresponding to the relators (bi ri , ai si ) and (bj rj , aj sj ). This implies that
there is a cycle in LGhX|Ri, which is a contradiction.

THE WORD PROBLEM FOR SOME CLASSES OF ADIAN INVERSE SEMIGROUPS 11


Proposition 3. Let M = InvhX|Ri be an Adian inverse semigroup and
w1 ∈ X + . Then:
(i) ψn : (αn , Γn (w1 ), βn ) → (αn+1 , Γn+1 (w1 ), βn+1 ) is an embedding for
all n ∈ N.
(ii) SC(w1 ) has exactly one source vertex α and exactly one sink vertex
β, where (α, Γ(w1 ), β) is the underlying birooted graph of SC(w1 ).
(iii) Every directed edge of SC(w1 ) can be extended to a positively labeled directed transversal from α to β.
Proof.

(i). (i) follows immediately from Lemma 4. Since no foldings
occur in the construction of Γn+1 (w) from Γn (w), the images of two
distinct vertices of the approximate complex (αn , Γn (w), βn ) remain
distinct under the map ψn , for all n ∈ N.
(ii). (ii) follows from the fact that ψn (αn ) = αn+1 = α and ψn (βn ) =
βn+1 = β for all n ∈ N. We sew on a new positively labeled
path (labeled by one side of a relation) to an approximate complex (α, Γn (w), β) only when we read a positively labeled segment of
a path from α to β, labeled by the other side of the same relation.
Each 2-cell is two sided and no folding occurs in the construction of
(α, Γn+1 (w), β) from (αn , Γn (w), βn ). So α and β remain the source
and sink vertices of the approximate complex (α, Γn (w), β) for all
n ∈ N. Furthermore, α and β were distinct vertices of (α, Γ0 (w1 ), β)
and no two vertices get identified with each other in the construction
of SC(w1 ), so α and β remain distinct vertices of SC(w1 ).
(iii). Let e0 be a directed edge of SC(w1 ). The complex SC(w1 ) contains
only one source vertex α and one sink vertex β. So, the initial vertex
of e0 is either α or it is a terminal vertex of another edge e−1 . If
the initial vertex of e0 is the terminal vertex of an edge e−1 then
the initial vertex vertex of e−1 is either α or the terminal vertex
of an edge e−2 . Since there are no directed cycles in SC(w1 ) (by
Lemma 2), we can find a sequence of edges e−n , e−(n−1) , ..., e−1 , e0
that constitutes a positively labeled directed path from α to the
terminal vertex of edge e0 .
Similarly, if the terminal vertex of e0 is not β then we can find
an edge e1 whose initial vertex is the terminal vertex of e0 . Continuing in this way, we can find a sequence of edges e0 , e1 , ..., em that
constitutes a positively labeled directed path from the edge e0 to β.
Hence, the sequence of edges e−n , e−(n−1) , ..., e0 , ..., em constitutes a
positively labeled directed transversal from α to β.


The word problem for S = SghX|Ri is the question of whether there is
an algorithm which given any two words u, v ∈ X + , will determine whether
u = v in S.

12

MUHAMMAD INAM

For any two words u, v ∈ X + , u = v if and only if there exists a transition
S

sequence from u to v.
u ≡ w0 → w1 → ... → wn ≡ v; for some n ≥ 0,
where wi−1 → wi represents that wi is obtained from wi−1 by replacing
one side of a relation r (that happens to be a subword of wi−1 ) with the
other side s of the same relation, for some (r, s) ∈ R. The above transition
sequence is called a regular derivation sequence of length n for the pair (u, v)
over the presentation SghX|Ri.
A semigroup diagram or S-diagram over a semigroup presentation SghX|Ri
for a pair of positive words (u, v) is a finite, planar cell complex D ⊆ R2 ,
that satisfies the following properties:
• The complex D is connected and simply connected.
• Each edge (1-cell) is directed and labeled by a letter of the alphabet X.
• Each region (2-cell) of D is labeled by the word rs−1 for some defining
relation (r, s) ∈ R.
• There is a distinguished vertex α on the boundary of D such that the
boundary of D starting at α is labeled by the word uv −1 . α is a source in
D (i.e. there is no edge in D with terminal vertex α).
• There are no interior sources or sinks in D.
In [6], Remmers proved an analogue of Van Kampen’s Lemma for semigroups to address the word problem for semigroups.
Theorem 3.1. Let S = SghX|Ri be a semigroup and u, v ∈ X + . Then
there exists a regular derivation sequence of length n for the pair (u, v)
over the presentation SghX|Ri if and only if there is an S-diagram over the
presentation SghX|Ri for the pair (u, v) having exactly n regions.
Proposition 4. Let M = InvhX|Ri be an Adian inverse semigroup and
w1 , w2 ∈ X + such that w1 ≤ w2 . Then:
M

(i) There exists a (planar) S-diagram corresponding to the pair of words
(w1 , w2 ) that embeds in SC(w1 ).
(ii) w1 = w2 .
M

Proof.

(ii). If w1 ≤ w2 , then w2 ∈ L(α, Γ(w1 ), β) (Stephen, [7]). So, w2
M

labels a directed transversal from the vertex α to the vertex β. Since
the transversals labeled by w1 and w2 are co-terminal and SC(w1 ) is
simply connected by Lemma 1, then the closed path labeled by the
word w1 w2−1 is filled with finitely many 2-cells. Every 2-cell is two
sided because hX|Ri is an Adian presentation. So, we can obtain a
regular derivation sequence from the word w1 to the word w2 from
the complex SC(w1 ), over the presentation hX|Ri in the following
way.

THE WORD PROBLEM FOR SOME CLASSES OF ADIAN INVERSE SEMIGROUPS 13

Geometrically, we push the transversal labeled by w1 across all
first generation 2-cells that were contained in the closed path labeled w1 w2−1 to obtain a new transversal labeled by u1 ∈ X + . Combinatorially, we have replaced some of the non overlapping R-words
that were subwords of the word w1 by the other side of the same
relations. Then we push the transversal labeled by u1 across all
generation 2-cells that were contained in the closed path labeled by
w1 w2−1 to obtain a new transversal labeled by u2 ∈ X + . Again, we
have just replaced some of the non overlapping R-words that were
subwords of the word u1 . This process eventually terminates because the closed path labeled by w1 w2−1 contains only finitely many
2-cells. So, we obtain a regular derivation w1 → u1 → u2 → ... → w2
over the presentation hX|Ri. Hence there exists an S-diagram S
corresponding to this derivation sequence. Since no two edges fold
together in SC(w1 ), therefore S embeds in SC(w1 ).
(ii). This follows immediately form (i) and the Theorem 3.1.

Lemma 5. Let M = InvhX|Ri be an Adian inverse semigroup, let w ∈
(X ∪ X −1 )∗ and let w1 , w2 ∈ X + label two co-terminal paths in SC(w).
Then there exists an S-diagram corresponding to the pair of words (w1 , w2 )
that embeds in SC(w).
Proof. Since M is E-unitary, SC(w) embeds into the Cayley complex of
the group G = GphX|Ri. So, the word w1 w2−1 labels a closed path in the
Cayley complex. Hence w1 w2−1 = 1. So, w1 = w2 . It follows from Theorem
G

G

2.1 that w1 = w2 in SghX|Ri. So, there exists a regular derivation sequence
D from w1 to w2 over the presentation S = SghX|Ri. The semigroup S
embeds into the inverse semigroup M , by Proposition 1. So the regular
derivation sequence sequence D also holds in M . The complex SC(w) is
closed under elementary P-expansion and folding and therefore all the 2cells corresponding to this regular derivation sequence D already exist in
SC(w) between the paths labeled by w1 and w2 . Hence the S-diagram
corresponding to the regular derivation sequence D embeds in SC(w).

In general for any finite inverse semigroup presentation (X, R), and for
any word w ∈ (X ∪ X −1 )∗ , there are natural birooted graph morphisms
for the sequence of approximate graphs given by Stephen’s procedure for
approximating the birooted Schützenberger graph (α, Γ(w), β).
(α1 , Γ1 (w), β1 ) → · · · → (αn , Γn (w), βn ) → (αn+1 , Γn+1 (w), βn+1 ) → · · · →
(α, Γ(w), β)
It was established in Proposition 4 that if M = InvhX|Ri is an Adian
inverse semigroup and w is a positive word, that is w ∈ X + , then all of
the maps in the above sequence are actually embeddings. We may abuse
the notation slightly in this case and for each approximate graph Γn (w) we

14

MUHAMMAD INAM

denote the initial and terminal vertices simply as α and β.
(α, Γ1 (w), β) ,→ · · · ,→ (α, Γn (w), β) ,→ (α, Γn+1 (w), β) ,→ · · · ,→ (α, Γ(w), β)
Recall that for a positive word w ∈ X + , a transversal of an approximate
Schützenberger complex (α, Γk (w), β) is defined to be any positively labeled
path in Γk (w) from α to β. Before proving the main theorem of this section
we introduce the following definition of n-th generation transversal of a
Schützenberger complex.
Definiton 1. An n-th generation transversal of the Schützenberger complex
(α, Γ(w), β) is a positively labeled path from α to β that can be read in the
approximate complex (α, Γn (w), β) but cannot be read in (α, Γn−1 (w), β),
for some n ∈ N.
When studying certain problems involving an inverse monoid given by a
finite presentation (X, R), for example when considering the word problem
for M = InvhX|Ri, it is natural to first ask whether it might happen to be
the case that all of the Schützenberger graphs of M are finite. The following
theorem, our main theorem for this paper, shows that this question can
be reduced to the question of whether or not all Schützenberger graphs of
positive words are finite.
Theorem 3.2. Let M = InvhX|Ri be a finitely presented Adian inverse
semigroup. Then the Schützenberger complex of w is finite for all words
w ∈ (X ∪ X −1 )∗ if and only if the Schützenberger complex of w0 is finite for
all positive words w0 ∈ X + .
Idea of the proof: We assume that the Schützenberger graph of every
positive word is finite and we let w be an arbitrary word, w ∈ (X ∪ X −1 )∗ .
We will use induction on the number of edges in the Munn tree M T (w) to
prove that, the Schützenberger complex of w is finite. The essential part
of the proof involves realizing SC(w) as the limit of a sequence of finite
complexes, via the procedure of Stephen’s P-expansion. We begin with a
finite inverse graph (complex) S that is closed under P-expansions relative
to hX|Ri. To the complex S we attach a single edge e that is labeled by
some letter, say a ∈ X. The resulting complex S1 = S ∨ {e} will in general
not be closed under P-expansions. In a process similar to Stephen’s full Pexpansion construction, we define a sequence of finite complexes S1 , S2 , . . .
that converges in the limit to SC(w). Our theorem will be proved if we can
show that this limit is in fact a finite complex. Equivalently, we must prove
that the sequence S1 , S2 , . . . stabilizes after finitely many steps at some Sk .
Proof. We assume that SC(w0 ) is finite for all positive words w0 ∈ X + ,. Let
w be an arbitrary word, w ∈ (X ∪ X −1 )∗ . We will show that SC(w) is finite,
by applying induction on the number of edges in M T (w).
For the base of our induction, we suppose that M T (w) consists of only
one edge, labeled say by a ∈ X. Then by our assumption about positive
words, SC(w) = SC(a) is finite.

THE WORD PROBLEM FOR SOME CLASSES OF ADIAN INVERSE SEMIGROUPS 15

For our induction hypothesis, we assume that SC(w0 ) is finite for all words
w0 ∈ (X ∪ X −1 )∗ , whose Munn tree consist of k edges. Let w ∈ (X ∪ X −1 )∗
be a word such that M T (w) consists of k + 1 edges. We will show that
SC(w) is finite.
Let α be an extremal vertex of M T (w) (i.e., a leaf of the tree M T (w)),
and let e be the edge of M T (w) that connects α to the remainder of the
M T (w). Assume that e is a positively labeled edge with initial vertex α
and terminal vertex β. The case when e is negatively labeled is dual. The
sub-tree obtained by removing the edge e consists of k edges; we denote this
sub-tree by T for our future reference. Note that the tree T is in fact the
Munn tree of some word z ∈ (X ∪ X −1 )∗ . That is, T = M T (z) and there
are k edges in M T (z). By the induction hypothesis, the Schützenberger
complex S generated by T , i.e., S = SC(z), is a finite complex. There
exists a graph morphism φ : T → S, and so we may regard the vertex β of
T as a vertex in the complex S = SC(z). We reattach the edge e to the
vertex β of S and denote the resulting finite complex by S1 , (see Figure 1.)
The finite complex S = SC(z) was obtained from the subtree T by sewing
on relations from R, and since we reattached the edge e in S1 = S ∨ {e},
then naturally S1 may be regarded as an approximation to SC(w). While
the Schützenberger complex S = SC(z) is closed under P-expansion, the
complex S1 is not necessarily closed under P-expansion. In particular, it is
possible that there may be one or more relations (r, s) ∈ R such that r labels
a path in S1 that begins at vertex α and the other side of the relation, s, is
not read in S1 at α. It is clear that the closure of S1 under P-expansion
over hX|Ri is the Schützenberger complex SC(w).
α
e
β

S

Figure 1. S1 = S ∨ {e}
If the edge e (labeled say, by a) gets immediately identified by folding
to an a-labeled edge of the finite complex S, then we are done, because in
that case we would have SC(w) = S, which was assumed to be a finite
complex. So, we assume that the edge e does not get immediately identified

16

MUHAMMAD INAM

by folding with any of the edges in the finite complex S. We extend the
edge e to all possible maximal positively labeled paths in S1 . There are
only finitely many maximal positively labeled paths in S1 with initial edge
e because S1 is a finite complex that has no positively labeled cycles (by
Lemma 2). We assume that these paths are labeled by w1 , w2 , ..., wn , where
wi ∈ X + for 1 ≤ i ≤ n. Each such wi labels a path from α to some vertex
βi of S. (See Figure 2).
α
e
β

β1

βn
β2

Figure 2. S1 with maximal positively labeled paths from α
to βi .
In order to complete S1 under elementary P-expansion and folding, we
first attach SC(wi ) to the path labeled by wi in S1 , for all i, and denote the
resulting finite complex by S10 . (See Figure 3.) Each complex SC(wi ) for
1 ≤ i ≤ n, is finite since each wi ∈ X + . Thus we obtain S10 by attaching to
S1 finitely many complexes, each of which is finite, and so S10 is finite.
The complex S10 is not necessarily determinized. That is, as a consequence of attaching the complexes SC(wi ), there may now be vertices along
the paths in S10 labeled by wi at which there exist two or more edges labeled
by the same letter and so we must perform foldings to obtain a determinized
graph (complex). We denote the determinized form of S10 by S2 . Since S10
is finite, then so is its determinized quotient S2 . Note however, as consequence of folding S10 to S2 , that the complex S2 may not be closed under
P-expansions.
And so, we iterate the procedure. In general, the complex Sk may not be
closed under P-expansion. That is, there may be a relation (r, s) ∈ R and
a path p labeled by r between some two vertices v and v 0 in Sk such that
the other side of the relation, s, does not label a path in Sk between v and
v 0 . We refer to such a path p in Sk as an unsaturated path.
Note that in Stephen’s procedure we would at this stage simply attach a
path labeled by s between v and v 0 as one step in the P-expansion. In our

THE WORD PROBLEM FOR SOME CLASSES OF ADIAN INVERSE SEMIGROUPS 17

α
e
SC(wn)

SC(w1)
SC(w2)

β1

βn
β2

Figure 3. S10 is obtained from S1 by sewing on SC(wi ) to
each maximal positive path, with label wi , that begins at α
in S1 .

setting it turns out, however, that we can “speed up” Stephen’s procedure.
We will show that every such unsaturated path p can be extended to a
positively labeled path that begins at the vertex α. Such a path can itself
be extended to a maximal positively labeled path that begins at α. So,
instead of merely attaching a single cell along the unsaturated path p that
is labeled by r, we instead read the label, say wj , of the maximal positively
labeled path beginning at α that contains p as a subpath and we attach
the (finite) complex SC(wj ) along this path. Thus in this one step we are
attaching not only the one cell along the unsaturated path p, but also are
attaching all cells that would arise from P-expansions on the maximal path
labeled by wj .
Our iterative procedure for constructing a sequence {Sn } of complexes
can be summarized as follows. Suppose that Sk has been constructed. We
first look for all positive words wi that label a maximal positive path in Sk
that starts at the vertex α and that does not label a path starting at α in
0
Sk−1
. We obtain Sk0 by attaching SC(wi ) to each such maximal positive
path in Sk . Then we obtain Sk+1 by determinizing Sk0 . Thus we obtain a
sequence of finite complexes {Sn } that has SC(w) as its limit.
S1 → · · · → Sk −−−−−−−−−−−−−−−−→ Sk0 −−−−−−−−−−−−−→ Sk+1 → · · ·
For each maximal positive
path with label wi that
starts at α and does not ex0
ist in Sk−1
, attach SC(wi ).

Fold. (Determinize.)

18

MUHAMMAD INAM

A question is whether we ever reach a graph Sk in the procedure such that
all maximal positive paths that can be read at α in Sk can already be read
0
in Sk−1
at α. If this happens, then the sequence of complexes will stabilize
at Sk . Equivalently, we can ask whether we ever reach a complex Sk such
that every maximal positive path in Sk is closed under P-expansion. (We
say that a maximal positive path p is closed under P-expansion if for every
relation (r, s) ∈ R, and for every subpath of p labeled by r between vertices
v and v 0 , then the other side of the relation, s, already labels a path between
v and v 0 in Sk ).
To answer this question, we analyze how the process of folding Sk0 to
Sk+1 affects positively labeled paths that already exist in Sk0 and how new
positively labeled paths may be created in Sk+1 as a consequence of the
folding process. We first note, for example, that when we fold S10 to S2
that each of the attached complexes SC(wi ) that we attached to S1 will
be embedded in S2 after the folding process. This follows from a fact (see
Stephen, [7]) about E-unitary semigroups: If M is E-unitary and w is any
word, and a word wi can be read along some path of the Schützenberger
graph Γ(w), then the entire Schützenberger graph Γ(wi ) will occur as an
embedded subgraph of Γ(w) along that path. Since the theorem we are
proving assumes that the semigroup M has an Adian presentation, we know
from the main theorem of [2] that M is E-unitary. Thus, each SC(wi )
embeds in S2 . Likewise, the original graph S is actually the Schützenberger
graph Γ(z), where the word z labels a path in S1 , and so we know that
the original graph S also remains embedded as a subgraph of S2 . In other
words, no two vertices of any one graph SC(wi ) will become identified with
each other and no two vertices of the original graph S will become identified
with each other in the folding process that takes S10 to S2 . Two vertices of
S10 will become identified in the folding process only if one of the vertices
belongs to the original S and the other vertex belongs to one of the attached
SC(wi ), or if the two vertices belong to SC(wi ) and SC(wj ), with i 6= j.
Everything that we just said about the process of folding S10 to S2 holds as
well for the process of folding Sk0 to Sk+1 . The original complex S and each
complex SC(wi ), attached at any step of the iteration, will be embedded as
subcomplexes of Sk+1 . The interest is in what new paths may be formed as
a result of folding Sk0 to Sk+1 .
Claim: Suppose that SC(wi ) is one of the complexes that was attached
to Sk to form Sk0 . Suppose, in the process of folding Sk0 → Sk+1 , that a vertex
γ of SC(wi ) gets identified, as a consequence of folding, with a vertex γ 0 of
the original complex S. Then we claim that every positively labeled path in
SC(wi ) from γ to βi will get identified by the folding process with a path in
S from the vertex γ 0 to βi . Thus, every maximal positive path p that begins
at the vertex α in Sk+1 and cannot be read beginning at the vertex α in Sk0
will factor uniquely as p = p1 p2 , where p1 is a path in some SC(wi )s and p2
is a path in the original complex S.

THE WORD PROBLEM FOR SOME CLASSES OF ADIAN INVERSE SEMIGROUPS 19

Proof of Claim: Since γ gets identified with γ 0 through folding, we know
(Stephen, [7]) that in Sk0 there is a path from γ to γ 0 labeled by a Dyck
word d that we may assume is of the form d = ss−1 , where s ∈ (X ∪ X −1 )∗ .
Further, we may assume that s is a reduced word. There must be a vertex
δ that lies on the path labeled by wi (the intersection of SC(wi ) and S in
Sk0 ) so that s labels a path in SC(wi ) from γ to δ and s also labels a path
in S from γ 0 to δ. (See Figures 5 & 6.) To prove the above claim we assume
that r2 labels an arbitrary positive path in SC(wi ) from γ to βi . We need
to prove that this path gets identified by folding with a path in S that is
labeled by r2 from γ 0 to βi . The path in SC(wi ) that is labeled by r2 can
be extended to an nth generation transversal t of SC(wi ), for some n. To
complete our proof, we apply induction on the generation number, n, of the
transversal of t of SC(wi ).
Suppose that the path labeled by r2 lies on a 1st generation transversal t
of SC(wi ). We assume that t ≡ r1 r2 where r1 labels the sub-path of t from
α to γ and r2 labels the sub-path of t from γ to βi . Since γ lies on a 1st
generation transversal of SC(wi ), we conclude that in the Dyck word path
ss−1 that goes from γ to δ to γ 0 , it must be that either s is a positive word
or s−1 is a positive word. We examine the following three cases.
Case 1. (See Figure 4.) Suppose that the vertex δ is actually βi , the terminal vertex of the path labeled by wi , and suppose the Dyck word labeling
the path from γ to γ 0 is the word r2 r2−1 . In this case, the word r2 labels
the subpath of the transversal t of SC(wi ) from γ to βi and the word r2
also labels a path from γ 0 to βi . These two paths, both labeled by r2 , which
meet at the vertex βi , will fold together so that the path labeled by r2 in
SC(wi ) from γ to βi gets identified with the path in S from γ 0 to βi . So in
this case the statement of the claim obviously holds.
Case 2. (See Figure 5.) We assume that the Dyck word path from γ to
δ to γ 0 is labeled by r3 r3−1 , where r3 is a positive word, r3 ∈ X + . So, the
path in SC(wi ) from γ to δ is labeled by r3 and the path in S from γ 0 to
δ is labeled by r3 . The oppositely oriented paths labeled by r3 , which meet
at δ, become identified with each other through folding. We assume that
the sub-path from δ to βi , of the maximal path labeled by wi , is labeled by
r4 ∈ X + . Obviously, the path labeled by r4 from δ to βi is in SC(wi ) and the
path labeled by r3 from γ to δ is also in SC(wi ). Hence the path labeled by
r3 r4 from γ to βi is in SC(wi ). The positive words r2 and r3 r4 label two coterminal paths in SC(wi ). So, by Lemma 5 an S-diagram corresponding to
the pair of words (r2 , r3 r4 ) embeds in SC(wi ). This S-diagram also embeds
in S, because S contains a path labeled by one side of this S-diagram,
(namely, the path from γ 0 to βi in S that is labeled by r3 r4 ), and S is closed
under elementary P-expansion. So, the two S-diagrams corresponding to
the pair of words (r2 , r3 r4 ) get identified with each other and our claim holds
in this case. That is, the path in SC(wi ) labeled by r2 from γ to βi gets
identified with a path in S from γ 0 to βi .

20

MUHAMMAD INAM

α
e

SC(wi)

r1

β

γ'

γ
r2

r2

βi

Figure 4. Case 1 for the first generation transversals of the
proof of the Claim
α
e

SC(wi)

r1

r3

β
δ
r3
γ'

γ
r4
r2

βi

Figure 5. Case 2 for the first generation transversals of
the proof of the Claim
Case 3. (See Figure 6.) We assume that the Dyck word path from γ to δ
to γ 0 is labeled by r3−1 r3 , where r3 is a positive word. So, the path in SC(wi )
from δ to γ is labeled by r3 and the path in S from δ to γ 0 is labeled by
r3 . The oppositely oriented paths labeled by r3 , which meet at δ, become
identified with each other through folding. Now we have the path in SC(wi )
labeled by r3 r2 from δ to βi in SC(wi ). Again, we let the positive word r4
be the label of the sub-path of the maximal path labeled by wi from δ to

THE WORD PROBLEM FOR SOME CLASSES OF ADIAN INVERSE SEMIGROUPS 21

βi . The words r3 r2 and r4 label two co-terminal paths in SC(wi ). So, by
Lemma 5 an S-diagram corresponding to the pair of words (r3 r2 , r4 ) embeds
in SC(wi ). This S-diagram also embeds in S, because S contains a path
labeled by one side of this S-diagram (namely, the path labeled by r4 ) and
S is closed under elementary P-expansion. Hence these two S-diagrams
get identified with each other through folding. In particular, the path in
SC(wi ) labeled by r2 from γ to βi gets identified with a path in S from γ 0
to βi , and so our claim follows in this case as well. This concludes the base
case of the inductive proof of the claim.
α
e

SC(wi)

r1

r3

β
δ
r3
γ'

γ

r4
r2

βi

Figure 6. Case 3 for the first generation transversals of
the proof of the Claim
We assume that our claim is true for all paths from γ to βi that lie along
a (n − 1)-st generation transversal of SC(wi ). We prove that our claim is
true for all n-th generation transversals of SC(wi ) as well.
Suppose that an arbitrary path from γ to βi is labeled by the positive word
s2 and suppose that this path extends to an n-th generation transversal t of
SC(wi ) . Let t ≡ s1 s2 where s1 labels the sub-path of t from α to γ and s2
labels the sub-path of t from γ to βi . Again, since the vertex γ in SC(wi )
gets identified with with the vertex γ 0 in S through folding, we know that
there is a Dyck word ss−1 that labels a path from γ to γ 0 . Since γ lies on
an n-th generation transversal of SC(wi ), the Dyck word path ss−1 must
pass through some vertex δ of SC(wi ) that lies on an (n − 1)-st generation
transversal of SC(wi ). We examine the following three cases.
Case 1. Suppose the vertex δ is the vertex βi and we read the Dyck word
0
0
s2 s−1
2 in Sk from γ to γ . Then we fold the oppositely oriented paths labeled
by s2 . So in this case it is obvious that that path in SC(wi ) labeled by s2
gets identified with the path in S from γ 0 to βi .

22

MUHAMMAD INAM

Case 2. (See Figure 7.) Suppose q denotes an (n − 1)-st generation
transversal of SC(wi ) and the vertex δ lies on the transversal q. Assume
also that δ has already been identified with a vertex of S as a consequence
of folding along the Dyck word ss−1 . In this case (Case 2), we assume that
the portion of the Dyck word path from γ to δ is labeled by a positive word
s3 ∈ X + . Since δ has already been folded and identified with a vertex of
0
S, we have the Dyck word s3 s−1
3 labeling a path from γ to δ to γ in the
partially folded Sk0 . The path in SC(wi ) labeled by s3 from γ to δ can be
extended along the (n − 1)-st generation transversal q to the vertex βi . We
assume that this path is labeled by s3 s4 ∈ X + , where s4 ∈ X + labels the
sub-path of q from δ to βi . By the induction hypothesis the sub-path of
q from δ to βi gets identified with a path in S. Thus we have a path in
SC(wi ) labeled by s3 s4 from γ to βi and we also have a path in S labeled
by s3 s4 from γ 0 to βi . The positive words s2 and s3 s4 label two co-terminal
paths in SC(wi ). So by Lemma 5 an S-diagram corresponding to the pair
of words (s2 , s3 s4 ) embeds in SC(wi ). This S-diagram also embeds in S,
because S contains the path labeled by one side of the S-diagram (namely,
s3 s4 ) and S is closed under elementary P-expansion. So the two S-diagrams
corresponding to the pair of words (s2 , s3 s4 ) get identified with each other.
Hence, the path in SC(wi ) labeled by s2 gets identified with a path in S,
and the claim holds in this case.
α
e
β

s1

SC(wi)
γ

s3

s3

γ'
δ

s2

s4

βi

Figure 7. Case 2 for the n-th generation transversal of the
proof of the claim
Case 3. (See Figure 8.) Suppose q denotes an (n − 1)-st generation
transversal of SC(wi ) and δ is a vertex on the transversal q that has already
been identified with a vertex of S. We also assume that there exists a path,
labeled by s3 ∈ X + , from δ to γ such that we can read the Dyck word s−1
3 s3

THE WORD PROBLEM FOR SOME CLASSES OF ADIAN INVERSE SEMIGROUPS 23

from γ to δ to γ 0 in Sk0 . We extend the path labeled by s3 from δ to γ
along the n-th generation transversal t to a positively labeled path (labeled
by s3 s2 ∈ X + ) from δ to βi . By the induction hypothesis the sub-path of q
from the vertex δ to the vertex βi (say, labeled by s4 ∈ X + ) is in S. Hence
s3 s2 and s4 label two co-terminal paths in SC(wi ) and the path labeled by s4
is also in S. By Lemma 5 an S-diagram corresponding to the pair of words
(s3 s2 , s4 ) embeds in SC(wi ). This S-diagram also embeds in S, because S
contains one side of this S-diagram and S is closed under elementary Pexpansion. Thus the two S-diagrams corresponding to the pair of words
(s3 s2 , s4 ) get identified with each other and the claim holds in this case as
well. This completes the inductive step in the proof of the claim.
α
e
β

s1
s3

SC(wi)

s3
δ

γ'

γ

s2

s4

βi

Figure 8. Case 3 for the n-th generation transversal of the
proof of the claim

We perform all possible foldings mentioned in the proof of above claim in
S10 and denote the resulting complex by S2 . In this folding process edges of
the complex S are folded with the edges of SC(wi ) for some i. This folding
process may create new maximal positively labeled paths starting from α
that did not exist in S10 .
For example, S10 may contain a path labeled by r3−1 r5 for some r5 ∈ X +
starting from the vertex βi as shown in the Figure 9. After folding the path
labeled by r3 r3−1 , we can read a new positively labeled path starting from α
and labeled by r1 r5 which could not be read in S10 .
It is also possible that S10 may contain a path labeled by r4 r5 for some
r5 ∈ X + starting from the vertex δ as shown in the following diagram. After
folding the path labeled by r4−1 r4 , we can read a new positively labeled path
starting from α and labeled by r1 r5 which could not be read in S10 .

24

MUHAMMAD INAM
α
e
SC(wi)

r1

α
e

β

SC(wi)

r1

fold

γ'

γ

γ

r5

r3
r2

β

r3

r3

r2
r5

βi

βi

Figure 9. An example showing the construction of new
maximal positively labeled paths starting from α as a consequence of folding of edges in S10
α
e
SC(wi)

r1

r4

α
e

β

SC(wi)

r1
δ

r4

r4
γ'

γ
w i'
r2

fold

β
δ

γ
w i'

r5
r2
r5

βi

βi

Figure 10. An example showing the construction of new
maximal positively labeled paths starting from α as a consequence of folding of edges in S10

Now we consider all those maximal positively labeled paths in S2 that
start from α and did not exist in S10 . Since there are only finitely many such
paths, we assume that these paths are labeled by u1 , u2 , ..., um and for each
i ∈ {1, 2, ..., m} the path labeled by ui terminates at the vertex γi . Note
that each maximal path labeled by ui must terminate at a vertex γi that is
in the original complex S. Then SC(ui ) for each i is finite by hypothesis.
So, we attach SC(ui ) at the path labeled by ui for all i and denote the
resulting complex by S20 .

THE WORD PROBLEM FOR SOME CLASSES OF ADIAN INVERSE SEMIGROUPS 25

If the paths labeled by ui and uj for some i 6= j are co-terminal, then
by the same argument as above SC(ui ) and SC(uj ) are isomorphic to each
other as edge labeled graphs. So, they get identified with each other.
If for some i, SC(ui ) contains a transversal labeled by t ∈ X + such that
θ(6= γi ) is the first vertex of u that gets identified with a vertex in S2 , then
the entire positively labeled sub-path of t from θ to γi gets identified with
a positively labeled path in S2 . This can be verified by using the same
argument as above.
We perform all possible foldings in S20 and denote the resulting complex
by S3 . In this folding process edges of the complex S are folded with the
edges of SC(ui ) for some i.This folding process may create new maximal
positively labeled paths starting from α that did not exist in S20 . So, we
repeat this entire process again.
We keep repeating this process of sewing finite Schützenberger complexes
of positive words and folding unless we reach to the point where we can not
create new maximal positively labeled paths starting from α and terminating at a vertex in the complex S. This process of expansion and folding
eventually terminates, because hX|Ri is a finite presentation, therefore an
edge labeled by a letter can only be incident with finitely many 2-cells and
there are only finitely many edges in S as S is a finite complex. By construction, the resulting complex is deterministic and closed with respect to
elementary P-expansions, so it is the Schützenberger complex of w. So, the
Schützenberger complex of w is finite.

The following Corollary follows immediately from the Theorem 3.2, because the Schützenberger complex, SC(w), for any ∈ (X ∪ X −1 )∗ , is finite
over a presentation (X, R) if and only if the underlying graph (1-skeleton)
of SC(w) is finite over the same presentation.
Corollary 2. Let M = InvhX|Ri be a finitely presented Adian inverse
semigroup. Then the Schützenberger graph of w is finite for all words w ∈
(X ∪ X −1 )∗ if and only if the Schützenberger graph of w0 is finite for all
positive words w0 ∈ X + .
4. Some applications of Theorem 3.2
4.1. The word problem for a sub-family of Adian inverse semigroups that satisfy condition (?).
Definiton 2. We say that a positive presentation hX|Ri satisfies condition
(?), if it satisfies the following two conditions:
(1) No proper prefix of an R-word is a suffix of itself or any other Rword.
(2) No proper suffix of an R-word is a prefix of itself or any other Rword.

26

MUHAMMAD INAM

If hX|Ri is a finite Adian presentation that satisfies condition (?), then
the set of relations R consists of two types of relations. First, those relations
which are of the form (u, xvy), where u and v are R-words and x, y ∈ X + .
Second, those relations (u, v) ∈ R where neither u nor v contains an Rword as a proper sub-word. We construct a directed graph corresponding
to an Adian presentation that satisfies condition (?) as follows. We call this
graph the bi-sided graph of the presentation hX|Ri. The bi-sided graph of a
positive presentation is defined as follows.
Definiton 3. The bi-sided graph of the presentation hX|Ri is a finite, directed, edge-labeled graph, denoted by BS(X, R) satisfying
• The vertex set of BS(X, R) is the set of all R-words.
• To define the edge set of BS(X, R), let u, v be two R-words (where it
may happen that u and v are the same R-word). There is a directed
edge from the vertex u to the vertex v if any of the following three
conditions holds:
(1) (u, xvy) ∈ R, for some x, y ∈ X + . In this case, the directed
edge from u to v is labeled by the ordered pair (x, y).
(2) u ≡ xvy, for some x, y ∈ X + and u and v are distinct R-words.
In this case, the edge from u to v is labeled by the ordered pair
(x, y).
(3) If (u, v) ∈ R is such that neither u nor v contains any R-word
as a proper sub-word, then there is an edge in the bi-sided
graph between u and v, pointing in both directions. This edge
is labeled by (ε, ε), where ε denotes the empty word.
In general, the bi-sided graph BS(X, R) of an Adian presentation may
contain closed paths.
Example 1. The bi-sided graph of the Adian presentation ha, b|aba = bi
contains a directed closed path (cycle), namely the loop consisting of the
single edge labeled by (a, a) from the vertex b to itself. (See Figure 11.) The
presentation ha, b|aba = bi does not satisfy condition (?) either, because the
R-word aba has the letter a as a prefix and as a suffix.

Ed g e o f t y p e 1
Ed g e o f t y p e 2
(a,a)
(a ,a )
b

aba

Figure 11. The bi-sided graph of ha, b|aba = bi contains a
cycle, (the loop at vertex b).

THE WORD PROBLEM FOR SOME CLASSES OF ADIAN INVERSE SEMIGROUPS 27

Example 2. The bi-sided graph of the Adian presentation ha, b, c, d, e, f, g, h, i, j, k|a =
f bg, a = jck, b = hci, c = dei contains an undirected closed path. (See figure
12.) The presentation ha, b, c, d, e, f, g, h, i, j, k|a = f bg, a = jck, b = hci, c =
dei satisfies condition (?).

Edge of type 2

Edges of type 1
(f, g)

b
(f, g)

fbg

(h, i)

(j, k)

c

(ε, ε)

a

de
(h, i)

(j, k)

hci

jck

Edge of type 3

Edges of type 2
Figure
12. The
bi-sided
graph
of
ha, b, c, d, e, f, g, h, i, j, k|a = f bg, a = jck, b = hci, c = dei
Example 3. The bi-sided graph of the Adian presentation ha, b, c, d, e, f, g, h,
i, j, k, l, m|a = f cg, b = hci, c = de, l = jm2 ki is a forest. (See figure 13).
The presentation ha, b, c, d, e, f, g, h, i, j, k, l, m|a = f cg, b = hci, c = de, l =
jm2 ki satisfies condition (?).
Remark 3. For the remainder of this subsection we consider presentations
hX|Ri such that
(1) hX|Ri is an Adian presentation.
(2) hX|Ri satisfies condition (?).
(3) The bi-sided graph BS(X, R) is cycle-free. That is, there are no
closed paths, directed or un-directed, in BS(X, R). In other words,
BS(X, R) is a forest.
Note that if the bi-sided graph of a presentation hX|Ri is a forest, then
every R-word labels a vertex of a connected component in BS(X, R) that is
a tree. For an R-word u, we let Tu denote the unrooted tree that contains
the vertex u and we refer to Tu as the bi-sided tree of u. If u and v label
two different vertices of the same bi-sided tree, then Tu and Tv denote the
same unrooted, bi-sided tree.
Definiton 4. Let u be an R-word. We say that a vertex labeled by v of Tu
is accessible from u if there exists a path labeled by v in SC(u).

28

MUHAMMAD INAM

Edges of type 2

Edges of type 3

fcg

hci
(h, i)

(f, g)

c

(ε, ε)

(ε, ε)

de
(f, g)
a

l

jm 2k

(h, i)

b

Edges of type 1
Figure
13. The
bi-sided
graph
of
ha, b, c, d, e, f, g, h, i, j, k, l, m|a = f cg, b = hci, c = de, l =
jm2 ki
Note that if there exists a directed edge from v1 to v2 in the bi-sided tree
of u and v1 is accessible from u then v2 is also accessible from u. Because
if v1 is accessible from u, then there exists a path labeled by v1 in SC(u).
Since there exists a directed edge from v1 to v2 in the bi-sided tree of u
therefore either (v1 , xv2 y) ∈ R or v1 ≡ xv2 y for some x, y ∈ X + . In either
case there exists a path labeled by v2 in SC(u).
However, if v2 is accessible from u, and there is an edge in BS(X, R) from
v1 to v2 , then v1 is not necessarily accessible from u. Also, if a vertex v of
Tu is not accessible from u then all of the vertices of Tu that lie after the
vertex v going along any geodesic path from u to an extremal vertex of Tu
are also not accessible.
Lemma 6. Let M = InvhX|Ri be a finitely presented Adian inverse semigroup that satisfies condition (?) and (such that) BS(X, R) contains no
closed paths. Then SC(u) is finite, for every R-word u.
Proof. We start from the linear automaton (α, Γ0 (u), β) and obtain the approximate complex (α, Γ1 (u), β) by applying full P-expansion on (α, Γ0 (u), β).
In the construction of (α, Γ1 (u), β), we attach a path labeled by one side
of a relation whose other side can be read in (α, Γ0 (u), β). In the linear
automaton (α, Γ0 (u), β) we can precisely read u and all those R-words that
are proper subwords of u. Each relation of R with one side u is either of the
form (u, xvy) for some x, y ∈ X + and an R-word v or of the form (u, v) where
v contains no R-word as its proper subword. The first case corresponds to
an edge of “type 1” in Tu and the second case corresponds to an edge of
“type 3” in Tu . Any R-word u1 that is a proper subword of u corresponds
to an edge of ”type 2” in Tu , where u ≡ xu1 y for some x, y ∈ X + . Thus, in

THE WORD PROBLEM FOR SOME CLASSES OF ADIAN INVERSE SEMIGROUPS 29

performing Stephen’s P-expansion to obtain Γ1 (u) from Γ0 (u), there is a
precise correspondence between first generation transversals of SC(u) and
the edges of Tu whose initial vertex is either labeled by u or labeled by an
R-word that is a proper subword of u.
If there exists an edge of type 1 or type 2 labeled by (x, y) for some x, y ∈
X + from a vertex labeled by an R-word v to the vertex u in Tu , then either
(v, xuy) ∈ R or v ≡ xuy. We show that no generation 1 transversal contains
a subpath labeled by v. In other words, we show that v is inaccessible from
u.
Note that we cannot read the word xuy in the linear automaton (α, Γ0 (u), β)
because (α, Γ0 (u), β) contains only one path from α to β that is labeled by
the word u. So, if (v, xuy) ∈ R then we cannot attach a path labeled by v
to the linear automaton (α, Γ0 (u), β) and if v ≡ xuy then we cannot read a
path labeled by v in (α, Γ0 (u), β) because it is longer than the path labeled
by u.
We obtain the approximate graphs (α, Γ2 (u), β) by applying the full Pexpansion on (α, Γ1 (u), β). We observe that the second generation transversals of SC(u) are obtained as a consequence of attaching paths labeled by
those R-words which label the terminal vertices of those edges of Tu whose
initial vertex is either a first generation transversal or a proper subword of
an R-word that labels a first generation transversal of SC(u). If there exists
an edge in BS(X, R) labeled by (x1 , y1 ) for some x1 , y1 ∈ X ∗ with initial
vertex labeled by v1 and terminal vertex labeled by v2 such that x1 v2 y1 is
a subword of an R-word that labels a first generation transversal, then we
obtain a second generation transversal by sewing on a path labeled by v1
from the initial vertex to the terminal vertex of the of the path x1 v2 y1 .
If there exists an edge of type 1 or type 2 labeled by (x1 , y1 ) with initial
vertex v1 and terminal vertex v2 (i.e. either (v1 , x1 v2 y1 ) ∈ R or v1 ≡ x1 v2 y1
) such that v2 is a subword of an R-word that labels a first generation
transversal but x1 v2 y1 is not a subword of that transversal, then we cannot
attach a path labeled by v1 to (α, Γ1 (u), β). So, none of the vertices of Tu
that occur after the vertex v1 going along a path from the vertex u to an
extremal vertex of Tu will be accessible from u in SC(u).
We observe that when we apply full P-expansion on (α, Γn (u), β) for
some n ∈ N, we cover some more vertices of Tu that were not covered before
in the sense that we add some new transversals that contains an R-word that
labels a vertex of Tu and that R-word does not label a path in (α, Γn (u), β).
Since Tu is a finite tree and none of the R-word label two distinct vertices of
Tu therefore the process of applying full P-expansion must terminate after
a finite number of steps. Hence SC(u) is finite.

Lemma 7. Let M = InvhX|Ri be an Adian inverse semigroup. Let u be
an R-word and z labels a proper suffix of a transversal p of SC(u). Then
either
(i) z contains an R word that also labels a subpath of p, or

30

MUHAMMAD INAM

(ii) A prefix of z is a suffix of some R-word that also labels a subpath
of p.
Proof. If z does not contain an R-word that also labels a subpath of the
transversal p then the initial vertex of the path labeled by z is not the
initial vertex of any R-word that labels a subpath of p. Hence the initial
vertex of z lies between a pair of vertices of p that are the initial and the
terminal vertex of a subpath of p that is labeled by an R-word. Hence a
prefix of z is a suffix of an R-word.

We also remark that a dual statement also holds for a prefix of a transversal of the Schützenberger complex of an R-word over an Adian presentation.
Remark 4. In Lemma 7, if the presentation hX|Ri satisfies condition (?)
and z happens to be a prefix of an R-word, then only (i) holds, because (ii)
violates the condition (?).
Similarly, in the dual statement to Lemma 7, if the presentation hX|Ri
satisfies condition (?) and z happens to be a suffix of an R-word, then only
(i) holds, because (ii) violates the condition (?).
Theorem 4.1. Let M = InvhX|Ri be a finitely presented Adian inverse
semigroup that satisfies condition (?) and BS(X, R) contains no closed path.
Then SC(w) is finite, for all w ∈ (X ∪ X −1 )∗ .
Proof. We just need to show that SC(w) is finite for all w ∈ X + and then
the above theorem follows from Theorem 3.2. So, we assume that w ∈ X +
and we construct the linear automaton of w, (α, Γ0 (w), β).
It follows from condition (?), that no two distinct R-words will overlap
with each other. However, an R-word can be a proper subword of another
R-word. So, we can uniquely factorize w as x0 u1 x2 u2 ...un xn , where xi ∈ X ∗
and ui ’s are maximal R-words in the sense that none of the ui ’s are properly
contained in another R-word that is also a subword of w.
It follows from Lemma 6, that SC(ui ) is finite for all 1 ≤ i ≤ n. So, we
attach SC(ui ) for all 1 ≤ i ≤ n to the corresponding paths labeled by ui ’s in
(α, Γ0 (w), β) to construct SC(w) and denote the resulting complex by S1 .
It follows from Lemma 4, that no two edges get identified with each other as
a consequence of attaching SC(ui ) for all 1 ≤ i ≤ n to the linear automaton
(α, Γ0 (w), β). If S1 is closed under elementary P-expansion, then we are
done. Otherwise, we will be able to read a finite number of R-words labeling
the paths of S1 where we can attach new 2-cells by sewing on paths labeled
by the other sides of the corresponding relations.
We assume that v1 , v2 , ..., vm are the R-words that label the paths of S1
where we can attach new 2-cells. Note that each of vi labels a vertex of Tuj
for some i and j, that was inaccessible from uj earlier. Because if vi labels a
path in S1 then by Lemma 7 and Remark 4 the path labeled by vi contains
an R-word rj as a proper subword such that the R-word rj labels a path in
SC(uj ). In other words, rj labels an accessible vertex of Tuj from the vertex

THE WORD PROBLEM FOR SOME CLASSES OF ADIAN INVERSE SEMIGROUPS 31

uj . Since rj is a proper subword of vi , therefore there exists an edge of type
2 in Tuj with initial vertex labeled by vi and the terminal vertex labeled by
rj . So, Tvi and Tuj represent the same tree for some i and j. By Lemma 6,
SC(vi ) is finite for all 1 ≤ i ≤ m and cover some more vertices of Tuj in the
sense that SC(vi ) contain paths labeled by those R-word which also label
some of the vertices of Tuj , for some 1 ≤ j ≤ n, that were not covered by
SC(uj ).
We attach SC(vi ) to the paths labeled by vi for all 1 ≤ i ≤ m in S1 and
denote the resulting complex by S2 . No two edges get identified with each
other in S2 as a consequence of attaching SC(vi )’s to S1 by Lemma 4. If S2
is closed under elementary P-expansion then we are done. Otherwise we
repeat this process of attaching Schützenberger complexes of R-words and
capturing more vertices of the trees Tui for some 1 ≤ i ≤ n. This process
eventually terminates, because, each Tui is a finite tree with all the vertices
labeled by distinct R-words and every R-word labels a vertex of exactly one
tree. Hence, SC(w) is a finite complex.

Remark 5. Let M = InvhX|Ri be an Adian inverse semigroup that satisfies
condition (?) and BS(X, R) contains no closed path then the word problem
for M is decidable. It follows from the Theorem ?? that the Schützenberger
complex of every word w ∈ (X ∪X −1 )∗ is finite over the presentation hX|Ri.
So, for any two given words w1 , w2 ∈ (X∪X −1 )∗ , we can easily check whether
w1 ∈ L(w2 ) and w2 ∈ L(w1 ) or not.
4.2. The word problem for Inverse semigroups given by the presentation ha, b|abm = bn ai. In this section we show that the word problem is decidable for the inverse semigroup given by the presentation M =
Invha, b|abm = bn ai, where m, n ∈ N. The word problem for the case case
m = n follows from Corollary 6.6 of [7]. So, throughout this section we
assume that m > n. The case m < n follows from a dual argument. We can
get an alternate proof for the case n = m by following along same lines as
in the case of m < n.
Lemma 8. The Schützenberger complex of a word ak bt for k, t ∈ N, over
the presentation ha, b|abm = bn ai, is finite.
Proof. We adopt a slightly different approach to construct SC(ak bt ). We
draw edges labeled by a horizontally and edges labeled by b vertically. Then
the linear automaton of ak bt , (α0 , Γ0 (ak bt ), β0 ), is shown in Figure 14. If
t < m, then we cannot attach any 2-cell to (α0 , Γ0 (ak bt ), β0 ). So, the above
lemma is true for this case.
If t ≥ m, then t = q1 m+r1 , where q1 is the quotient and r1 is a remainder
and 0 ≤ r1 < m. We can attach q1 2-cells in the first column along the
vertical segment labeled by bt of (α0 , Γ0 (ak bt ), β0 ). After attaching all the
2-cells in the first column along the vertical segment labeled by bt we have
created a new vertical segment labeled by bnq1 , because there are total q1

32

MUHAMMAD INAM

2-cells and each 2-cells contains exactly n edges on the newly attached side
of the 2-cell.
β0
br1

a
bn

bm
a
bt

bn
α0 a

a

bm

a

Figure 14. Construction of SC(ak bt ).
If nq1 < m or k = 1 then the process of attaching new 2-cells terminates
at this stage. If neither nq1 < m nor k = 1, then nq1 = q2 m + r2 , where
q2 is a quotient, r2 is a remainder and 0 ≤ r2 < m. So, We can attach a
column of q2 2-cells along the vertical segment labeled by bnq1 . This process
of attaching columns of new 2-cells terminates after at most k steps. So,
SC(ak bt ) is a finite complex.

Remark 6. In the above construction of SC(ak bt ) in Lemma 8, every new
maximal vertical segment contains fewer edges than the other vertical side
of the same column of 2-cells.
Lemma 9. The Schützenberger complex of a word bt ak for k, t ∈ N, over
the presentation ha, b|abm = bn ai, is finite.
Proof. We draw edges labeled by a horizontally and edges labeled by b vertically. Then the linear automaton of bt ak , (α0 , Γ0 (bt ak ), β0 ), is shown in
Figure 15. If t < n, then we cannot attach any 2-cell to (α0 , Γ0 (bt ak ), β0 ).
So, the above lemma is true for this case.
If t ≥ n, then t = q1 n + r1 , where q1 is the quotient and r1 is a remainder
and 0 ≤ r1 < n. We can attach q1 2-cells in the first column along the
vertical segment labeled by bt of (α0 , Γ0 (ak bt ), β0 ). After attaching all the
2-cells in the first column along the vertical segment labeled by bt we have
created a new vertical segment labeled by bmq1 , because there are total q1
2-cells and each 2-cells contains exactly m edges on the newly attached side
of the 2-cell.
If k = 1 then the process of attaching new 2-cells terminates at this stage.
Otherwise mq1 = q2 n + r2 , where q2 is a quotient, r2 is a remainder and

THE WORD PROBLEM FOR SOME CLASSES OF ADIAN INVERSE SEMIGROUPS 33

a
bn

a

β0

bm
a

bt
a
bn

bm
a

br1

α0

Figure 15. Construction of SC(bt ak ).
0 ≤ r2 < n. So, We can attach a column of q2 2-cells along the vertical
segment labeled by bmq1 . Clearly, this process of attaching columns of new
2-cells terminates after k steps. So, SC(bt ak ) is a finite complex.

Remark 7. In the above construction of SC(bt ak ) in Lemma 9 every new
maximal vertical segment contains more edges than the other vertical side
of the same column of 2-cells.
Theorem 4.2. For all w ∈ {a, b, a−1 , b−1 }∗ the Schützenberger complex of
a word w, SC(w), over the presentation Invha, b|abm = bn ai is finite. Hence
the word problem is decidable for M .
Proof. Since hX|Ri is an Adian presentation, we just need to show that
SC(w) for all w ∈ {a, b}+ is finite, then Theorem 4.2 follows from Theorem
3.2.
If w is of the form ak or bk for some k ∈ N, then SC(w) is finite.
We assume that w ≡ ak0 bt0 ak1 bt1 ...akl btl , where k0 , tl ∈ N ∪ {0} and
ki , tj ∈ N for 1 ≤ i ≤ l and 0 ≤ j ≤ l − 1.
We construct SC(w) by drawing the edges labeled by a horizontally and
the edges labeled by b vertically. So, (α0 , Γ0 (w), β0 ) looks like the diagram
shown in Figure 16. We attach SC(aki bti ) on the path labeled by aki bti of
(α0 , Γ0 (w), β0 ) wherever it is possible to attach and we denote the resulting
complex by S1 . No two edges get identified with each other as a consequence
of attaching these finite complexes to (α0 , Γ0 (w), β0 ) by Lemma 4. As a
consequence of attaching these finite complexes to the (α0 , Γ0 (w), β0 ), we
have created at most l − 1 new maximal directed paths labeled by ak bt for
some k, t ∈ N.

34

MUHAMMAD INAM

β0
bt2
ak2
bt1
ak1
bt0

α0

ak0
Figure 16. (α0 , Γ0 (w), β0 )

We attach finite complexes of the form SC(ak bt ) to every new maximal
path labeled by a word of the form ak bt for some k, t ∈ N in S1 . We denote
the resulting complex by S2 . Again by Lemma 4, no two edges get identified
with each other in S2 . We can read at most l−2 new maximal directed paths
in S2 which are labeled by the words of the form ak bt for some k, t ∈ N. So,
we repeat the process attaching finite Schützenberger complexes of the words
of the form ak bt where ever it is possible to attach and denote the resulting
complex by S3 . Note that this process of attaching finite Schützenberger
complexes of the words of the form ak bt eventually terminates after at most
l steps. We denote the resulting complex by S 0 .
Now in S 0 , on the other side of the path labeled by w, we attach finite Schützenberger complexes of the words bti aki+1 at the paths labeled by
bti aki+1 for 0 ≤ i ≤ l − 1, where ever it is possible to attach and denote
the resulting complex by S10 . By Lemma 4 no two edges in S10 get identified
with each other as a consequence of attaching these finite complexes. As
a consequence of attaching these finite complexes we have created at most
l − 1 new maximal paths which are labeled by the words of the form bt ak for
some k, t ∈ N. So, we repeat the process of attaching finite Schützenberger
complexes of the words of the form bt ak at the corresponding new paths in
S10 . We denote the resulting complex by S20 . This process of attaching finite
complexes of the words of the form bt ak terminates after at most l steps and
we obtain a finite complex which is closed under elementary P-expansion
and folding. Hence, SC(w) is a finite complex.


THE WORD PROBLEM FOR SOME CLASSES OF ADIAN INVERSE SEMIGROUPS 35

Acknowledgement
The author of this paper is thankful to John Meakin and Robert Ruyle
for their several useful suggestions.
References
[1] Adian, S. I., Defining relations and algorithmic problems for groups and semigroups,
Proc. Steklov Inst. Math., No 85 (1966).
[2] Inam, M., Meakin, J., Ruyle, R., A structural property of Adian inverse semigroups,
Semigroup Forum, Nov. 2015.
[3] Lawson, M. V., Inverse semigroups, World Scientific Co. Pte. Ltd., 1998.
[4] Linblad, S. P.,Inverse monoids presented by a single relator, PhD thesis, Dept. of
Math., University of Nebraska-Lincoln, Dec. 2003.
[5] Magnus, W., Das Identitätsproblem für Gruppen mit einer definierenden Relation,
Math Ann. 106 (1932), 295-307.
[6] Remmers, J. H., On the Geometry of Semigroup Presentations, Advances in Mathematics, 36 (1980), 283-296.
[7] Stephen, J. B., Presentations of inverse monoids, Journal of Pure and Applied Algebra (1990), 81-112.
[8] Steinberg, B., A topological approach to inverse and regular semigroups, Pacific J.
Math. 208 (2003), no. 2, 367-396.
[9] Steinberg, B., A sampler of a topological approach to inverse semigroups, Semigroups,
Algorithms, Automata and Languages, Word Scientific, (2002), 437 - 461.
E-mail address: s-minam1@math.unl.edu
Department of Mathematics, University of West Georgia, Carrollton, Georgia 30118 USA

