Network semigroups
We introduce the class of network semigroups. These are based on networks that extend the notion of a directed graph. This class properly contains the class of graph inverse semigroups. We investigate the structure of network semigroups. We show that two network semigroups are isomorphic if and only...
Gespeichert in:
| Datum: | 2026 |
|---|---|
| Hauptverfasser: | , , |
| Format: | Artikel |
| Sprache: | Englisch |
| Veröffentlicht: |
Lugansk National Taras Shevchenko University
2026
|
| Schlagworte: | |
| Online Zugang: | https://admjournal.luguniv.edu.ua/index.php/adm/article/view/2486 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Algebra and Discrete Mathematics |
| Завантажити файл: |  |
Institution
Algebra and Discrete Mathematics| _version_ | 1870196963473883136 |
|---|---|
| author | Wang, Yanhui H. Gao, Pei Ren, Xueming M. |
| author_facet | Wang, Yanhui H. Gao, Pei Ren, Xueming M. |
| author_institution_txt_mv | [
{
"author": "Yanhui H. Wang",
"institution": "Shandong University of Science and Technology"
},
{
"author": "Pei Gao",
"institution": "Shandong University of Science and Technology"
},
{
"author": "Xueming M. Ren",
"institution": "Xi'an University of Architecture and Technology"
}
] |
| author_sort | Wang, Yanhui H. |
| baseUrl_str | https://admjournal.luguniv.edu.ua/index.php/adm/oai |
| collection | OJS |
| datestamp_date | 2026-07-08T07:55:33Z |
| description | We introduce the class of network semigroups. These are based on networks that extend the notion of a directed graph. This class properly contains the class of graph inverse semigroups. We investigate the structure of network semigroups. We show that two network semigroups are isomorphic if and only if the underlying networks are isomorphic. |
| doi_str_mv | 10.12958/adm2486 |
| first_indexed | 2026-07-09T01:00:10Z |
| format | Article |
| fulltext |
© Algebra and Discrete Mathematics RESEARCH ARTICLE
Volume 41 (2026). Number 2, pp. 305–338
DOI:10.12958/adm2486
Network semigroups
Yanhui H. Wang, Pei Gao, and Xueming M. Ren
Communicated by G. Kudryavtseva
Abstract. We introduce the class of network semigroups.
These are based on networks that extend the notion of a directed
graph. This class properly contains the class of graph inverse semi-
groups. We investigate the structure of network semigroups. We
show that two network semigroups are isomorphic if and only if the
underlying networks are isomorphic.
Introduction
The concept of a network provides a fundamental framework for model-
ling complex systems in which entities and their interactions are repre-
sented abstractly. Traditionally, such systems are described by graphs,
where vertices represent entities and edges encode pairwise (dyadic) in-
teractions between them. This classical framework has proved highly
successful in a wide range of areas, including algebraic structures associ-
ated with graphs [5, 21]. However, it has become increasingly clear that
many real-world systems cannot be adequately captured by pairwise in-
teractions alone. In particular, complex systems arising in biology, social
The authors would like to thank the Editor and the anonymous referees for their
careful reading of the manuscript and for their valuable comments and suggestions,
which have led to a significant improvement of the paper. The authors are also very
grateful to Professor Victoria Gould for her careful reading of the manuscript and for
many helpful suggestions, particularly concerning rewriting systems. This research was
supported by the National Natural Science Foundation of China (Grant No. 11501331).
2020 Mathematics Subject Classification: 20M10.
Key words and phrases: network right ∗-abundant semigroups, networks, graph
inverse semigroups.
https://doi.org/10.12958/adm2486
306 Network semigroups
sciences and data science often exhibit higher-order interactions, invol-
ving simultaneous relationships among more than two entities [7–9,16].
Motivated by these developments, the theory of higher-order net-
works has emerged as a natural generalisation of classical graph theory.
One prominent approach models higher-order interactions via simplicial
complexes, where interactions are encoded by simplices of arbitrary di-
mension [6]. Another direction, which is particularly relevant in appli-
cations involving flows or transformations, considers networks in which
both the source and the range of an interaction are subsets of vertices,
not necessarily singletons [9]. Such structures extend directed graphs
by allowing multi-source and multi-target relations, thereby providing a
flexible framework for describing non-dyadic and nonlinear interactions.
In this paper we focus on a class of higher-order networks in which
relations connect subsets of vertices to subsets of vertices. Our aim
is to investigate the algebraic structures naturally associated with such
networks, and in particular to study the semigroups arising from them
and their structural properties.
Throughout, a network Γ = (V, T, s, r) consists of a set of vertices V ,
a set of relations T , together with mappings s, r : T → P(V ), where P(V )
is the power set of V and any relation t ∈ T is composed of an ordered
pair (s(t), r(t)), where s(t) and r(t) are disjoint non-empty subsets of V ,
called the source and the range of t, respectively. If, in addition, each
t ∈ T satisfies the condition that s(t) and r(t) are singleton subsets of
V , then Γ reduces to a (simple directed) graph, and we identify it with
its underlying graph structure and refer to it simply as a graph. In this
paper we restrict attention to networks with finitely many or countably
infinitely many vertices and relations.
Let Γ = (V, T, s, r) be a graph. A path in Γ is a finite sequence
p = t1t2 · · · tn of relations such that r(ti) = s(ti+1) for all i = 1, . . . , n−1.
Ash and Hall [5] introduced the class of graph inverse semigroups as-
sociated with such paths. These semigroups generalize the polycyclic
monoids [20] and play an important role in the theory of graph algeb-
ras [21]. The algebraic investigation of structures generated by paths
in graphs has developed into an active area of research, revealing deep
connections with semigroup theory, ring theory, and operator algebras
(see, for example, [1–5,14,17] ).
For general networks, there is a natural extension of the notion of a
path. Namely, a sequence p = t1t2 · · · tn of relations is admissible whene-
ver r(ti)∩s(ti+1) ̸= ∅ for each i = 1, . . . , n−1. This broader notion reflects
Y. H. Wang, P. Gao, X. M. Ren 307
the higher-order interactions inherent in networks. It is therefore natural
to ask what algebraic structures arise from such generalized paths.
Motivated by the construction of graph inverse semigroups, we asso-
ciate to each network a semigroup generated by paths and their formal in-
verses, subject to suitable relations. The resulting semigroup is obtained
as a quotient of a path-generated semigroup and is shown to be a right
∗-abundant semigroup. In the sense of Fountain, this places it within
the framework of unary (or ∗-) semigroups [13]. Such structures form a
rich class encompassing, for example, right adequate, right h-adequate
and right ample semigroups [11, 13]. Furthermore, in the special case
where the network is a graph, the constructed semigroup coincides with
the corresponding graph inverse semigroup (see Proposition 2), showing
that our construction properly extends the classical theory.
The paper is organized as follows. In Section 1 we recall the neces-
sary preliminaries on semigroup theory, with particular emphasis on right
abundant semigroups. We also introduce paths in a network and discuss
basic properties, together with the notion of network homomorphisms.
In Section 2 we define, for a given network Γ, the semigroup QΓ generated
by paths in Γ, and prove that QΓ is a right ∗-abundant semigroup (see
Theorem 2). Furthermore, we construct two subsemigroups SΓ and RΓ
of QΓ determined by paths satisfying additional conditions, and establish
that SΓ is right ample (see Proposition 4) and that RΓ is a fundamental
inverse semigroup (see Corollary 2), with RΓ ⊆ SΓ ⊆ QΓ. Section 3 is
devoted to congruence-theoretic aspects. We define a proper ideal I of
QΓ (and similarly for SΓ), and show that the relation ρI = (I × I)∪ 1QΓ
is an idempotent-separating congruence on QΓ. We also provide suffi-
cient conditions under which QΓ fails to be ∗-congruence-free as a unary
semigroup (see Theorem 4). In addition, we obtain analogous sufficient
conditions ensuring that SΓ is not ∗-congruence-free and that RΓ is not
congruence-free (see Theorem 5). Finally, in Section 4 we investigate the
structure of idempotents in QΓ via the natural partial order. As an ap-
plication, we prove that two networks are isomorphic if and only if their
associated network semigroups are isomorphic (see Theorem 6).
1. Preliminaries
For the convenience of the reader, we recall some basic definitions and
results concerning (right) abundant semigroups and networks. Further
details may be found in [9, 11,12,15].
308 Network semigroups
1.1. (Right) abundant semigroups
We recall the definitions of the relations L∗ and R∗. Let S be a semi-
group. We denote the set of idempotents of S by E(S). For a, b ∈ S,
define
aL∗ b ⇐⇒ ∀x, y ∈ S1(ax = ay ⇐⇒ bx = by),
and
aR∗ b ⇐⇒ ∀x, y ∈ S1(xa = ya ⇐⇒ xb = yb).
Then L∗ is a right congruence and R∗ is a left congruence.
Lemma 1. Let e ∈ E(S) and a ∈ S. The following are equivalent:
(i) eL∗ a;
(ii) ae = a and ax = ay implies ex = ey for all x, y ∈ S1.
The dual statement holds for R∗.
Recall that L and R denote Green’s relations on S. Then L ⊆ L∗
and R ⊆ R∗. Moreover, for regular elements a, b ∈ S,
aL∗ b ⇐⇒ aL b, aR∗ b ⇐⇒ aR b.
In particular, if S is regular, then L∗ = L and R∗ = R.
A semigroup S is called right abundant if every L∗-class contains an
idempotent.
Definition 1. A right abundant semigroup S is called right ∗-abundant
if each L∗-class of S contains a unique idempotent.
Let S be a right ∗-abundant semigroup. For each a ∈ S, denote by a∗
the unique idempotent in the L∗-class of a. Then ∗ defines a unary opera-
tion on S, and hence S may be regarded as an algebra of type (2, 1). In
this setting, a homomorphism between right ∗-abundant semigroups is
understood to be a mapping that preserves both the multiplication and
the unary operation ∗ (equivalently, the relation L∗). When necessary,
such homomorphisms will be referred to as (2, 1)-morphisms. In particu-
lar, every semigroup isomorphism between right ∗-abundant semigroups
preserves the unary operation ∗.
Definition 2. A semigroup S is right ample (formerly right type A) if
it is right abundant, its idempotents commute, and ea = a(ea)∗ for all
a ∈ S and e ∈ E(S).
Y. H. Wang, P. Gao, X. M. Ren 309
Since the idempotents of a right ample semigroup commute, they
are closed under multiplication and hence form a semilattice. Further-
more, each L∗-class contains at most one idempotent, and thus every
right ample semigroup is right ∗-abundant. Moreover, when regarded
as unary semigroups, the class of right ample semigroups constitutes a
quasi-variety of right ∗-abundant semigroups [13].
Dually, one defines left ample semigroups. A semigroup is ample
(formerly type A) if it is both left and right ample. In particular, every
inverse semigroup is ample, where for a ∈ S, a† = aa−1 and a∗ = a−1a,
with a† the unique idempotent in the R∗-class of a and a−1 the inverse
of a. Thus ample semigroups may be viewed as the abundant analogue
of inverse semigroups.
Lemma 2. Let S be a right ample semigroup with semilattice of idem-
potents E(S), and let Reg(S) denote the set of regular elements of S.
Then Reg(S) is an inverse semigroup and a subsemigroup of S.
Proof. Since every idempotent is regular, E(S) ⊆ Reg(S). To show that
Reg(S) is a subsemigroup, it suffices to prove closure under multiplica-
tion.
Let a, b ∈ Reg(S). We have aL∗ a∗ and bL∗ b∗. Since a, b, a∗, b∗ are
regular, it follows that aL a∗ and bL b∗. As L is a right congruence, we
obtain abL a∗b, and hence (ab)∗ = (a∗b)∗. Since S is right ample, we
have a∗b = b(a∗b)∗. Applying the unary operation ∗ to both sides yields
(a∗b)∗ = (b(a∗b)∗)∗. Using bL b∗, it follows that (b(a∗b)∗)∗ = b∗(a∗b)∗,
and therefore (ab)∗ = (a∗b)∗ = (b(a∗b)∗)∗ = b∗(a∗b)∗. Consequently,
abL a∗b = b(a∗b)∗ L b∗(a∗b)∗ = (ab)∗, so ab is L-related to an idempotent.
Hence ab ∈ Reg(S). Therefore Reg(S) is a subsemigroup of S. Since
its idempotents form a semilattice, it follows that Reg(S) is an inverse
semigroup.
Lemma 3 ([15]). Let S be a semigroup with set of idempotents E(S),
and let a be a regular element in S, where b is an inverse of a. Then
ab, ba ∈ E(S) and abR aL ba. Moveover, if E(S) is a semilattice and a
is a regular element in S then the inverse of a is unique.
1.2. Generation and presentation
We now recall the notion of a semigroup generated by a non-empty setX.
The free monoid X∗ on X consists of all words over X with operation of
juxtaposition. We use ε to denote the empty word. The free semigroup
310 Network semigroups
X+ on X is X∗\{ε}. A non-empty word is denoted by x1x2 · · ·xn, where
xi ∈ X for 1 ≤ i ≤ n. For any two words α = x1x2 · · ·xn, β = y1y2 · · · ym
of X+, we use αβ to denote the juxtaposition of α and β, that is αβ =
x1x2 · · ·xny1y2 · · · ym. If α = βµ, where α, β, µ ∈ X∗, β is called a prefix
of α, and a proper prefix if µ is not the empty word ε. For any two
non-empty words α, β in X+, we say that α, β are prefix comparable if
one of α, β is a prefix of the other.
Let R be a binary relation on X+. The quotient semigroup X+/R♯,
where R♯ is the smallest congruence on X+ containing R, is said to be
the semigroup generated by X subject to relations R. We use the formal
equality u = v to mean that (u, v) ∈ R. We denote the R♯-class of
x ∈ X+ by [x].
We conclude this subsection with basic notions on rewriting systems;
see [10,23] for details.
Let A be a non-empty set and → a binary relation on A. The pair
(A,→) is called a rewriting system. Denote by
∗→ the reflexive and tran-
sitive closure of →, and by
∗↔ the equivalence relation generated by →.
For x ∈ A, write [x] for its
∗↔ -class. An element x ∈ A is irreducible
or reduced if there is no y ∈ A with x → y. If x
∗→ y and y is irre-
ducible, then y is called a normal form of x. A rewriting system (A,→)
is noetherian if there is no infinite sequence x0 → x1 → x2 → · · · in A.
A rewriting system (A,→) is confluent if for all w, x, y ∈ A,
w
∗→ x, w
∗→ y ⇒ ∃z ∈ A such that x
∗→ z, y
∗→ z,
and locally confluent if for all w, x, y ∈ A,
w → x, w → y ⇒ ∃z ∈ A such that x
∗→ z, y
∗→ z.
Lemma 4 ([10]). Let (A,→) be a rewriting system.
(i) If (A,→) is noetherian and confluent, then every
∗↔-class contains
a unique normal form.
(ii) If (A,→) is noetherian, then it is confluent if and only if it is locally
confluent.
Let S be a semigroup with presentation ⟨X : ui = vi, i ∈ I⟩, where
ui, vi ∈ X+. This presentation induces a rewriting system (X+,→) with
rules
xuiy → xviy (x, y ∈ X∗, i ∈ I).
Y. H. Wang, P. Gao, X. M. Ren 311
Then
∗↔ is the congruence on X+ generated by R = {(ui, vi) : i ∈ I}, and
hence S ∼= X+/
∗↔. In particular, if (X+,→) is noetherian and confluent,
then every element of S admits a unique normal form over X+.
1.3. Networks
In this subsection we give some basic definitions and results of networks.
For further details, of both background and technicalities, we refer the
reader to [9] and [22].
Definition 3. A network is a quadruple Γ = (V, T, s, r) consisting of a
non-empty set V of vertices, a non-empty set T of relations, and map-
pings s, r : T → P(V ), where P(V ) denotes the power set of V , such
that for each t ∈ T , the subsets s(t) and r(t) are non-empty and disjoint.
Each element t ∈ T is identified with the ordered pair (s(t), r(t)), where
s(t) and r(t) are called the source and the range of t, respectively.
Let Γ = (V, T, s, r) be a network. If for all t ∈ T , the sets s(t) and r(t)
are singletons, we identify Γ with the underlying simple directed graph
and refer to it simply as a graph. In a graph, a relation corresponds to
an edge connecting two vertices, whereas in a general network, a relation
connects two disjoint non-empty subsets of V .
For a network Γ = (V, T, s, r), define
T 0 = {A ⊆ V | ∃ t ∈ T, A = s(t) or A = r(t) } ∪ V,
and for each A ∈ T 0, set
s(A) = A = r(A).
Remark 1. Here we include V ⊆ T 0 to account for isolated vertices
v ∈ V in the network Γ, i.e., those for which there exists no t ∈ T with
v ∈ s(t) or v ∈ r(t). If Γ is a graph, then T 0 = V , since the source and
range of each relation are singleton sets.
Definition 4. Let Γ = (V, T, s, r) be a network. A path in Γ is a finite
sequence α = t1t2 · · · tn with ti ∈ T ∪ T 0 such that r(ti)∩ s(ti+1) ̸= ∅ for
1 ≤ i < n. The source and range of α are defined by s(α) = s(t1) and
r(α) = r(tn), respectively.
Elements of T 0 are regarded as trivial (empty) paths. Let P (Γ) de-
note the set of all paths in Γ, together with a zero element 0.
312 Network semigroups
Definition 5. A path α = t1t2 · · · tn ∈ P (Γ) \ {0} is called linear if
r(ti) = s(ti+1) for all 1 ≤ i < n.
Let LP (Γ) denote the set of all linear paths in Γ. Then T 0 ⊆ LP (Γ)
and 0 /∈ LP (Γ). If Γ is a graph, then every non-zero path is linear, and
hence P (Γ) = LP (Γ) ∪ {0}.
For non-zero paths α = t1 · · · tn and β = y1 · · · ym, their concatena-
tion αβ is defined as the sequence t1 · · · tny1 · · · ym. Then the following
lemma is immediate, and its proof is omitted.
Lemma 5. Let Γ = (V, T, s, r) be a network. Then:
(i) if α = t1· · ·tn ∈ LP (Γ), then ti · · · tj ∈ LP (Γ) for all 1 ≤ i < j ≤ n;
(ii) αβ ∈ P (Γ) \ {0} if and only if r(α) ∩ s(β) ̸= ∅;
(iii) if α, β ∈ LP (Γ) with r(α) = s(β), then αβ ∈ LP (Γ).
Definition 6. Let Γ = (VΓ, TΓ, s, r) and ∆ = (V∆, T∆, s, r) be networks.
A homomorphism ϕ : Γ → ∆ is a pair of maps ϕ = (ϕV , ϕT ), where
ϕV : VΓ → V∆ and ϕT : TΓ → T∆, such that for all t ∈ TΓ, s(t)ϕ =
{vϕV : v ∈ s(t)} = s(tϕT ) and r(t)ϕ = {vϕV : v ∈ r(t)} = r(tϕT ).
Let Γ = (VΓ, TΓ, s, r) and ∆ = (V∆, T∆, s, r) be networks. A homo-
morphism ϕ = (ϕV , ϕT ) : Γ → ∆ is called an isomorphism if both ϕV
and ϕT are bijections. In this case, Γ and ∆ are said to be isomorphic,
and we write Γ ∼= ∆.
Proposition 1. Let Γ = (VΓ, TΓ, s, r) and ∆ = (V∆, T∆, s, r) be net-
works. If ϕ = (ϕV , ϕT ) : Γ → ∆ is an isomorphism, then its inverse
ϕ−1 = (ϕ−1
V , ϕ−1
T ) : ∆ → Γ is also an isomorphism.
Proof. Since ϕ = (ϕV , ϕT ) is an isomorphism, both ϕV and ϕT are bijec-
tions, and hence ϕ−1
V and ϕ−1
T are well-defined bijections. It suffices to
show that ϕ−1 is a homomorphism.
Let t′ ∈ T∆. Since ϕT is surjective, there exists t ∈ TΓ such that
t′ = tϕT . Then
s(t′) = s(tϕT ) = {vϕV : v ∈ s(t)}.
Applying ϕ−1
V , we obtain
{wϕ−1
V : w ∈ s(t′)} = s(t),
and hence s(t′)ϕ−1 = s(t′ϕ−1
T ). Similarly, r(t′)ϕ−1 = {wϕ−1
V : w ∈ r(t′)}
= r(t′ϕ−1
T ). Thus ϕ−1 is a homomorphism, and therefore an isomorphism.
Y. H. Wang, P. Gao, X. M. Ren 313
2. The semigroup QΓ
The aim of this section is to construct a semigroup using paths in a
network.
Let Γ = (V, T, s, r) be a network. The set of inverse edges is defined
as
T−1 = { t−1 | t ∈ T },
which is in bijection with T and disjoint from T . For each t ∈ T , the
corresponding t−1 ∈ T−1 is a formal symbol with
s(t−1) = r(t), r(t−1) = s(t),
and it is distinct from any element of T , even if (r(t), s(t)) ∈ T .
Moreover, for any vertex A ∈ T 0, we set A−1 = A.
Let {0} be disjoint from T 0 ∪ T ∪ T−1. Extend the source and range
maps by defining
s(0) = r(0) = 0,
and define the involution on 0 by
0−1 = 0.
Definition 7. Let Γ = (V, T, s, r) be a network. The semigroup QΓ is
given by the presentation QΓ := ⟨X : R⟩, where
X = T 0 ∪ T ∪ T−1 ∪ {0},
and R consists of the following relations:
(NR1) s(t)t = t = tr(t) for t ∈ T 0 ∪ T ∪ T−1;
(NR2) t1t2 = 0 if r(t1) ∩ s(t2) = ∅ for t1, t2 ∈ T 0 ∪ T ∪ T−1;
(NR3) t−1
1 t2 = 0 if t1 ̸= t2 for t1, t2 ∈ T ;
(NR4) t−1t = r(t) for t ∈ T ;
(NR5) t−1A = 0 if s(t) ̸= A for t ∈ T and A ∈ T 0;
(NR6) 0x = 0 = x0 for all x ∈ X.
314 Network semigroups
By (NR6), the semigroup QΓ defined in Definition 7 has a zero ele-
ment 0. For A,B ∈ T 0, we regard the product AB as a path from A to
B whenever A ∩B ̸= ∅.
For a graph Γ, the associated graph inverse semigroup was introduced
by Ash and Hall [5] as the set of pairs (α, β) with α, β ∈ P (Γ) and
r(α) = r(β). Paterson [21] subsequently gave a presentation of this
semigroup and proved that the two constructions are isomorphic. In [21],
the graph inverse semigroup I(Γ) of a graph Γ = (V, T, s, r) is defined as
the semigroup generated by T 0∪T ∪T−1 together with a zero 0, subject
to the relations:
(V) uv = δuvu for all u, v ∈ T 0;
(E1) s(t)t = t = tr(t) for each t ∈ T ;
(E2) r(t)t−1 = t−1 = t−1s(t) for each t ∈ T ;
(CK1) t−1
1 t2 = δt1t2r(t1) for all t1, t2 ∈ T ,
where δ is Kronecker Delta.
Remark 2. Let Γ = (V, T, s, r) be a graph, that is, a network in which
s(t), r(t) ∈ V for all t ∈ T . Then the semigroup QΓ defined by (NR1)–
(NR6) coincides with the graph inverse semigroup I(Γ). Indeed, in this
case T 0 = V , and all sources and ranges are single vertices. Conse-
quently:
(i) By (NR2), for u, v ∈ V we have uv = 0 whenever u ̸= v, while
uu = u by (NR1). Hence uv = δuvu, which is precisely the vertex
relation (V).
(ii) Relation (NR1) gives s(t)t = t = tr(t) for all t ∈ T , which is exactly
(E1), and dually yields (E2) for t−1.
(iii) Relations (NR3) and (NR4) combine to give
t−1
1 t2 =
{
r(t1) t1 = t2,
0 t1 ̸= t2,
which is precisely the Cuntz–Krieger relation (CK1).
Y. H. Wang, P. Gao, X. M. Ren 315
(iv) Relation (NR5) reduces to
t−1A = 0 for A ∈ V, A ̸= s(t),
which simply enforces that products involving t−1 and a vertex
vanish unless the vertex matches the source of t. This is consistent
with the vertex relation (V).
(v) Relation (NR6) provides a zero element.
Proposition 2. If Γ is a graph then QΓ is the graph inverse semigroup
I(Γ).
Let Γ = (V, T, s, r) be a network. If α = t1t2 · · · tn ∈ P (Γ) \ {0},
where ti ∈ T ∪ T 0, then α is a word over T 0 ∪ T ∪ T−1. We define
α−1 = t−1
n · · · t−1
2 t−1
1 .
If Γ is a graph, then every element of the graph inverse semigroup I(Γ)
admits a unique representation of the form αβ−1, where α, β ∈ P (Γ).
Motivated by this, we show that each element of QΓ has a unique normal
form αβ−1, analogous to the graph inverse semigroup case.
Let Γ be a network and consider X = T 0 ∪T ∪T−1 ∪{0}. Define the
rewriting system (X+,→) using the following reduction rules (R1)-(R6)
corresponding to (NR1)-(NR6):
(R1) : s(t)t→ t, tr(t) → t, t ∈ T 0 ∪ T ∪ T−1,
(R2) : xy → 0, x, y ∈ T 0 ∪ T ∪ T−1, r(x) ∩ s(y) = ∅,
(R3) : x−1y → 0, x, y ∈ T, x ̸= y,
(R4) : x−1y → r(y), x, y ∈ T, x = y,
(R5) : x−1y → 0, x ∈ T, y ∈ T 0, s(x) ̸= y,
(R6) : 0x→ 0, x0 → 0 ∀x ∈ X.
Proposition 3. The rewriting system (X+,→) is confluent.
Proof. Let X = T 0 ∪ T ∪ T−1 ∪ {0} and consider the rewriting system
(X+,→) defined by rules (R1)-(R6). To prove confluence, it suffices to
consider the one-step overlapping case
(t1t2)t3 = t1(t2t3), t1, t2, t3 ∈ X,
that is, considering the situation
316 Network semigroups
t1t2t3
ut3 t1v
we must show in each case that there exists w with
w ,
ut3 t1v
∗∗
where
∗→ is the reflexive and transitive closure of →,
We consider all possible combinations of rules applied to t1t2 and
t2t3. Since 0x = x0 = 0 for all x ∈ X, if at least one of t1, t2, t3 is 0,
then(t1t2)t3 = 0 = t1(t2t3). Hence, it suffices to consider the case where
t1t2 and t2t3 satisfy one of the relations (R1)–(R5). Observe that it is
impossible for both t1t2 and t2t3 to satisfy (R3), (R4), or (R5) simulta-
neously. Therefore, there are exactly seven nontrivial cases to consider.
In each of the following cases, the dual situation (obtained by inter-
changing the roles of t1t2 and t2t3) can be verified analogously, and will
therefore be omitted.
We verify in each case that there exists an element w such that ut3∗→w
and t1v
∗→ w, where t1t2 → u and t2t3 → v.
Case 1. Both t1t2 and t2t3 satisfy (R1).
Suppose that t1t2 → u and t2t3 → v by (R1). Then four subcases
arise.
(i) Suppose that t1 = s(t2) and t2 = s(t3). Then t1 = t2 = s(t3) ∈ T 0,
u = t2 and v = t3. Hence
ut3 = t2t3 → t3, t1v = t1t3 → t3.
Thus both expressions reduce to w = t3.
(ii) Suppose that t1 = s(t2) and t3 = r(t2). Then u = v = t2. Hence
ut3 = t2t3 → t2, t1v = t1t2 → t2,
and we take w = t2.
(iii) Suppose that t2 = r(t1) and t2 = s(t3). Then u = t1 and v = t3.
Hence
ut3 = t1t3, t1v = t1t3,
Y. H. Wang, P. Gao, X. M. Ren 317
so both expressions coincide. Let w = t1t3.
(iv) Suppose that t2 = r(t1) and t3 = r(t2). Then t3= t2=r(t1) ∈ T 0,
u = t1 and v = t2. Hence
ut3 = t1t3 → t1, t1v = t1t2 → t1.
Thus both reduce to w = t1.
Case 2. t1t2 satisfies (R1) and t2t3 satisfies (R2).
Suppose that t1t2 → u and t2t3 → v by (R1) and (R2), respectively.
(i) If t1 = s(t2) and r(t2) ∩ s(t3) = ∅, then u = t2 and v = 0. Hence
ut3 = t2t3 → 0, t1v = t10 → 0,
so we take w = 0.
(ii) If t2 = r(t1) and r(t2) ∩ s(t3) = ∅, then r(t1) = t2 = r(t2) ∈ T 0,
u = t1 and v = 0. Hence
ut3 = t1t3 → 0, t1v = t10 → 0,
and again w = 0.
Case 3. t1t2 satisfies (R1) and t2t3 satisfies (R3).
In this case t1 = s(t2), t2 ∈ T−1, t3 ∈ T and t2 ̸= t−1
3 . Then u = t2
and v = 0. Hence
ut3 = t2t3 → 0, t1v = t10 → 0,
so w = 0.
Case 4. t1t2 satisfies (R1) and t2t3 satisfies (R4).
Here t1 = s(t2) and t2 = t−1
3 . Then t1 = r(t3), u = t2 and v = r(t3).
Hence
ut3 = t2t3 → r(t3), t1v = t1r(t3) → r(t3).
Thus w = r(t3).
Case 5. t1t2 satisfies (R1) and t2t3 satisfies (R5).
Here t1 = s(t2), t2 ∈ T−1, t3 ∈ T 0 and r(t2) ̸= t3. Then u = t2 and
v = 0. Hence
ut3 = t2t3 → 0, t1v = t10 → 0,
so w = 0.
Case 6. t1t2 satisfies (R2) and t2t3 satisfies (R2), (R3), or (R5).
318 Network semigroups
In all such cases we have u = 0 and v = 0, and hence
ut3 → 0, t1v → 0,
so w = 0.
Case 7. t1t2 satisfies (R2) and t2t3 satisfies (R4).
Then r(t1) ∩ s(t2) = ∅, s(t2) = r(t3), and so u = 0 and v = r(t3).
Hence
ut3 = 0t3 → 0, t1v = t1r(t3) = t1s(t2) → 0,
so w = 0.
This completes the verification.
The reader may ask why we do not define the product on T 0 by
AB = A ∩ B. We show that such a definition leads to a failure of
confluence. Let t ∈ T and let A ∈ T 0 satisfy r(t−1) ⊊ A. Suppose
that the product on T 0 is given by set-theoretic intersection, that is,
AB = A∩B for all A,B ∈ T 0. Then, using (NR1) and (NR5), we obtain
t−1r(t−1)A = (t−1r(t−1))A→ t−1A→ 0.
On the other hand, interpreting the product via intersection yields
t−1r(t−1)A = t−1
(
r(t−1)A
)
= t−1
(
r(t−1) ∩A
)
= t−1r(t−1) → t−1,
where we use r(t−1) ∩ A = r(t−1). Hence two distinct irreducible out-
comes are obtained, and so (X+,→) fails to be confluent.
By contrast, the rewriting system (X+,→), where X = T 0 ∪ T ∪
T−1 ∪ {0}, is clearly noetherian. It follows from Lemma 4 that every
element of QΓ admits a unique normal form as a word over X.
We next describe these normal forms. Observe that if α ∈ P (Γ)\{0},
then any reduction of α involves only relations of type (R1), and hence
preserves both s(α) and r(α). Consequently, every non-zero path reduces
to a unique irreducible path.
A path α = t1t2 · · · tn with ti ∈ T ∪ T 0 (1 ≤ i ≤ n) is said to be
reduced (or irreducible) if no adjacent pair admits a reduction, that is,
ti ̸= r(ti−1) and ti−1 ̸= s(ti) for all 2 ≤ i ≤ n.
Lemma 6. Let Γ = (V, T, s, r) be a network. For any α ∈ P (Γ) \ {0},
let α′ be the unique reduced path with [α] = [α′]. Then s(α) = s(α′) and
r(α) = r(α′).
Y. H. Wang, P. Gao, X. M. Ren 319
We remark that the reduction of a linear path is again linear, and
that 0 is irreducible. Define
RP (Γ) = {α ∈ P (Γ) : α is reduced},
and
RLP (Γ) = {α ∈ LP (Γ) : α is reduced}.
Then T ∪ T 0 ⊆ RLP (Γ) ⊆ RP (Γ), and
RLP (Γ) = { t1 · · · tn : ti ∈ T, r(ti) = s(ti+1) (1 ≤ i < n) } ∪ T 0.
Lemma 7. If α = t1 · · · tn ∈ RLP (Γ), then every subword ti · · · tj (1 ≤
i < j ≤ n) also lies in RLP (Γ).
Theorem 1. Each element of QΓ has a unique normal form of one of
the following types:
(i) [α], (ii) [β−1], (iii) [αβ−1], (iv) [0],
where α ∈ RP (Γ), β ∈ RLP (Γ)\T 0, and in (iii) one has r(α)∩r(β) ̸= ∅.
In particular, for A ∈ T 0, the normal form of [A] is [A], while [A−1]
reduces to [A].
Proof. Let [w] ∈ QΓ. By Proposition 3, we may assume that w is reduced.
If w ̸= 0, then w contains no subword of the form x−1y with x ∈ T ,
y ∈ T ∪ T 0, nor of the form x−1y−1 with x, y ∈ T such that yx is not
linear. It follows that w is of the form α, β−1, or αβ−1, where α ∈ RP (Γ),
β ∈ RLP (Γ) \ T 0, and in the latter case r(α) ∩ r(β) ̸= ∅.
Finally, if A ∈ T 0, we have A−1 = A, and hence any occurrence of
A−1 reduces to A. Therefore, the normal form of [A] is [A], and [A−1]
has the same normal form.
A word αβ−1 with α ∈ RP (Γ), β ∈ RLP (Γ) and r(α) = r(β) is
called a right normal form. In particular, 0 is in right normal form.
Each element of types (i)–(iii) in Theorem 1 can be written uniquely
in the form [αβ−1] with α ∈ RP (Γ), β ∈ RLP (Γ) and r(α) = r(β). More
precisely, one has
[α] = [αβ−1] with β = r(α),
and
[β−1] = [αβ−1] with α = r(β).
320 Network semigroups
Furthermore, if an element is given in the form [αβ−1], then
[αβ−1] =
{
[αβ−1] if r(α) = r(β),
[µβ−1] otherwise,
where µ = α r(β).
Corollary 1. Each element of QΓ admits a unique representative of the
form αβ−1 in right normal form, where α ∈ RP (Γ), β ∈ RLP (Γ) and
r(α) = r(β).
Lemma 8. If α ∈ LP (Γ) \ {0}, then [α−1α] = [r(α)].
Proof. The claim is immediate if α ∈ T ∪ T 0 by (NR1) and (NR4).
Let α = t1 · · · tn with r(ti) = s(ti+1) for 1 ≤ i < n. Then repeated
applications of (NR4) and (NR1) yield
[α−1α] = [t−1
n · · · t−1
1 t1 · · · tn] = [t−1
n tn] = [r(tn)] = [r(α)].
Lemma 9. Let [αβ−1], [µν−1] ∈ QΓ \ {[0]} be such that αβ−1 and µν−1
are in right normal form, where α, µ ∈ RP (Γ) and β, ν ∈ RLP (Γ). Then
[αβ−1][µν−1] =
[αµν−1] if β = r(α) ∈ T 0 and r(α) ∩ s(µ) ̸= ∅,
[α(νβ)−1] if β /∈ T 0, µ = r(ν) = s(β),
[αν−1] if β /∈ T 0 and µ = β,
[αξν−1] if β /∈ T 0 and µ = βξ for some ξ ∈ RP (Γ),
[α(νη)−1] if β /∈ T 0 and β = µη for some η ∈ RLP (Γ),
[0] otherwise.
Proof. Let [αβ−1], [µν−1] ∈ QΓ\{[0]} be such that αβ−1 and µν−1 are in
right normal form. We proceed by a case analysis, according to whether
β ∈ T 0 or β /∈ T 0, and whether µ ∈ T 0 or µ /∈ T 0.
Case 1. β ∈ T 0. Then β = r(α).
If r(α)∩ s(µ) = ∅, then by (NR2), [αβ−1][µν−1] = [αr(α)µν−1] = [0].
If r(α) ∩ s(µ) ̸= ∅, then by (NR1), [αβ−1][µν−1] = [αr(α)µν−1] =
[αµν−1].
Y. H. Wang, P. Gao, X. M. Ren 321
Case 2. β /∈ T 0 and µ ∈ T 0. Then µ = r(ν).
If s(β) = µ, then by (NR1), [αβ−1][µν−1] = [αβ−1ν−1] = [α(νβ)−1].
Otherwise, by (NR5), the product is [0].
Case 3. β /∈ T 0 and µ /∈ T 0.
(i) Suppose that β and µ are prefix comparable.
(a1) If µ = β, then using Lemma 8, r(α) = r(β) and (NR1), we get
[αβ−1][µν−1] = [αν−1].
(a2) If µ = βξ for some ξ ∈ RP (Γ), then using Lemma 8, r(α) = r(β)
and (NR1),
[αβ−1][µν−1] = [α(β−1β)ξν−1] = [αr(β)ξν−1] = [αξν−1].
(a3) If β = µη for some η ∈ RLP (Γ), then µ ∈ RLP (Γ) and r(µ) =
s(η). By Lemma 8 and (NR1),
[αβ−1][µν−1] = [αη−1µ−1µν−1] = [αη−1r(µ)ν−1] =[αη−1ν−1]
=[α(νη)−1].
(ii) Suppose that β and µ are not prefix comparable. Write β=x1x2· · ·xm
and µ = y1y2 · · · yn, where xi ∈ T and yj ∈ T ∪ T 0.
(a1) If x1 ̸= y1, then β
−1µ→ 0.
Indeed, if y1 ∈ T , then x−1
1 y1 → 0 by (NR3). If y1 ∈ T 0, then either
y1 ̸= s(x1), so x
−1
1 y1 → 0 by (NR5), or y1 = s(x1), in which case, since
µ is reduced, y1 ̸= s(y2) and hence
x−1
1 y1y2 → x−1
1 s(y2)y2 → 0
by (NR5). Thus β−1µ→ 0, and so [αβ−1][µν−1] = [0].
(a2) Otherwise, let k ≥ 2 be minimal such that xk ̸= yk and xj = yj
for 1 ≤ j ≤ k − 1. Then
β−1µ = x−1
m · · ·x−1
k+1x
−1
k (x−1
k−1 · · ·x
−1
1 x1 · · ·xk−1)yk · · · yn.
Since β ∈ RLP (Γ), we have r(xi−1) = s(xi), and hence
x−1
k−1 · · ·x
−1
1 x1 · · ·xk−1 → r(xk−1)
by Lemma 8. Thus
β−1µ→ x−1
m · · ·x−1
k+1x
−1
k yk · · · yn.
322 Network semigroups
Since xk ̸= yk, if yk ∈ T then x−1
k yk → 0 by (NR3); if yk ∈ T 0, then
reducedness of µ implies r(yk−1) ̸= yk, but xk−1 = yk−1 and r(xk−1) =
s(xk), so s(xk) = r(yk−1) ̸= yk. Hence x−1
k yk → 0 by (NR5). Therefore
β−1µ→ 0.
Consequently, [αβ−1][µν−1] = [α(β−1µ)ν−1] = [0].
Combining all cases yields the result.
Lemma 10. The set of idempotents of QΓ is
E(QΓ) = {[αα−1] : α ∈ RLP (Γ)} ∪ {[0]}.
Moreover,
E = E(QΓ) \ {[A] : A ∈ T 0} = {[αα−1] : α ∈ RLP (Γ) \ T 0} ∪ {[0]}
is a subsemilattice of QΓ.
Proof. It is immediate that [0] ∈ E(QΓ). By Lemma 8 together with
(NR1), for every α ∈ RLP (Γ) the element [αα−1] is idempotent.
Conversely, let [αβ−1] ∈ QΓ \ {[0]} be idempotent, where αβ−1 is in
right normal form. Then [αβ−1]2 = [αβ−1], and hence, by Lemma 9, one
of the following cases occurs.
(i) If β = r(α) ∈ T 0, then [α] = [αβ−1] = [αβ−1]2 = [αα], which
implies that α ∈ T 0. Thus α = β ∈ RLP (Γ).
(ii) Assume now that β /∈ T 0. If α = r(β) = s(β) ∈ T 0, then
[αβ−1] = [β−1], which is not idempotent, a contradiction. Hence α /∈ T 0.
If α = β, then clearly [αβ−1] = [αα−1]. Otherwise, either α = βξ for
some ξ ∈ RP (Γ) or β = αη for some η ∈ RLP (Γ).
If α = βξ, then [αβ−1] = [αβ−1]2 = [αξβ−1], and since αβ−1 is
in right normal form, it follows that [α] = [αξ] or [ξβ−1] = [β−1]. As
α ∈ RP (Γ) and β ∈ RLP (Γ) \ {[0]}, this forces ξ = r(α) = r(β),
contradicting the reducedness of α = βξ.
If β = αη, then [αβ−1] = [α(βη)−1], so [β] = [βη]. Since β /∈ T 0,
we deduce that η = r(β) ∈ T 0, again contradicting the reducedness of
β = αη.
Hence neither of the above cases can occur, and we conclude that
α = β ∈ RLP (Γ). Therefore [αβ−1] = [αα−1], and so E(QΓ) = {[αα−1] :
α ∈ RLP (Γ)} ∪ {[0]}.
Finally, let [αα−1], [ββ−1] ∈ E \ {[0]}. By Lemma 9,
[αα−1][ββ−1] =
[ββ−1] if β = αξ for some ξ ∈ RLP (Γ),
[αα−1] if α = β or α = βη for some η ∈ RLP (Γ),
[0] otherwise.
Y. H. Wang, P. Gao, X. M. Ren 323
In particular, the product is commutative and again lies in E. Hence E
is a semilattice.
Remark 3. Let A,B ∈ T 0 with A ̸= B. Then [A], [B] ∈ E(QΓ). Howe-
ver, if A ∩B ̸= ∅, then [AB] /∈ E(QΓ), and moreover [A][B] ̸= [B][A]. It
follows that, in general, E(QΓ) is neither closed under multiplication nor
commutative; in particular, E(QΓ) need not form a subsemigroup of QΓ.
Lemma 11. Let [αβ−1] ∈ QΓ be such that αβ−1 is in right normal form.
Then [αβ−1] is regular if and only if α ∈ RLP (Γ) or [αβ−1] = [0].
Proof. It is clear that [0] is regular. Suppose that α ∈ RLP (Γ). Then,
using (NR1) and Lemma 8, we obtain
[αβ−1][βα−1][αβ−1] =[αr(β)(α−1α)β−1] = [α(α−1α)β−1]
=[αr(α)β−1] = [αβ−1],
where r(α) = r(β). Thus [βα−1] is an inverse of [αβ−1], and hence [αβ−1]
is regular.
Conversely, let [αβ−1] ∈ QΓ\{[0]} be regular, and suppose that [µν−1]
is an inverse of [αβ−1], where both αβ−1 and µν−1 are in right normal
form. Then [αβ−1][µν−1] is a non-zero idempotent, and so [αβ−1][µν−1]
= [ζζ−1] for some ζ ∈ RLP (Γ). By Lemma 9, it follows that α is a prefix
of ζ, and hence α ∈ RLP (Γ) by Lemma 7.
Lemma 12. Let α, β ∈ RLP (Γ) with r(α) = r(β). Then [βα−1] is the
unique inverse of [αβ−1] in QΓ.
Proof. Since α, β ∈ RLP (Γ) and r(α) = r(β), both αβ−1 and βα−1 are
in right normal form. By Lemma 11, [βα−1] is an inverse of [αβ−1].
To prove uniqueness, let [µν−1] be any inverse of [αβ−1]. Then
[αβ−1][µν−1][αβ−1] = [αβ−1], (1)
and [µν−1] is regular. Hence, by Lemma 11, µ ∈ RLP (Γ).
We analyse the product [αβ−1][µν−1].
Case 1. β ∈ T 0. Then β = r(α), and by Lemma 9, [αβ−1][µν−1] =
[αµν−1], whenever r(α) ∩ s(µ) ̸= ∅. Hence
[αβ−1][µν−1][αβ−1] = [αµν−1][αβ−1].
Applying Lemma 9 again, the left component of the product[αµν−1][αβ−1]
is αµ (or an extension thereof). For (1) to hold, this must coincide
324 Network semigroups
with α, which forces µ = r(α) = β. Substituting µ = β, we obtain
[αβ−1][µν−1] = [αβ−1][βν−1] = [αν−1], and hence
[αν−1][αβ−1] = [αβ−1].
Since α ∈ RLP (Γ), a further application of Lemma 9 yields ν = α. Thus
[µν−1] = [βα−1].
Case 2. β /∈ T 0. Since β, µ ∈ RLP (Γ), Lemma 9 shows that a non-zero
product can occur only in one of the following cases:
(i) µ = r(ν) = s(β);
(ii) µ = β;
(iii) µ = βξ for some ξ ∈ RP (Γ);
(iv) β = µη for some η ∈ RLP (Γ).
If (i) holds, then [αβ−1][µν−1] = [α(νβ)−1], and hence
[αβ−1][µν−1][αβ−1] = [α(νβ)−1][αβ−1].
For (1) to hold, Lemma 9 forces νβ = α, and thus [ν−1] = [βα−1].
Consequently,
[µν−1] = [s(β)βα−1] = [βα−1].
If (iii) holds with non-trivial ξ, then [αβ−1][µν−1] = [αξν−1], and
hence
[αβ−1][µν−1][αβ−1] = [αξν−1][αβ−1].
By Lemma 9, the left component is αξ (or an extension thereof), which
cannot equal α. Hence (1) cannot hold.
If (iv) holds with non-trivial η, then [αβ−1][µν−1] = [α(νη)−1], and
similarly the product in (1) cannot reduce to [αβ−1], a contradiction.
Therefore the only possible case is (ii), namely µ = β. Substituting
into (1), we obtain [αβ−1][βν−1][αβ−1] = [αβ−1]. As in Case 1, repeated
application of Lemma 9 yields ν = α.
Thus in all cases µ = β and ν = α, and hence [µν−1] = [βα−1].
Therefore [βα−1] is the unique inverse of [αβ−1].
Lemma 13. Let [αβ−1] ∈ QΓ \ {[0]} be regular, where αβ−1 is in right
normal form. Then α, β ∈ RLP (Γ) and [αα−1]R [αβ−1]L [ββ−1], where
[αα−1], [ββ−1] ∈ E(QΓ).
Y. H. Wang, P. Gao, X. M. Ren 325
Lemma 14. Let [αβ−1] ∈ QΓ\{[0]} be such that αβ−1 is in right normal
form. Then [αβ−1]L∗ [ββ−1].
Proof. Let [αβ−1] ∈ QΓ \ {[0]} with αβ−1 in right normal form. Then
β ∈ RLP (Γ), and hence [ββ−1] ∈ E(QΓ) by Lemma 10. Moreover,
[αβ−1][ββ−1] = [αβ−1].
To verify that [αβ−1]L∗ [ββ−1], let [x1y
−1
1 ], [x2y
−1
2 ] ∈ QΓ be such
that x1y
−1
1 and x2y
−1
2 are in right normal form and [αβ−1][x1y
−1
1 ] =
[αβ−1][x2y
−1
2 ]. We show that [ββ−1][x1y
−1
1 ] = [ββ−1][x2y
−1
2 ].
First assume that β = r(α) ∈ T 0. Then [ββ−1] = [r(α)]. By
Lemma 9, the equality [αβ−1][x1y
−1
1 ] = [αβ−1][x2y
−1
2 ] implies either
r(α) ∩ s(x1) = ∅ and r(α) ∩ s(x2) = ∅, or r(α) ∩ s(x1) ̸= ∅ and r(α) ∩
s(x2) ̸= ∅. In the former case, [r(α)][x1y
−1
1 ] = [r(α)][x2y
−1
2 ] = [0]. In the
latter case, [αx1y
−1
1 ] = [αx2y
−1
2 ], and since α ∈ RP (Γ) it follows that
[r(α)x1y
−1
1 ] = [r(α)x2y
−1
2 ]. Thus [ββ−1][x1y
−1
1 ] = [ββ−1][x2y
−1
2 ].
Assume now that β /∈ T 0. We proceed by a case analysis according
to whether x1 or x2 belongs to T 0.
(i) If x1, x2 ∈ T 0, then using Lemma 9, the equality [αβ−1][x1y
−1
1 ] =
[αβ−1][x2y
−1
2 ] implies that either x1 = x2 = s(β) or x1 ̸= s(β) and x2 ̸=
s(β). In the former case, the equality [αβ−1][x1y
−1
1 ] = [αβ−1][x2y
−1
2 ]
yields [α(y1β)
−1] = [α(y2β)
−1], and since α ∈ RP (Γ) we obtain
[r(α)(y1β)
−1] = [r(α)(y2β)
−1].
Using r(α) = r(β), this gives [β(y1β)
−1] = [β(y2β)
−1], that is,
[ββ−1][x1y
−1
1 ] = [ββ−1][x2y
−1
2 ].
In the latter case, both products [ββ−1][xiy
−1
i ] are equal to [0] for i = 1, 2.
(ii) Suppose that either x1 ∈ T 0 and x2 /∈ T 0, or x1 /∈ T 0 and
x2 ∈ T 0. Since the latter situation is dual to the former, it suffices
to consider the case where x1 ∈ T 0 and x2 /∈ T 0. By Lemma 9, the
equality [αβ−1][x1y
−1
1 ] = [αβ−1][x2y
−1
2 ] implies that either x1 = s(β)
and x2 is prefix-comparable with β, or x1 ̸= s(β) and x2 is not prefix-
comparable with β. In the latter case, both products are equal to [0],
and the conclusion is immediate.
Assume therefore that x1 = s(β) and that x2 is prefix-comparable
with β. By Lemma 9, [αβ−1][x1y
−1
1 ] = [α(y1β)
−1] and there exist three
subcases for x2 and β.
(a1) If β = x2, then, by Lemma 9, [αβ−1][x2y
−1
2 ] = [αy−1
2 ]. Hence
[α(y1β)
−1] = [αy−1
2 ]. Since α ∈ RP (Γ), we get
[r(α)(y1β)
−1] = [r(α)y−1
2 ],
326 Network semigroups
and so [βr(α)(y1β)
−1] = [βr(α)y−1
2 ]. Noting that r(α) = r(β), we obtain
[β(y1β)
−1] = [βy−1
2 ], that is, [ββ−1][x1y
−1
1 ] = [ββ−1][x2y
−1
2 ] as required.
(a2) If x2 = βµ2 for some µ2 ∈ RP (Γ), then
[αβ−1][x2y
−1
2 ] = [αµ2y
−1
2 ],
and the same argument as in (a1) gives
[α(y1β)
−1] = [αµ2y
−1
2 ] ⇒ [β(y1β)
−1] = [βµ2y
−1
2 ].
So [ββ−1][x1y
−1
1 ] = [ββ−1][x2y
−1
2 ].
(a3) If β = x2ξ2 for some ξ2 ∈ RLP (Γ), then [αβ−1][x2y
−1
2 ] =
[α(y2ξ2)
−1], and arguing as in (a1) we obtain
[α(y1β)
−1] = [α(y2ξ2)
−1] ⇒ [β(y1β)
−1] = [β(y2ξ2)
−1].
So [ββ−1][x1y
−1
1 ] = [ββ−1][x2y
−1
2 ].
(iii) We now suppose that both x1, x2 /∈ T 0. If β is prefix comparable
with exactly one of x1 and x2, then Lemma 9 yields [αβ−1][x1y
−1
1 ] ̸=
[αβ−1][x2y
−1
2 ], a contradiction. Hence β is either prefix comparable with
both x1 and x2, or with neither.
If β is not prefix comparable with either x1 or x2, then both
[αβ−1][xiy
−1
i ] and [ββ−1][xiy
−1
i ] are equal to [0] for i = 1, 2.
Otherwise, β is prefix comparable with both x1 and x2. It suffices to
consider the case where x1 = βµ1 and x2 = βµ2 for some µ1, µ2 ∈ RP (Γ),
the remaining cases being analogous.Then [αβ−1][xiy
−1
i ]=[αµiy
−1
i ] ̸= [0]
for i = 1, 2, and the hypothesis yields [αµ1y
−1
1 ] = [αµ2y
−1
2 ]. Since α ∈
RP (Γ), we obtain [r(α)µ1y
−1
1 ] = [r(α)µ2y
−1
2 ], and hence [βµ1y
−1
1 ] =
[βµ2y
−1
2 ] as r(α) = r(β). Noting that [ββ−1][xiy
−1
i ] = [βµiy
−1
i ] for i =
1, 2, we conclude that [ββ−1][x1y
−1
1 ] = [ββ−1][x2y
−1
2 ].
Therefore [αβ−1]L∗ [ββ−1] by Lemma 1.
Lemma 15. Suppose that [αβ−1], [µν−1] ∈ QΓ \ {[0]}, where αβ−1 and
µν−1, are in right normal form. Then:
(i) [αβ−1]L∗ [µν−1] if and only if β = ν;
(ii) if α, µ ∈ RLP (Γ), then [αβ−1]R [µν−1] if and only if α = µ.
Proof. (i) By Lemma 14, we have [αβ−1]L∗ [ββ−1] and [µν−1]L∗ [νν−1].
Hence [αβ−1]L∗ [µν−1] if and only if [ββ−1]L∗ [νν−1]. Since [ββ−1],
[νν−1] ∈ E(QΓ), Lemma 11 implies that L∗ coincides with L on idem-
potents, and thus [ββ−1]L [νν−1]. It is immediate that β = ν implies
Y. H. Wang, P. Gao, X. M. Ren 327
[αβ−1]L∗ [µν−1]. Conversely, assume that [ββ−1]L [νν−1]. We distin-
guish three cases.
Case 1. If β = r(α) ∈ T 0 and ν = r(µ) ∈ T 0, then [ββ−1] = [β]
and [νν−1] = [ν]. The relation [β]L [ν] means that [β][ν] = [β] and
[ν][β] = [ν], which forces r(β) = r(ν), and hence β = ν.
Case 2. If β, ν ∈ RLP (Γ) \ T 0, then by Lemma 10 the idempo-
tents commute, that is, [ββ−1][νν−1] = [νν−1][ββ−1]. The condition
[ββ−1]L [νν−1] implies β = ν.
Case 3. If one of β, ν lies in T 0 and the other lies in RLP (Γ) \ T 0,
then, say β ∈ T 0 and ν /∈ T 0, we have [ββ−1] = [β] ̸= [ββ−1][νν−1], so
([ββ−1], [νν−1]) /∈ L, a contradiction. The symmetric case is analogous.
Hence this situation cannot occur.
Thus β = ν, and the proof of (i) is complete.
(ii) Let α, µ ∈ RLP (Γ). Then [αβ−1] and [µν−1] are regular by
Lemma 11. By Lemma 13, we have [αβ−1]R [αα−1] and [µν−1]R [µµ−1].
Hence [αβ−1]R [µν−1] if and only if [αα−1]R [µµ−1]. Arguing as in
part (i), this is equivalent to α = µ.
Lemma 16. Suppose that µ, η ∈ RP (Γ), y ∈ RLP (Γ), µ = yη, and
[µν−1] ∈ QΓ\{[0]} with µν−1 in right normal form. Then ([yy−1], [µν−1])
/∈ R∗.
Proof. Assume that µ, η ∈ RP (Γ), y ∈ RLP (Γ) and µ = yη, and let
[µν−1] ∈ QΓ \ {[0]} be such that µν−1 is in right normal form.
Let [αβ−1] ∈ QΓ \ {[0]}, and choose [xy−1], [x1y
−1
1 ] ∈ QΓ in right
normal form such that α = yξ = y1ξ1 and xξ = x1ξ1 for some ξ, ξ1 ∈
RLP (Γ), where y1 and µ are not prefix comparable. Then
[xy−1][αβ−1] = [xξβ−1] = [x1ξ1β
−1] = [x1y
−1
1 ][αβ−1],
whereas
[xy−1][µν−1] = [xην−1] ̸= [0] = [x1y
−1
1 ][µν−1].
It follows that ([αβ−1], [µν−1]) /∈ R∗.
Now argue by contradiction. If ([yy−1], [µν−1]) ∈ R∗, then also
([yy−1], [αβ−1]) ∈ R∗, and hence ([αβ−1], [µν−1]) ∈ R∗, contradicting
the above. Therefore ([yy−1], [µν−1]) /∈ R∗.
328 Network semigroups
Let [yy−1] ∈ E(QΓ) \ {[0]}. By Lemma 10, we have y ∈ RLP (Γ).
Let µ ∈ RP (Γ) \ RLP (Γ) be a non-zero element. Then either y is a
prefix of µ, or y is not prefix-comparable with µ. If y is a prefix of µ,
then by Lemma 16, the idempotent [yy−1] need not be R∗-related to
[µν−1] ∈ QΓ. If y is not prefix-comparable with µ, then by Lemma 9 we
have [yy−1][µν−1] = [0]. It follows that there exists an R∗-class of QΓ
which contains no idempotent, and hence QΓ is not left abundant. On
the other hand, by Lemma 15 (i) and Lemma 14, each L∗-class of QΓ
contains a unique idempotent. Therefore, we obtain the following.
Theorem 2. The semigroup QΓ is a right ∗-abundant semigroup with
zero.
Put
SΓ = {[αβ−1] ∈ QΓ : α ∈ RP (Γ), β ∈ RLP (Γ)\T 0, r(α) = r(β)}∪{[0]}.
Then the set
E = E(QΓ) \ {[A] : A ∈ T 0} = {[αα−1] : α ∈ RLP (Γ) \ T 0} ∪ {[0]}
coincides with the set of idempotents of SΓ. It follows from Lemma 9
that SΓ is a subsemigroup of QΓ. Moreover, since β ∈ RLP (Γ) \ T 0 for
every [αβ−1] ∈ SΓ, the multiplication in SΓ can be described as follows:
for all [αβ−1], [µν−1] ∈ SΓ,
[αβ−1][µν−1] =
[α(νβ)−1] if µ = r(ν) = s(β),
[αν−1] if β = µ,
[αξν−1] if µ = βξ for some ξ ∈ RP (Γ),
[α(νη)−1] if β = µη for some η ∈ RLP (Γ),
[0] otherwise.
Proposition 4. The semigroup SΓ is a right ample semigroup with zero.
Proof. By Lemma 10 and Lemma 14, the semigroup SΓ is right abundant
and its set of idempotents forms the semilattice E = {[αα−1] : α ∈
RLP (Γ) \ T 0} ∪ {[0]}. Thus it suffices to verify the right ample identity
ea = a(ea)∗ for all e ∈ E and a ∈ SΓ \ {[0]}.
Let e = [ξξ−1] ∈ E and a = [αβ−1] ∈ SΓ \ {[0]}. By Lemma 9, the
product [ξξ−1][αβ−1] is equal to [αβ−1] if α = ξ or α = ξµ for some
µ ∈ RP (Γ), is equal to [ξ(βη)−1] if ξ = αη for some η ∈ RLP (Γ), and is
Y. H. Wang, P. Gao, X. M. Ren 329
[0] otherwise. Consequently, ([ξξ−1][αβ−1])∗ = [ββ−1] in the first case,
[(βη)(βη)−1] in the second case, and [0] otherwise.
A direct computation, again using Lemma 9, shows that [αβ−1][ββ−1]
= [αβ−1] and [αβ−1][βη(βη)−1] = [ξ(βη)−1] whenever ξ = αη, while
in the remaining case both products are equal to [0]. It follows that
[αβ−1]([ξξ−1][αβ−1])∗ coincides with [ξξ−1][αβ−1] in all cases. Hence
ea = a(ea)∗, and therefore SΓ is right ample with zero.
By Lemma 11, if α, β ∈ RLP (Γ) with r(α) = r(β), then [αβ−1] is
regular. Define
RΓ = {[αβ−1] ∈ SΓ : α, β ∈ RLP (Γ) \ T 0 and r(α) = r(β)} ∪ {[0]}.
Then E ⊆ RΓ, and by Lemma 2 the set RΓ is an inverse semigroup of SΓ.
Moreover, by Lemma 15, the Green’s relation H = L∩R is trivial on RΓ.
Recall that a semigroup is fundamental if the only congruence contained
in H is the identity congruence [19]. Hence we obtain the following.
Corollary 2. The semigroup RΓ is a fundamental inverse semigroup
and a subsemigroup of SΓ.
3. The congruence-free case
The aim of this section is to investigate congruence-free conditions on
QΓ. We will consider congruences to be semigroup congruences, unless
stated otherwise. Congruences compatible with both the multiplication
and the unary operation ∗ will be referred to as ∗-congruences.
We begin by recalling that a semigroup is said to be congruence-free
if it admits precisely two congruences, namely the identity congruence
and the universal congruence. A congruence ρ on a semigroup S with
set of idempotents E(S) is called idempotent-separating if eρ ̸= fρ for
all distinct e, f ∈ E(S). A non-empty subset I of S is an ideal if SI ⊆ I
and IS ⊆ I, and such an ideal is said to be proper if I ̸= S.
Lemma 17. Let I = {[αβ−1] ∈ QΓ : α ∈ RP (Γ) \ RLP (Γ)} ∪ {[0]}.
Then I is a proper ideal of QΓ. Moreover, the relation ρI = (I× I)∪1QΓ
is an idempotent-separating congruence on QΓ.
Proof. By Lemma 9, the set I is closed under multiplication in QΓ, and
clearly QΓ \ I ̸= ∅, so I ̸= QΓ. Let [αβ−1] ∈ I and [µν−1] ∈ QΓ.
Since α ∈ RP (Γ) \ RLP (Γ), an application of Lemma 9 shows that
[αβ−1][µν−1] ∈ I.
330 Network semigroups
To verify that QΓI ⊆ I, consider [µν−1][αβ−1]. Since α /∈ RLP (Γ)
and ν ∈ RLP (Γ), Lemma 7 implies that ν ̸= α and ν ̸= αη for any
η ∈ RLP (Γ). Hence, by Lemma 9, the product [µν−1][αβ−1] is equal to
[µαβ−1] if ν = r(µ) and r(µ)∩ s(α) ̸= ∅, or to [µξν−1] if α = νξ for some
ξ ∈ RP (Γ), and is [0] otherwise.
If ν = r(µ) and r(µ) ∩ s(α) ̸= ∅, then µα ∈ RP (Γ) \ RLP (Γ) since
α ∈ RP (Γ) \ RLP (Γ), and hence [µαβ−1] ∈ I. If α = νξ for some
ξ ∈ RP (Γ), then either r(ν) ̸= s(ξ) with r(ν) ∩ s(ξ) ̸= ∅, or r(ν) = s(ξ)
and ξ ∈ RP (Γ) \ RLP (Γ). In the former case, since r(µ) = r(ν), we
have r(µ) ̸= s(ξ) and r(µ) ∩ s(ξ) ̸= ∅, so µξ ∈ RP (Γ) \ RLP (Γ) and
thus [µξν−1] ∈ I. In the latter case, µξ ∈ RP (Γ) \RLP (Γ) again follows
directly, and hence [µξν−1] ∈ I. In the remaining case the product is
[0] ∈ I. Therefore QΓI ⊆ I, and so I is an ideal of QΓ; moreover, it is
proper.
Finally, by Lemma 10, the only idempotent contained in I is [0]. It
follows immediately that ρI is an idempotent-separating congruence on
QΓ.
A similar construction yields a proper ideal of SΓ.
Lemma 18. Let I = {[αβ−1] ∈ SΓ : α ∈ RP (Γ) \ RLP (Γ)} ∪ {[0]}.
Then I is a proper ideal of SΓ, and ρI = (I × I)∪ 1SΓ
is an idempotent-
separating congruence on SΓ.
Proof. The proof is analogous to that of Lemma 17, and is therefore
omitted.
According to Lemma 11, Lemma 17 and Lemma 18, the semigroups
QΓ and SΓ fail to be congruence-free whenever they contain non-regular
elements. Indeed, if t ∈ T satisfies |s(t)| > 1 and v ∈ s(t), then vt ∈
RP (Γ) \ RLP (Γ), whence [vtt−1] ∈ SΓ ⊆ QΓ is a non-regular element.
This yields the following result.
Theorem 3. Let Γ = (V, T, s, r) be a network. If there exists t ∈ T with
|s(t)| > 1, then neither QΓ nor SΓ is congruence-free.
Let Γ = (V, T, s, r) be a network. For each subset A ⊆ V , the cardi-
nality of the set {t ∈ T : s(t) = A} is called the out-index of A in Γ, and
is denoted by o(A).
Let S be a right abundant semigroup. An ideal I of S is called
a ∗-ideal if it is closed under the relation L∗. Viewing S as a unary
semigroup, it is straightforward to verify that if I is a proper ∗-ideal of
Y. H. Wang, P. Gao, X. M. Ren 331
S, then ρI = (I× I)∪ 1S is a unary semigroup congruence on S. Indeed,
if a ρI b, then either a = b, in which case a∗ = b∗ trivially, or a, b ∈ I,
and hence a∗, b∗ ∈ I since I is closed under the unary operation ∗; thus
a∗ ρI b
∗.
A right ∗-abundant semigroup is said to be ∗-congruence-free if it
admits only two unary semigroup congruences, namely the identity con-
gruence and the universal congruence.
Lemma 19. Let Γ = (V, T, s, r) be a network and let t ∈ T be such
that o(r(t)) = 0 and there exists no A ∈ T 0 \ V with r(t) ⊆ A. Then
the principal ideal I = QΓ[tt
−1]QΓ generated by [tt−1] is a proper ∗-ideal
of QΓ.
Proof. Let t ∈ T satisfy the stated hypotheses. We first show that
|r(t)| = 1. Indeed, if |r(t)| > 1, then r(t) ∈ T 0 \ V and trivially
r(t) ⊆ r(t), contradicting the assumption. Hence r(t) is a singleton.
We derive the explicit description of the ideal I = QΓ[tt
−1]QΓ using
Lemma 9.
Let [αβ−1], [µν−1] ∈ QΓ \ {[0]} be such that αβ−1 and µν−1 are in
right normal form. We first compute the product [αβ−1][tt−1]. Since
t, β ∈ RLP (Γ), Lemma 9 shows that a non-zero product can occur only
if either β = r(α) ∈ T 0 and r(α) ∩ s(α) ̸= ∅ or β /∈ T 0 and t are prefix
comparable, namely in the cases β = t, β = tξ for some ξ ∈ RP (Γ), or
t = βη for some η ∈ RLP (Γ).
In the former case, we get [αβ−1][tt−1] = [att−1]. In the later case, the
assumption o(r(t)) = 0 and |r(t)| = 1 exclude any non-trivial extension
at r(t). Consequently, neither β = tξ with non-trivial ξ nor t = βη with
non-trivial η can occur. Hence only the case β = t yields a non-zero
product, and then [αβ−1][tt−1] = [αt−1]. Thus every non-zero element
of QΓ[tt
−1] is of the form [γt−1] with γ ∈ RP (Γ) and r(γ) = r(t).
Next, consider the product [γt−1][µν−1]. By Lemma 9, a non-zero
product can occur either when µ = r(ν) = s(t) or when t and µ are
prefix comparable. In the former case we obtain [γt−1][µν−1] = [γ(νt)−1],
therefore the resulting element again has r(γ) = r(νt) = r(t).
In the latter case, prefix comparability yields µ = t, µ = tξ for
some ξ ∈ RP (Γ), or t = µη for some η ∈ RLP (Γ). As before, the
condition o(r(t)) = 0 excludes the possibilities µ = tξ and t = µη, so
that necessarily µ = t. In this case we obtain [γt−1][µν−1] = [γν−1], and
clearly r(γ) = r(ν) = r(t).
Combining the above, every non-zero element of QΓ[tt
−1]QΓ is of the
form [αβ−1] with α ∈ RP (Γ), β ∈ RLP (Γ) and r(α) = r(β) = r(t).
332 Network semigroups
Therefore,
QΓ[tt
−1]QΓ = {[αβ−1] : α ∈ RP (Γ), β ∈ RLP (Γ),
r(α) = r(β) = r(t)} ∪ {[0]}.
By Lemma 15(i), each L∗-class in QΓ is determined by the second
component in right normal form; hence I is closed under L∗ and therefore
is a ∗-ideal. Finally, since s(t) ∩ r(t) = ∅, we have [s(t)] /∈ I, so that I is
a proper ideal of QΓ.
The following consequence is immediate.
Theorem 4. Let Γ = (V, T, s, r) be a network. If there exists t ∈ T such
that o(r(t)) = 0 and there is no A ∈ T 0 \ V with r(t) ⊆ A, then QΓ is
not ∗-congruence-free as a unary semigroup.
Lemma 20. Let Γ=(V, T, r, s)be a network with |T |>1, and let t, q ∈ T
be such that o(r(t)) = 0, r(t) ̸= r(q), and there exists no A ∈ T 0 \V with
r(t) ⊆ A. Then the principal ideal generated by [tt−1] is a proper ∗-ideal
of SΓ.
Proof. Let t, q ∈ T satisfy the stated hypotheses. As in the proof of
Lemma 19, the assumptions imply that |r(t)| = 1, and hence r(t) ∈ V .
Using the multiplication rule in SΓ together with the condition o(r(t))
= 0, the same argument as in Lemma 19 shows that non-zero products
involving [tt−1] arise only in the trivial prefix-comparable case. Conse-
quently, every non-zero element of S1
Γ[tt
−1]S1
Γ is of the form [αβ−1] with
α ∈ RP (Γ), β ∈ RLP (Γ) \ T 0, and r(α) = r(β) = r(t). Hence
S1
Γ[tt
−1]S1
Γ = {[αβ−1] : α ∈ RP (Γ), β ∈ RLP (Γ) \ T 0,
r(α) = r(β) = r(t)} ∪ {[0]}.
By Lemma 15(i), the set I is closed under L∗, and thus forms a ∗-ideal
of SΓ. To see that I is proper, observe that r(q) ̸= r(t), so [qq−1] /∈ I,
and hence I ̸= SΓ.
Lemma 21. Let Γ=(V, T, r, s) be a network with |T | > 1,and let t, q ∈ T
be such that o(r(t)) = 0, r(t) ̸= r(q), and there exists no A ∈ T 0 \V with
r(t) ⊆ A. Then the principal ideal RΓ[tt
−1]RΓ generated by [tt−1] is a
proper ideal of RΓ, where
RΓ[tt
−1]RΓ = {[αβ−1] : α, β ∈ RLP (Γ)\T 0, r(α) = r(β) = r(t)}∪{[0]}.
Y. H. Wang, P. Gao, X. M. Ren 333
Proof. The proof is analogous to that of Lemma 20, restricting to ele-
ments whose components lie inRLP (Γ)\T 0, and is therefore omitted.
Theorem 5. Let Γ = (V, T, r, s) be a network with |T | > 1, and suppose
that there exist t, q ∈ T such that o(r(t)) = 0, r(t) ̸= r(q), and there
exists no A ∈ T 0 \V with r(t) ⊆ A. Then SΓ is not ∗-congruence-free as
a unary semigroup, and RΓ is not congruence-free.
Proof. By Lemma 20, the semigroup SΓ admits a proper ∗-ideal I. Hence
the relation ρI = (I × I) ∪ 1SΓ
defines a non-trivial unary semigroup
congruence on SΓ, so SΓ is not ∗-congruence-free.
Similarly, by Lemma 21, the semigroup RΓ admits a proper ideal,
which induces a non-trivial congruence. Therefore RΓ is not congruence-
free.
4. Homomorphisms
In this section we investigate the relationship between network homo-
morphisms and semigroup homomorphisms.
Let S be a semigroup with set of idempotents E(S). The natural
partial order on S is defined by
a ≤ b ⇐⇒ a = xb = by and xa = a
for some x, y ∈ S1 (see [18]).
When restricted to E(S), the natural partial order takes the familiar
form: for all e, f ∈ E(S), we have e ≤ f if and only if e = ef = fe.
In particular, E(S) becomes a partially ordered set under ≤. Moreover,
if E(S) is a semilattice, then the order simplifies further, and for all
e, f ∈ E(S) we have
e ≤ f if and only if e = ef.
Lemma 22. Let E(QΓ) be the set of all idempotents of QΓ and let ≤ be
the natural partial order on QΓ. Then the following statements hold.
(i) An idempotent [αα−1] is maximal in E(QΓ) with respect to ≤ if
and only if α ∈ T 0.
(ii) An idempotent [αα−1] is maximal in E = E(QΓ) \ {[A] : A ∈ T 0}
with respect to ≤ if and only if α ∈ T .
334 Network semigroups
Proof. (i) Suppose that α ∈ T 0 and [αα−1] ≤ [µµ−1] for some µ ∈
RLP (Γ). Then [µµ−1] ̸= [0] and [αα−1] = [αα−1][µµ−1] = [µµ−1][αα−1].
Since α ∈ T 0, we have α−1 = α and hence [αα−1] = [α]. It follows that
[α] = [αµµ−1] = [µµ−1α]. If µ ∈ RLP (Γ) \ T 0, this is impossible. Hence
µ ∈ T 0, and the above equalities reduce to [α] = [αµ] = [µα], which
implies α = µ. Thus [αα−1] is maximal in E(QΓ).
Conversely, let α ∈ RLP (Γ) and suppose that [αα−1] is maximal
in E(QΓ). Then [αα−1] ̸= [0], and [αα−1] ≤ [s(α)], since [αα−1] =
[s(α)αα−1] = [αα−1s(α)]. By maximality, we obtain [αα−1] = [s(α)],
and hence α = s(α) ∈ T 0.
(ii) By Lemma 10, the set E = E(QΓ)\{[A] : A ∈ T 0} is a semilattice.
Let α ∈ T and suppose that [αα−1] ≤ [µµ−1] for some µ ∈ RLP (Γ) \
T 0. Then [µµ−1] ̸= [0] and [αα−1] = [αα−1][µµ−1]. By the proof of
Lemma 10, this implies that either α = µ or α = µx for some x ∈
RLP (Γ). Since α ∈ T and µ ∈ RLP (Γ) \ T 0, the latter possibility
cannot occur, and hence α = µ. Therefore [αα−1] is maximal in E.
Conversely, suppose that α ∈ RLP (Γ) \T 0 and [αα−1] is maximal in
E. Then [αα−1] ̸= [0]. Thus we may write α = tβ for some t ∈ T and
β ∈ RLP (Γ). By the proof of Lemma 10, we have [αα−1] ≤ [tt−1], and
since [tt−1] ∈ E, maximality yields [αα−1] = [tt−1]. As both αα−1 and
tt−1 are in right normal form, it follows that α = t ∈ T .
Theorem 6. Let Γ = (VΓ, TΓ, s, r) and ∆ = (V∆, T∆, s, r) be networks.
Then Γ ∼= ∆ if and only if QΓ
∼= Q∆.
Proof. It suffices to prove the non-trivial direction. Suppose that θ :
QΓ → Q∆ is a semigroup isomorphism. Let E(QΓ) and E(Q∆) denote
the sets of idempotents of QΓ and Q∆, respectively, and let ≤ denote the
natural partial order on each semigroup. Then θ restricts to an order-
isomorphism from (E(QΓ),≤) onto (E(Q∆),≤).
We first identify the vertices. By Lemma 22(i), the maximal elements
of E(QΓ) are precisely the idempotents of the form [A] with A ⊆ VΓ, and
analogously for Q∆. Hence θ induces a bijection
θ : {[A] : A ⊂ VΓ} −→ {[A′] : A′ ⊆ V∆}.
We claim that for each v ∈ VΓ, the element [v]θ corresponds to a singleton
vertex. Indeed, write [v]θ = [B] with B ⊆ V∆. If |B| > 1, choose distinct
u1, u2 ∈ B. Then [ui][B] ̸= [0] for i = 1, 2. By Lemma 22(i), there exist
A1, A2 ∈ T 0
Γ such that [Ai]θ = [ui]. It follows that
[Aiv]θ = [Ai]θ[v]θ = [ui][B] ̸= [0] (i = 1, 2),
Y. H. Wang, P. Gao, X. M. Ren 335
whence [Aiv] ̸= [0] and so v ∈ Ai for i = 1, 2. Thus A1 ∩ A2 ̸= ∅, and
hence [A1A2] ̸= [0]. However,
[A1A2]θ = [A1]θ[A2]θ = [u1][u2] = [0],
a contradiction. Therefore B is a singleton. Consequently, θ induces a
bijection
φ : VΓ → V∆, v 7→ v′ where [v]θ = [v′].
Next, we identify the relations. By Lemma 22(ii), the maximal ele-
ments of E(QΓ) \ {[A] : A ∈ T 0
Γ} are precisely the idempotents [tt−1]
with t ∈ TΓ, and similarly for ∆. Hence θ induces a bijection
θ : {[tt−1] : t ∈ TΓ} −→ {[qq−1] : q ∈ T∆}.
Let t ∈ TΓ and suppose that [tt−1]θ = [qq−1] for some q ∈ T∆. Write
[t]θ = [xy−1],
where xy−1 is in right normal form, that is, x ∈ RP (∆), y ∈ RLP (∆)
and r(x) = r(y).
We claim that x ∈ RLP (∆). Since θ is a semigroup isomorphism, [t]θ
is a regular element of Q∆ with inverse [t−1]θ. By Lemma 11, an element
of the form [xy−1] admits a (non-zero) inverse only if x ∈ RLP (∆).
If x ∈ RP (∆) \ RLP (∆), then [xy−1] has no non-zero inverse in Q∆,
which contradicts the fact that [t−1]θ is an inverse of [t]θ. Therefore
x ∈ RLP (∆), as required. Then by Lemma 12, [t−1]θ = [yx−1] ̸= [0],
and hence
[tt−1]θ = [t]θ[t−1]θ = [xy−1][yx−1] = [xx−1].
Thus [qq−1] = [xx−1], and so q = x. Moreover,
[r(t)]θ = [t−1t]θ = [yx−1xy−1] = [yy−1],
which implies that y ∈ T 0
∆ and hence y = r(y). Therefore
[t]θ = [xy−1] = [x] = [q].
It follows that θ induces a bijection
ψ : TΓ → T∆, t 7→ q where [t]θ = [q].
336 Network semigroups
Finally, we verify that φ and ψ preserve the source and range maps.
Let t ∈ TΓ. From the preceding computations we have
[r(t)]θ = [r([t]θ)] and [s(t)]θ = [s([t]θ)].
We now justify the description of [r(t)]θ. Clearly,
[r(t)]θ ⊆ {[v]θ : v ∈ r(t)}.
Conversely, let v ∈ r(t). Then [tv] ̸= [0], and since θ is a homomorphism,
it follows that [tv]θ ̸= [0]. Hence [v]θ ∈ r([t]θ), and therefore [v]θ ∈
[r(t)]θ. Thus
[r(t)]θ = {[v]θ : v ∈ r(t)}.
Combining this with the identity [r(t)]θ = [r([t]θ)], we obtain
[r(t)]θ = {[v]θ : v ∈ r(t)} = [r([t]θ)].
Since θ induces a bijection between {[v] : v ∈ VΓ} and {[v′] : v′ ∈ V∆},
it follows that
φ(r(t)) = r(ψ(t)) and φ(s(t)) = s(ψ(t)).
Therefore (φ,ψ) is an isomorphism of networks from Γ to ∆.
The converse implication is immediate, since any network isomor-
phism induces a semigroup isomorphism between the associated semi-
groups. This completes the proof.
Since the unary operation ∗ on QΓ is determined by the semigroup
structure, namely a∗ is the unique idempotent in the L∗-class of a, eve-
ry semigroup isomorphism between network semigroups automatically
preserves the ∗-operation. Therefore the isomorphisms considered in
Theorem 6 may equivalently be viewed as semigroup isomorphisms or as
∗-semigroup isomorphisms.
References
[1] Abrams, G., Aranda Pino, G.: The Leavitt path algebra of a graph. J. Algebra
293(2), 319–334 (2005). https://doi.org/10.1016/j.jalgebra.2005.07.028
[2] Abrams, G., Dokuchaev, M., Nam, T.G.: Realizing corners of Leavitt path algebras
as Steinberg algebras, with corresponding connections to graph C∗-algebras. J.
Algebra 593, 72–104 (2022). https://doi.org/10.1016/j.jalgebra.2021.11.004
https://doi.org/10.1016/j.jalgebra.2005.07.028
https://doi.org/10.1016/j.jalgebra.2021.11.004
Y. H. Wang, P. Gao, X. M. Ren 337
[3] Abrams, G., Nam, T.G.: Corners of Leavitt path algebras of finite graphs are
Leavitt path algebras. J. Algebra 547, 494–518 (2020). https://doi.org/10.1016/j.
jalgebra.2019.11.020
[4] Ara, P., Moreno, M.A., Pardo, E.: Nonstable K-theory for graph algebras. Al-
gebr. Represent. Theory 10(2), 157-178 (2007). https://doi.org/10.1007/s10468-
006-9044-z
[5] Ash, C.J., Hall, T.E.: Inverse semigroups on graphs. Semigroup Forum 11,
140–145 (1975). https://doi.org/10.1007/BF02195262
[6] Bianconi,G.: Higher-Order Networks.Cambridge University Press (2022). https://
doi.org/10.1017/9781108770996
[7] Battiston, F., Cencetti, G., Iacopini, I., Latora, V., Lucas, M., Patania, A., Young,
J.G., Petri, G.: Networks beyong pairwise interactions: Structure and dynamics.
Phys. Rep. 874, 1–92 (2020). https://doi.org/10.1016/j.physrep.2020.05.004
[8] Bick, C., Gross, E., Harrington, A.H., Schaub, T.M.: What are higher-order net-
works? SIAM Rev. 65(3), 686–731 (2023). https://doi.org/10.1137/21M1414024
[9] Bowers, P.M., Cokus, S.J., Eisenberg, D., et al. Use of logic relationships to de-
cipher protein network organization. Sci. 306(5705), 2246–2249 (2004). https://
doi.org/10.1126/science.1103330
[10] Book, R.V., Otto, F.: String-Rewriting Systems. In: String-Rewriting Systems.
Text and Monographs in Computer Science. Springer, New York, NY (1993).
https://doi.org/10.1007/978-1-4613-9771-7 3
[11] Fountain, J.B.: Adequate semigroups. Proc. Edinburgh Math. Soc. 22(2),113–125
(1979). https://doi.org/10.1017/S0013091500016230
[12] Fountain, J.B.: Abundant semigroups. Proc. Lond. Math. Soc. 44(s3), 103–129
(1982). https://doi.org/10.1112/plms/s3-44.1.103
[13] Fountain, J.B.: Free right h-adequate semigroups. In: Jürgensen, H., Lalle-
ment, G., Weinert, H.J. (eds) Semigroups Theory and Applications. Lecture
Notes in Mathematics, vol. 1320, 97–120. Springer, Berlin, Heidelberg (1988).
https://doi.org/10.1007/BFb0083424
[14] Hazrat, R., Nam, T.G.: Unital algebras being Morita equivalent to weighted Lea-
vitt path algebras. J. Algebr. Comb. 62, 28 (2025). https://doi.org/10.1007/s10801
-025-01454-y
[15] Howie, J.M.: An Introduction to Semigroup Theory. Academic Press, London
(1976).
[16] Klamt, S., Haus, U.-U., Theis, F.: Hypergraphs and cellular networks, PLoS
Comput. Biol.5(5), e1000385(2009). https://doi.org/10.1371/journal.pcbi.1000385
[17] Meakin, J., Milan, D., Wang, Z.P.: On a class of inverse semigroups related to
Leavitt path algebras. Adv. Math. 384, 107729 (2021). https://doi.org/10.1016/J.
AIM.2021.107729
[18] Mitsch, H.: A natural partial order for semigroups. Proc. Amer. Math. Soc. 97(3),
384–388 (1986). https://doi.org/10.1090/S0002-9939-1986-0840614-0
[19] Munn, W.D.: Fundamental inverse semigroups. Quart. J. Math. Oxford 21(2),
157–170 (1970). https://doi.org/10.1093/qmath/21.2.157
https://doi.org/10.1016/j.jalgebra.2019.11.020
https://doi.org/10.1016/j.jalgebra.2019.11.020
https://doi.org/10.1007/s10468-006-9044-z
https://doi.org/10.1007/s10468-006-9044-z
https://doi.org/10.1007/BF02195262
https://doi.org/10.1017/9781108770996
https://doi.org/10.1017/9781108770996
https://doi.org/10.1016/j.physrep.2020.05.004
https://doi.org/10.1137/21M1414024
https://doi.org/10.1126/science.1103330
https://doi.org/10.1126/science.1103330
https://doi.org/10.1007/978-1-4613-9771-7_3
https://doi.org/10.1017/S0013091500016230
https://doi.org/10.1112/plms/s3-44.1.103
https://doi.org/10.1007/BFb0083424
https://doi.org/10.1007/s10801-025-01454-y
https://doi.org/10.1007/s10801-025-01454-y
https://doi.org/10.1371/journal.pcbi.1000385
https://doi.org/10.1016/J.AIM.2021.107729
https://doi.org/10.1016/J.AIM.2021.107729
https://doi.org/10.1090/S0002-9939-1986-0840614-0
https://doi.org/10.1093/qmath/21.2.157
338 Network semigroups
[20] Nivat, M., Perrot, J.F.: Une generalisation du monoide bicclique. C. R. Acad.
Sci. Paris 271, 824–827 (1970).
[21] Paterson, A.L.T.: Graph inverse semigroups, groupoids and their C∗-algebras. J.
Operator Theory 48(3), 645–662 (2002). http://www.jstor.org/stable/24715591
[22] Wang, Y.H., Meng, D.Z.: Quasi-semilattices on networks. Axioms 12(10), 943
(2023). https://doi.org/10.3390/axioms12100943
[23] Yang, D., Gould, V.A.R.: Free idempotent generated semigroups over bands
and biordered sets with trivial products. Int. J. Algebra Comput. 26(3), 473–507
(2016). https://doi.org/10.1142/S021819671650020X
Contact information
Y. H. Wang,
P. Gao
College of Mathematics and Systems Science,
Shandong University of Science and Technology,
Qingdao 266590 China
E-Mail: yanhuiwang@sdust.edu.cn,
gaopei0403@163.com
X. M. Ren Department of Mathematics, Xi’an University
of Architecture and Technology, Xi’an 710055
China
E-Mail: xmren@xauat.edu.cn
Received by the editors: 19.04.2026
and in final form 13.06.2026.
http://www.jstor.org/stable/24715591
https://doi.org/10.3390/axioms12100943
https://doi.org/10.1142/S021819671650020X
Yanhui H. Wang, Pei Gao, and Xueming M. Ren
|
| id | admjournalluguniveduua-article-2486 |
| institution | Algebra and Discrete Mathematics |
| keywords_txt_mv | keywords |
| language | English |
| last_indexed | 2026-07-09T01:00:10Z |
| publishDate | 2026 |
| publisher | Lugansk National Taras Shevchenko University |
| record_format | ojs |
| resource_txt_mv | admjournalluguniveduua/36/036554f2f2736c62623dcdc26da66c36.pdf |
| spelling | admjournalluguniveduua-article-24862026-07-08T07:55:33Z Network semigroups Wang, Yanhui H. Gao, Pei Ren, Xueming M. network right \(*\)-abundant semigroups, networks, graph inverse semigroups 20M10 We introduce the class of network semigroups. These are based on networks that extend the notion of a directed graph. This class properly contains the class of graph inverse semigroups. We investigate the structure of network semigroups. We show that two network semigroups are isomorphic if and only if the underlying networks are isomorphic. Lugansk National Taras Shevchenko University Natural Science Foundation of China (Grant No: 11501331) 2026-07-08 Article Article Peer-reviewed Article application/pdf https://admjournal.luguniv.edu.ua/index.php/adm/article/view/2486 10.12958/adm2486 Algebra and Discrete Mathematics; Vol 41, No 2 (2026) 2415-721X 1726-3255 en https://admjournal.luguniv.edu.ua/index.php/adm/article/view/2486/pdf Copyright (c) 2026 Algebra and Discrete Mathematics |
| spellingShingle | network right \(*\)-abundant semigroups networks graph inverse semigroups 20M10 Wang, Yanhui H. Gao, Pei Ren, Xueming M. Network semigroups |
| title | Network semigroups |
| title_full | Network semigroups |
| title_fullStr | Network semigroups |
| title_full_unstemmed | Network semigroups |
| title_short | Network semigroups |
| title_sort | network semigroups |
| topic | network right \(*\)-abundant semigroups networks graph inverse semigroups 20M10 |
| topic_facet | network right \(*\)-abundant semigroups networks graph inverse semigroups 20M10 |
| url | https://admjournal.luguniv.edu.ua/index.php/adm/article/view/2486 |
| work_keys_str_mv | AT wangyanhuih networksemigroups AT gaopei networksemigroups AT renxuemingm networksemigroups |