Classification of inverse semigroups generated by two-state partially defined invertible automata over the two-symbol alphabet
The classification of inverse semigroups generated by two-state partially defined invertible automata over a twosymbol alphabet is investigated. Two presentations of such semigroups are given. The structures of these semigroups are analyzed.
Saved in:
| Published in: | Algebra and Discrete Mathematics |
|---|---|
| Date: | 2006 |
| Main Author: | |
| Format: | Article |
| Language: | English |
| Published: |
Інститут прикладної математики і механіки НАН України
2006
|
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/157367 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Classification of inverse semigroups generated by two-state partially defined invertible automata over the two-symbol alphabet / J.K. Slupik // Algebra and Discrete Mathematics. — 2006. — Vol. 5, № 1. — С. 67–80. — Бібліогр.: 7 назв. — англ. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859471930738868224 |
|---|---|
| author | Slupik, J.K. |
| author_facet | Slupik, J.K. |
| citation_txt | Classification of inverse semigroups generated by two-state partially defined invertible automata over the two-symbol alphabet / J.K. Slupik // Algebra and Discrete Mathematics. — 2006. — Vol. 5, № 1. — С. 67–80. — Бібліогр.: 7 назв. — англ. |
| collection | DSpace DC |
| container_title | Algebra and Discrete Mathematics |
| description | The classification of inverse semigroups generated by two-state partially defined invertible automata over a twosymbol alphabet is investigated. Two presentations of such semigroups are given. The structures of these semigroups are analyzed.
|
| first_indexed | 2025-11-24T10:31:03Z |
| format | Article |
| fulltext |
Algebra and Discrete Mathematics RESEARCH ARTICLE
Number 1. (2006). pp. 67 – 80
c© Journal “Algebra and Discrete Mathematics”
Classification of inverse semigroups generated by
two-state partially defined invertible automata
over the two-symbol alphabet
Janusz Konrad Slupik
Communicated by V. I. Sushchansky
Abstract. The classification of inverse semigroups gener-
ated by two-state partially defined invertible automata over a two-
symbol alphabet is investigated. Two presentations of such semi-
groups are given. The structures of these semigroups are analyzed.
Introduction
The problem of classification of (semi)groups generated by Mealy au-
tomata have been actively investigated for the last few years. It seems
natural to study (semi)groups defined by finite automata with small pa-
rameters (numbers of states and symbols in the alphabet). R. I. Grigor-
chuk proved that there exist 6 pairwise nonisomorphic groups generated
by two-state invertible Mealy automata over a two-symbol alphabet (fi-
nite groups: the trivial group, the cyclic group of order two and the
Klein four-group; infinite groups: the infinite cyclic group, the infinite
dihedral group and the lamplighter group, see [2]). I. I. Reznykov and
V. I. Sushchansky proved that there are 29 pairwise nonisomorphic semi-
groups and six aforementioned groups generated by fully defined two-state
automata over a two-symbol alphabet (see [3]).
In paper [4], we started to investigate inverse semigroups generated
by two-state partially defined invertible automata over a two-symbol al-
2000 Mathematics Subject Classification: 20M18; 20M35, 68Q35.
Key words and phrases: inverse semigroup, Mealy automata,partially defined
Mealy automata, automaton transformations.
68 Inverse Semigroups
phabet. Namely, we proved that such semigroups are finite. The aim of
this paper is to give a full classification of these inverse semigroups.
Let us denote the set of all partially defined invertible Mealy automata
with m states over some n-symbol alphabet by IPMA(m, n).
The computer counting was applied to investigate isomorphisms of
inverse semigroups generated by automata from IPMA(2, 2). The cal-
culation was made in Institute of Mathematics of Silesian University of
Technology. The following results were obtained.
Theorem 1. Let S be an inverse semigroup defined by some automaton
from IMPA(2, 2). Then |S| is a number from the set
M = [1, 16] ∪ [18, 20] ∪ [23, 26]∪
∪{28, 30, 32, 36, 39, 43, 52, 59, 89, 149, 357, 388} .
For every number m ∈ M there exists an automaton A ∈ IPMA(2, 2)
such that |SA| = m.
Theorem 2. There exist 59 pairwise nonisomorphic inverse semigroups
generated by automata from IPMA(2, 2).
The complete list of these 59 inverse semigroups is given in the last
section of the paper. We give two descriptions of such semigroups: as
subsemigroups of symmetric inverse semigroups, and as presentation with
generators and determining relations. We present some structural aspects
of such semigroups, which are expressed in theorem 3.
1. Preliminaries
The standard terminology and notations from the theory of inverse semi-
groups (see [5, 6, 7]) is used.
Let X be a nonempty finite set (an alphabet) and let X∗ be the free
monoid over X. Its subsemigroup consisting of all nonempty words is
denoted by X+. If ω = x1x2...xn ∈ X∗, then |ω| = n is the length of the
word ω. The length of the empty word is equal to zero. We denote the
domain of any partial transformation f by the symbol dom(f) and the
image of f we denote by im(f).
Let A = 〈X, Q, π, λ〉 be a Mealy automaton, where X is the alphabet
of input and output symbols (|X| < ∞), Q is the set of internal states
(not necesserly finite), π : X × Q → Q and λ : X × Q → X are its
transition and output functions respectively.
J. K. Slupik 69
Definition 1. The automaton A = 〈X, Q, π, λ〉 is called a partially de-
fined automaton if its transition function π or output function λ are par-
tially defined, i.e.
dom(π) ∩ dom(λ) 6= X × Q .
Hence, the set of patially defined automata and the set of fully defined
automata are disjoint.
Each state q ∈ Q of a Mealy automaton determines a certain partial
transformation λq : X → X defined by the formula λq(x) = λ(x, q).
The automaton A with a fixed (initial) state q ∈ Q is called an initial
automaton and is denoted by (A, q).
Definition 2. An automaton A is called invertible if λq is a partial
permutation on X for every q ∈ Q.
Let A = 〈X, Q, π, λ〉 be an invertible partially defined automaton.
Let A′ = 〈X, Q, π′, λ′〉 be a partially defined automaton such that the
following conditions hold
i) λ′
q(x) = λ−1
q (x) for every q ∈ Q,
ii) if (λ−1
q (x), q) ∈ dom(π), then π′(x, q) = π(λ−1
q (x), q)
otherwise (x, q) 6∈ dom(π′).
Definition 3. The automaton A′ is called an inverse automaton to A.
The functions π and λ can be naturally extended to mappings π̄, λ̄ of
subsets of the X∗×Q into the sets Q and X∗ by the following equalities:
π̄(e, q) = q, π̄(ωx, q) = π(x, π̄(ω, q)),
λ̄(e, q) = e, λ̄(ωx, q) = λ̄(ω, q)λ(x, π̄(ω, q)),
where e is the empty word, q ∈ Q, ω ∈ X∗, x ∈ X. Moreover, if
(ω, q) /∈ dom λ̄ then (ωx, q) /∈ dom λ̄.
Now, let us introduce the partial transformation fA,q : X∗ → X∗
determined by the partially defined automaton A at the state q ∈ Q in
the following way
fA,q(u) = λ̄(u, q),
where u ∈ X∗.
Definition 4. A partial transformation f : X∗ → X∗ is called
an automaton transformation if there exists a finite automaton
A = 〈X, Q, π, λ〉 and a state q ∈ Q such that f = fA,q.
70 Inverse Semigroups
The partially defined Mealy automaton A with the set of states Q
defines the set of partial transformations TA = {fA,q ; q ∈ Q} on the set
X∗.
Definition 5. The semigroup SA = 〈TA〉 is called the semigroup of par-
tial transformations which is defined by the automaton A with the set of
internal states Q.
If A is an invertible partially defined automaton, then for every q ∈ Q
the transformation fA,q is a partial permutation over X∗. In this case we
denote by SA the inverse semigroup generated by such automaton, i.e.
SA =
〈
fA,q, f
−1
A,q ; q ∈ Q
〉
.
Now, let us adduce very useful properties of automaton transforma-
tions.
Lemma 1. Let f : X∗ → X∗ be a partial transformation. The automaton
transformation f holds
a) f preserves the lengths of words, i.e. if ω ∈ dom(f) then |f(ω)| = |ω|,
b) f preserves the beginnings of words, i.e. if f(u) = u′ then f(uv) = u′v′
for v ∈ X∗ such that uv ∈ dom(f),
c) if u 6∈ dom(f), then ux 6∈ dom(f) for every x ∈ X.
Let A1 = 〈X, Q1, π1, λ1〉 and A2 = 〈X, Q2, π2, λ2〉 be two automata.
Let us construct a new automaton B = A1 ∗A2 with the set of states
Q1 ×Q2 and the transition function π and the output function λ defined
by the equalities, respectively
π(x, (q1, q2)) =
(
π1(x, q1), π2(λ1(x, q1), q2)
)
,
λ(x, (q1, q2)) = λ2
(
λ1(x, q1), q2)
)
.
The automaton B is called the composition of automata A1 and A2. If we
consider initial automata (A1, q
0
1) and (A2, q
0
2), then B is the automaton
with the initial state (q0
1, q
0
2).
It is clear that, if ω ∈ X∗ is a word such that ω ∈ dom
(
f(A1,q0
1
)
)
and
f(A1,q0
1
)(ω) ∈ dom
(
f(A2,q0
2
)
)
, then
f(A1∗A2,(q0
1
,q0
2
))(ω) = f(A2,q0
2
)(f(A1,q0
1
)
(
ω)
)
.
Hence, the superposition of partial automaton transformations is a
partial automaton transformation.
J. K. Slupik 71
Definition 6. Two initial automata (A1, q1) and (A2, q2) are called
equivalent if they define the same partial transformations, i.e. f(A1,q1) =
f(A2,q2).
There exist well known algorithms that determine whether or not two
given finite automata are equivalent. One of the basis facts in the theory
of finite automata is the existence of a unique automaton in the class
of equivalent automata that has the minimal number of states, so called
the minimal automaton. The procedure of determination of minimal
automaton for (A, q) is called the reduction of (A, q). Let us denote the
result of this procedure by red
(
(A, q)
)
.
In the sequel of this section we recall the essential definitions.
Let S be an inverse semigroup. We will denote by L, R, H and D
Green’s relations on S. Let E(S) denote the set of all idempotents of a
semigroup S.
Definition 7. An inverse semigroup S is called a Clifford semigroup if
for every s ∈ S ss−1 = s−1s.
It is equivalent that every H-class of the inverse semigroup S is a
group.
Definition 8. An inverse semigroup S is said to be E-reflexive if for
every s, t ∈ S
st ∈ E(S) ⇔ ts ∈ E(S) .
Definition 9. An inverse semigroup S (without zero) having a single D-
class is said to be bisimple. An inverse semigroup with zero S is called
0-bisimple if it contains two D-classes.
2. Algorithms
The set of all two-state partially defined Mealy automata over the two-
symbol alphabet has 6305 elements. The set IPMA(2, 2) of all partially
defined invertible Mealy automata with 2 states over 2-symbol alpha-
bet has 3905 elements. We introduce an equivalence relation on the set
IPMA(2, 2) by setting two automata to be equivalent if they can be ob-
tained from each other by permutations of the states or letters of the
alphabet.
Let A ∈ IPMA(2, 2) and λ, π are its output and transition functions
respectively. If (x, q) 6∈ dom(λ) for certain x ∈ X and q ∈ Q, then fA,q
does not depend on value π(x, q). Hence, we can add to the equivalence
relation pairs of automata which differ in this way.
72 Inverse Semigroups
Straightforward calculation shows that IPMA(2, 2) divides into 209
classes of equivalence. It is enough to investigate representative automata
from each class.
Of course, with an enormous machine calculations of this nature, one
inevitably asks how far the result can be trusted, and whether it is likely
that a small logical or other error in the code could have resulted in an
incorrect final result. This is extremely unlikely in this case, for the fol-
lowing reason. All of the calculations have been made by two completely
different versions of the program and yielded the same results.
The algorithm 1 was used to investigate the orders of inverse semi-
groups generated by automata from IPMA(2, 2).
Algorithm 1.
1. Input: Given an automaton A from IPMA(2, 2).
2. Let L be a list of elements of SA. Now, let L = ∅. Setting
M = {(A, q0), (A, q1), (A
−1, q0), (A
−1, q1)}.
3. Reduction of elements from M and adding different one to L.
4. n := |L|
5. For every automaton (B, s) ∈ L and (C, q) ∈ M , the following
superpositions are callculated (D, s′) = (B, s) ∗ (C, q) .
Next:
5.1. The reduction of the automaton (D, s′),
5.2. If {red
(
(D, s′)
)
} ∩ L = ∅, then red
(
(D, s′)
)
is added to L.
6. After step 5 if |L| = n, then the algorithm stops and returns:
the list L and the number n. Otherwise go to 4.
7. Ouput: |SA| and the list L of different elements of SA,
(each element of SA is represented by some minimal initial
automaton from L).
Algorithm 2.
1. Input: Given the list L of different elements of SA.
(L contains inital automata)
2. The Cayley table is made according to multiplication defined
by the rule: for each (A, q) and (B, q′) from L,
(A, q) ◦ (B, q′) = red ((A, q) ∗ (B, q′))
3. Ouput: the Cayley table TA.
J. K. Slupik 73
Algorithm 3.
1. Input: Given Cayley tables TA and TB.
2. For every element from SA and SB the frequency of appearance
in the table is counted. Making the lists of all frequences L(SA)
and L(SB).
3. Ordering the lists L(SA), L(SB) and replacing elements in TA
and TB according to the lists.
4. If L(SA) has different elements than L(SB), then the semigroups
are not isomorphic and the algorithm stops.
Otherwise:
4.1. Permuting elements from L(SA) which have the same fre-
quency.
4.2. Enumerating the table TA according to such permutation.
4.3. Compering the tables: TA and TB. If the tables are the
same, then the semigroups are isomorphic and the algorithm stops.
5. If for every possible permutation described in point 4.1. the
Cayley tables are different, then the semigroups are not isomorphic.
The algorithm stops.
6. Ouput: the answer ’isomorphic’ or ’nonisomorphic’.
Algorithm 4.
1. Input: Given the Cayley table TA.
2. According to the Wagner-Preston theorem, partial permutations
are made.
3. Output: two partial permutations.
Algorithm 5.
1. Input: Given the Cayley table TA.
2. Let n be a dimension of the table TA.
For arbitrary element s ∈ SA, we denote by w(s) element
s rewritten as a product of generators.
3. We construct n2 relations by the rule:
if a ◦ b = c where a, b, c are elements of TA,
then we have a relation w(a)w(b) = w(c).
4. We apply preliminary reduction according to patterns:
- relations uu−1u = u are deleted,
- if u = v, then relation u−1 = v−1 is deleted,
- if uu = u, then relation u = u−1 is deleted,
- if u = v, then relations aub = avb are deleted,
where u, v, a, b are words in the alphabet consisted of generators.
5. Output: the set of relations.
74 Inverse Semigroups
The isomorphism test (i.e. whether or not two given inverse semi-
groups defined by Cayley tables are isomorphic), is complex. The analysis
of n element semigroup gives rise to checking n! permutations of rows and
columns of Cayley tables. In the case of inverse semigroups generated by
automata from IPMA(2, 2), the algorithm 3 was proposed to solve that
problem.
3. Results of calculations
Our investigations can be briefly described in the following way. First,
for every automaton A ∈ IPMA(2, 2) a list of elements in SA is made by
the algorithm 1. Next for each inverse semigroup SA the Cayley table is
made by the algorithm 2. Then, we use the algorithm 3, which generates
a list of non isomorphic inverse semigroup. Next, the algorithm 4 is used
and the charts presentations are made. The reduction of the lengths of
partial permutations is made manually. Finally, we use the algorithm 5,
which made lists of relations. The presentations with generator sets and
relations are made by manual reduction from obtained lists of relations.
We use the following symbols: n - serial number, o - order of a semi-
group, z - zero, i - the identity, e - number of idempotents in a semigroup.
n o z i e
1 1 0 1 1
2 2 _ 1 1
3 2 0 1 2
4 3 0 1 2
5 3 0 _ 3
6 3 _ 1 2
7 4 _ 1 2
8 4 _ 1 2
9 5 0 _ 3
10 6 0 _ 4
11 6 0 1 4
12 6 _ _ 3
13 7 0 _ 4
14 7 0 1 4
15 7 _ 1 4
16 8 0 _ 5
17 8 _ _ 4
18 8 _ 1 4
19 9 0 _ 5
20 9 0 _ 5
n o z i e
21 10 0 _ 6
22 10 0 _ 6
23 10 0 _ 6
24 10 0 _ 6
25 10 _ _ 4
26 11 0 _ 6
27 11 0 _ 6
28 11 0 1 4
29 12 _ _ 6
30 12 _ 1 4
31 13 0 _ 7
32 14 0 _ 6
33 14 _ _ 7
34 15 0 _ 8
35 16 _ _ 8
36 18 0 _ 8
37 19 0 _ 10
38 19 0 _ 9
39 19 _ _ 6
40 20 _ _ 10
n o z i e
41 23 0 _ 11
42 23 0 _ 12
43 23 _ _ 8
44 24 _ _ 12
45 25 _ _ 9
46 26 0 _ 10
47 28 0 _ 11
48 30 0 _ 12
49 32 _ _ 10
50 36 0 _ 13
51 36 _ _ 12
52 39 0 _ 17
53 43 0 _ 17
54 52 0 _ 17
55 59 _ _ 17
56 89 0 _ 27
57 149 _ _ 27
58 357 0 _ 66
59 388 _ _ 66
J. K. Slupik 75
Our notation is slightly different from that of [6]. We will write every
cycle of the length one and we will omit paths of the length one. This
convention gives us shorter chart decompositions of generators.
According to the above numeration of inverse semigroups, the follow-
ing presentations are written:
n charts
1 f = 0 g = 0
2 f = (1, 2) g = (1, 2)
3 f = (1) g = 0
4 f = (1, 2) g = 0
5 f = (1) g = (2)
6 f = (1)(2)(3) g = (2, 3)
7 f = (1, 3)(2)(4) g = (2, 4)
8 f = (1, 3)(2, 4) g = (2, 4)
9 f = (2, 1] g = 0
10 f = (1)(2) g = (3, 2]
11 f = (1)(2)(3) g = (3, 2]
12 f = (4, 1](2, 3) g = (2, 3)
13 f = (3, 1](2, 4) g = 0
14 f = (1, 3)(2, 4) g = (2)
15 f = (1)(2)(3)(4) g = (3, 1](2, 4)
16 f = (1, 3)(4, 5) g = (2)(5)
17 f = (5, 1](2, 4)(3, 6) g = (2, 4)
18 f = (1, 3)(2, 4)(5, 6) g = (2)(5)(6)
19 f = (3, 1](4, 2] g = (2)
20 f = (1, 3)(4, 6) g = (2, 5)(6)
21 f = (4, 1](2)(3) g = (5, 2]
22 f = (3, 1](2)(4) g = (4, 2]
23 f = (2)(4) g = (3, 1](4, 2]
24 f = (1)(2)(4) g = (3, 1](2, 4]
25 f = (5, 1](2, 4)(3, 6, 8, 7) g = (2)(4)
26 f = (5, 1](2, 4)(3, 6) g = (2)
27 f = (1, 3)(4, 6) g = (5, 2](4, 6]
28 f = (1, 3)(2, 4)(5, 6) g = (2, 5)
29 f = (5, 1](2, 4)(3, 7)(6, 8) g = (4, 2](6, 8)
30 f = (1, 3)(2, 4)(5, 6)(7, 8) g = (2, 5)(7)(8)
31 f = (4, 1](6, 3] g = (5, 2](3, 6]
32 f = (5, 1](2, 4](6, 7] g = (8, 1](3, 4](7)
33 f = (5, 1](3, 7)(8, 4] g = (6, 2](3, 7)(4, 8]
76 Inverse Semigroups
34 f = (5, 1](6, 2](3, 7)(4, 8) g = (6, 2](4, 8]
35 f = (5, 1](6, 2](3, 8)(4, 9)(7, 10) g = (6, 2](4, 9](7, 10)
36 f = (1, 3)(4, 6)(7, 10)(8, 11) g = (2, 5)(6, 12)(9, 11)(10)
37 f = (6, 1](3, 8)(4, 9)(10, 5] g = (7, 2](4, 9](10, 5]
38 f = (3, 1](6, 2](4)(5)(7)(8) g = (7, 2](8, 5]
39 f = (1, 4](3, 10)(6)(8) g = (2, 4](12, 3](6, 8)(9, 10]
40 f = (6, 1](3, 4](5, 10)(7, 9) g = (8, 2](4, 3](10, 5](7, 9)
41 f = (7, 1](8, 2](3)(4)(5)(6) g = (10, 2](9, 5](6, 3]
42 f = (1, 4](2, 5](6, 3) g = (4, 1](2, 5](3, 6]
43 f = (6, 4)(11, 7)(3, 10)(9, 1) g = (2, 5)(8, 6)(10)(1, 11)(3)
44 f = (12, 1](6, 4](3, 5](11, 7)(9, 10)
g = (8, 2](4, 6](3, 5](11, 7)(9, 10]
45 f = (1)(2)(3, 4)(5)(6)(8, 9](7) g = (1, 2)(3, 6](4, 5](8, 7]
46 f = (7, 2](3, 5](4)(1, 8](9, 10](6) g = (9, 2](3, 8](6, 4]
47 f = (7, 2](13, 4)(6, 5)(8, 1](17, 10](9, 11]
g = (12, 2](3, 11](1, 10)(6)
48 f = (1)(2)(3, 4](5, 6] g = (1, 2](3, 5](4, 6]
49 f = (8, 2](6, 5)(9)(1, 3](4, 10)(7) g = (1, 2](10, 5](7, 9)(4, 6]
50 f = (1, 2)(3, 4, 5, 6] g = (1)
51 f = (6, 5](1)(4)(10, 9)(3, 2](7, 8) g = (5, 2](1, 4)(8, 9](6, 3](7, 10]
52 f = (1, 4)(6, 3](7, 5](9, 10] g = (1)(2, 3](8, 5)(10)
53 f = (2, 4](5)(11, 1](10)(8) g = (7, 4](5, 8](9, 10](6, 1](3, 2]
54 f = (1, 2)(4, 5, 3, 6] g = (1)(3)
55 f = (5, 3, 1, 2](7, 9, 8, 4)(6, 10) g = (1)(4)(6)(9)(10)
56 f = (1)(2)(3)(4)(5, 6](7)(8)(9, 10](11, 13]
(12, 14](15, 16](20, 18](19, 21]
g = (1, 2](3, 5](4, 6](7, 11](8, 12](9, 14](15, 17](20, 21]
57 f = (1)(2)(3, 4)(5)(6)(7, 9](8, 10](11, 12)(13)(14)(15, 20](16, 19]
(17, 22](23, 25](24, 26](27, 28)(30)(18, 21](29, 31]
g = (1, 2)(3, 5](4, 6](7, 12](8, 11](9, 13](10, 14](15, 25](16, 26]
(19, 28](20, 27](22, 30](21, 31]
58 f = (1, 2)(4, 5, 3, 6](12, 7, 14](9, 11, 8, 13]
(16, 29](25, 15, 30](20, 23, 18](19, 24, 17, 27]
g = (1)(3, 4)(8, 9, 7, 10](17, 19, 16, 21](20, 15, 22]
59 f = (1, 2)(3, 5, 4, 6)(13, 8, 11, 9](14, 7, 12, 10](16, 15, 17]
(19, 18, 21, 20](25, 24, 26](32, 31, 33, 30](37, 38, 27](39, 29]
g = (1)(2)(3, 4)(7, 9, 8, 10)(22, 15, 20, 18](23, 24, 27](28, 29, 30, 31]
J. K. Slupik 77
Now, we have the following presentations with generators and rela-
tions.
n presentation
1 〈f, g; f = g = 0〉
2 〈f, g; f = g, f2 = 0〉
3 〈f, g; f = 1, g = 0〉
4 〈f, g; f2 = 1, g = 0〉
5 〈f, g; f = f2, g = g2, fg = 0〉
6 〈f, g; f = 1, g = g3〉
7 〈f, g; f2 = 1, g = g−1, fg = g〉
8 〈f, g; f2 = 1, g = g−1, gf = fg = g2〉
9 〈f, g; f2 = 0, g = 0〉
10 〈f, g; f2 = f, gf = 0, fg = g〉
11 〈f, g; f = 1, g2 = 0〉
12 〈f, g; f2 = f4, g = f3〉
13 〈f, g; f2 = f4, g = 0〉
14 〈f, g; f2 = 1, g2 = g, gfg = 0〉
15 〈f, g; f = 1, g2 = g4〉
16 〈f, g; f = f−1, g2 = g, gfg = 0, gf2 = f2g〉
17 〈f, g; f2 = f4, g = g−1, g = gf2, gf = fg = g2〉
18 〈f, g; f2 = 1, g = g2, gfgf = fgfg〉
19 〈f, g; f2 = 0 = fg, g = g2, ff−1g = g〉
20 〈f, g; f = f−1, g = g−1, gfg = 0, gf2 = f2g, fg = fg2〉
21 〈f, g; f2 = f3, g = fg = f−1g, fg−1 = gf = 0〉
22 〈f, g; f2 = f3, g2 = 0, fg = gf = g = f−1g = gf−1〉
23 〈f, g; f = f2, g2 = 0, fg = gf〉
24 〈f, g; f = f2, g2 = 0, fg = g〉
25 〈f, g; f2 = f−2, g = g2, gf = fg = f−1g, gf2 = g〉
26 〈f, g; f2 = f4, g = g2 = gf2, gfg = 0, fg = f−1g〉
27 〈f, g; f = f−1, g2 = 0, gf = fg−1, fg = g−1f, gf2 = gfg〉
28 〈f, g; f2 = 1, g = g−1, gfg = 0〉
29 〈f, g; f2 = f4, g2 = g4, gf = gf−1 = gg−1, fg = f−1g = g−1g〉
30 〈f, g; f2 = 1, g = g−1, fgfg = gfgf, gfg = g2fg = gfg2〉
31 〈f, g; f2 = g2 = 0 = fg−1 = f−1g, (gf)2 = gf, (fg)2 = fg〉
32 〈f, g; f2 = 0 = fg = fg−1, g2 = g3, gg−1 = ff−1, gf = g−1gf〉
33 〈f, g; f2 = f4 = g2 = fg−1 = g−1f, gff−1 = gfg,
gf−1f = gf2 = f2g, fg = g−1f−1〉
34 〈f, g; f2 = f4, g2 = 0, g = gf−1f = ff−1g, gf−1 = gg−1,
gff−1 = f−1fg = gf2 = gfg = f2g〉
35 〈f, g; f2 = f4, g2 = g4, g = gf−1f = ff−1g, gf−1 = gg−1
g−1g = f−1g, gfg = gff−1 = f−1fg〉
78 Inverse Semigroups
36 〈f, g; f = f−1, g = g−1, gfg = 0, f2g2 = g2f2, fgf2 = fgf2g〉
37 〈f, g; f2 = f4, g2 = 0, gff−1 = gf2 = gfg = f2g = f−1fg,
ff−1g = gf−1g = gf−1f〉
38 〈f, g; f2 = f3, g2 = 0, g = gf = gf−1, fg = f2g = gg−1fg〉
39 〈f, g; f2 = f4, g2 = g4, gg−1 = ff−1, gfg = gfgf = fg2,
gf = gf2 = gf−1 = fgf = f−1g−1〉
40 〈f, g; f2 = f4, g2 = g4, gfg = gff−1 = f−1fg,
gf2 = gf−1f = ff−1g = gf−1g, g3 = fg2 = g2f〉
41 〈f, g; f2 = f3, g2 = 0 = gfg, gf = gf−1 = gf2 = fgf,
g = ff−1g, fg−1 = fg−1f, fg−1g = g−1gf,
fgg−1 = gg−1f−1 = fgg−1f〉
42 〈f, g; f2 = f4, g2 = 0, gf−1g = gf−1f = ff−1g,
gfg = f−1fg = gff−1〉
43 〈f, g; f = f−1, g = g−1, g2f2 = f2g2, fgfg = gfgf,
gfg2 = gfg = f2gfg, gf2gf2 = f2gf2g〉
44 〈f, g; f2 = f4, g2 = g4, gf2 = f2g, gfg = gff−1 = f−1fg,
gf−1g = gg−1f = gf−1f = ff−1g, g3 = g2f = fg2〉
45 〈f, g; f2 = f4, g2 = g4, g = gf = gf−1 = ff−1g, f−1fg = f2g,
fgg−1 = gg−1f−1, g−1f−1g = g−1fg〉
46 〈f, g; f2 = f3, g2 = 0 = gf−1g, gf = fg = gff−1 = f−1fg,
g = gf−1f = ff−1g, gg−1f−1 = fgg−1, g−1gf = f−1g−1g〉
47 〈f, g; f2 = f4, g2 = g4, gfg = 0 = gf−1g, g = ff−1g,
f−1fg = gf−1f = gf2 = f2g〉
48 〈f, g; f2 = f3, g2 = 0, gf = fg, gf−1 = f−1g〉
49 〈f, g; f2 = f4, g2 = g4, gf = fg, g = gf−1f = ff−1g〉
50 〈f, g; f4 = f6, g = g2 = gf2 = f2g = gff−1 = gf−1f, gfg = 0〉
51 〈f, g; f2 = f4, g2 = g4, gf = fg, gf−1 = f−1g, gf2 = f2g〉
52 〈f, g; f2 = f4, g2 = g4, gfg = gf−1g = 0, fg−1 = fg,
gf2 = f2g = gf−1f = f−1fg〉
53 〈f, g; f2 = f3, g2 = 0 = gfg, g−1gf = fg−1g,
gf = gf−1 = gf2 = fgf〉
54 〈f, g; f4 = f6, g = g2 = gff−1 = gf−1f, gfg = 0,
f2g = gf−2 = gf4, gf3 = gf−3 = gf5, gf = gf2f−1〉
55 〈f, g; f4 = f8, g = g2 = gff−1 = f−1fg = gf2f−2,
gfg = gf−1g, gf4 = f4g = f2gf2 = gf−2f2, gfgf = fgfg〉
56 〈f, g; f2 = f3, g2 = 0 = gfg = gf−1g, g = gf−1f,
fg = fgf = fgf−1, f−1gf = gg−1f−1gf〉
57 〈f, g; f2 = f4, g2 = g4 = g2f = gfg = gf−1g = gf2g = fg2,
fgf−1 = fgf, g = gf−1f, gf = gf3, f2g = f2gf,
gfg−1 = gf−1g−1, g−1gf = f−1g−1g, fgg−1f = f2gg−1〉
J. K. Slupik 79
58∗ 〈f, g; f4 = f6, g4 = g6, gfg = 0 = gf−1g = gfg−1 = g−1fg,
gf3g = 0 = gf−3g, gf3 = g−1f3 = gf5 = f2g2f,
g = gf−1f, gf4 = gf4g = f4g, (f−1gf)2 = f−1gf = f2f−1gf,
(g−1f2)2 = g−1f2, g−1g2 = f−1fg, f−2fg = f−1g,
(gf2)2 = gf2, (f2g)2 = f2g, ...〉
59∗ 〈f, g; f4 = f8, g4 = g8, (gf2)2 = gf2, (f2g)2 = f2g,
gfg = gf−1g = gfg−1 = g−1fg = gf3g = gf−3g,
gfg = gfg2 = g−1f−1g−1, g−1f2 = f−2g, f−1fg = g−1g2,
gfgf = fgfg, gf4 = f4g = f4g−1, gf3 = g−1f3,
g = gf−1f, f−1gf = f−1g−1f, gf5 = ff−1gf = f2g2f,
g−1f−1f2 = g−1f, (f−1gf)2 = f2f−1gf, ...〉
( * - these two presentations may have not enough relations)
According to the above numeration of semigroups, we can formulate
the following theorem:
Theorem 3. Let S be an inverse semigroup generated by an automaton
from IPMA(2, 2).
a) S is a Clifford semigroup if, and only if S have a number from
1÷8,
b) S is bisimple if, and only if S have a number 1 or 2,
c) S is 0-bisimple if, and only if S have a number 3, 4 or 9,
d) S is E-reflexive if, and only if S have a number 1÷8, 12, 13, 15,
17,18, 25, 29, 30, 33, 35, 39, 40, 44, 45, 49, 51, 55, 57, 59.
References
[1] C. K. Gupta, V. I. Sushchansky, Semigroups of Automatic Transformations, in:
Topics in Infinite Groups, Quaderni di Matematica, 8 Aracne, Napoli 2001, 205-
218.
[2] R. I.Grigorchuk, V. V.Nekrashevych, V. I. Sushchansky, Automata, Dynamical
Systems, and Groups, Proceedings of the Steklov Institute of Mathematics, 231
2000, 134-214.
[3] I. I. Reznykov, V. I. Sushchansky, Growth functions of semigroups defined by Mealy
automata with two states over two-letter alphabet, Report of Ukrainian NAN 2002,
N2, 23-27.
[4] J. K. Slupik, V. I. Sushchansky, Inverse semigroups generated by two-state partially
defined automata, Contr. Gen. Alg. 16, Klagenfurt 2005, 261-274.
[5] M. V. Lawson, Inverse semigroups: The Theory of Partial Symmetries, World Sci-
entific, Singapore 1998.
[6] S. L. Lipskomb, Symmetric inverse semigroups, Mathematical Surves and mono-
graphs, 46, AMS, Providence, RI, 1996, 166 p.
[7] M. Petrich, Inverse semigroups, John Wiley & Sons Inc., New York 1984.
80 Inverse Semigroups
Contact information
J. K. Slupik Institute of Mathematics, Silesian Univer-
sity of Technology, ul. Kaszubska 23, Gli-
wice, Poland
E-Mail: Janusz.Slupik@polsl.pl
URL: 157.158.16.184/js/
|
| id | nasplib_isofts_kiev_ua-123456789-157367 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1726-3255 |
| language | English |
| last_indexed | 2025-11-24T10:31:03Z |
| publishDate | 2006 |
| publisher | Інститут прикладної математики і механіки НАН України |
| record_format | dspace |
| spelling | Slupik, J.K. 2019-06-20T03:07:11Z 2019-06-20T03:07:11Z 2006 Classification of inverse semigroups generated by two-state partially defined invertible automata over the two-symbol alphabet / J.K. Slupik // Algebra and Discrete Mathematics. — 2006. — Vol. 5, № 1. — С. 67–80. — Бібліогр.: 7 назв. — англ. 1726-3255 2000 Mathematics Subject Classification: 20M18; 20M35, 68Q35. https://nasplib.isofts.kiev.ua/handle/123456789/157367 The classification of inverse semigroups generated by two-state partially defined invertible automata over a twosymbol alphabet is investigated. Two presentations of such semigroups are given. The structures of these semigroups are analyzed. en Інститут прикладної математики і механіки НАН України Algebra and Discrete Mathematics Classification of inverse semigroups generated by two-state partially defined invertible automata over the two-symbol alphabet Article published earlier |
| spellingShingle | Classification of inverse semigroups generated by two-state partially defined invertible automata over the two-symbol alphabet Slupik, J.K. |
| title | Classification of inverse semigroups generated by two-state partially defined invertible automata over the two-symbol alphabet |
| title_full | Classification of inverse semigroups generated by two-state partially defined invertible automata over the two-symbol alphabet |
| title_fullStr | Classification of inverse semigroups generated by two-state partially defined invertible automata over the two-symbol alphabet |
| title_full_unstemmed | Classification of inverse semigroups generated by two-state partially defined invertible automata over the two-symbol alphabet |
| title_short | Classification of inverse semigroups generated by two-state partially defined invertible automata over the two-symbol alphabet |
| title_sort | classification of inverse semigroups generated by two-state partially defined invertible automata over the two-symbol alphabet |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/157367 |
| work_keys_str_mv | AT slupikjk classificationofinversesemigroupsgeneratedbytwostatepartiallydefinedinvertibleautomataoverthetwosymbolalphabet |