On sequences of Mealy automata and their limits
We introduce the notions of n-state Mealy automaton sequence and limit of this sequence. These notions are illustrated by the 2-state Mealy automaton sequences that have the set of finite limit automata.
Збережено в:
| Дата: | 2006 |
|---|---|
| Автор: | |
| Формат: | Стаття |
| Мова: | English |
| Опубліковано: |
Інститут прикладної математики і механіки НАН України
2006
|
| Назва видання: | Algebra and Discrete Mathematics |
| Онлайн доступ: | http://dspace.nbuv.gov.ua/handle/123456789/157396 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | On sequences of Mealy automata and their limits / I.I. Reznykov // Algebra and Discrete Mathematics. — 2006. — Vol. 5, № 4. — С. 93–111. — Бібліогр.: 3 назв. — англ. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-157396 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-1573962019-06-21T01:28:18Z On sequences of Mealy automata and their limits Reznykov, I.I. We introduce the notions of n-state Mealy automaton sequence and limit of this sequence. These notions are illustrated by the 2-state Mealy automaton sequences that have the set of finite limit automata. 2006 Article On sequences of Mealy automata and their limits / I.I. Reznykov // Algebra and Discrete Mathematics. — 2006. — Vol. 5, № 4. — С. 93–111. — Бібліогр.: 3 назв. — англ. 1726-3255 2000 Mathematics Subject Classification: 20M35, 68Q70. http://dspace.nbuv.gov.ua/handle/123456789/157396 en Algebra and Discrete Mathematics Інститут прикладної математики і механіки НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
English |
| description |
We introduce the notions of n-state Mealy automaton sequence and limit of this sequence. These notions are
illustrated by the 2-state Mealy automaton sequences that have
the set of finite limit automata. |
| format |
Article |
| author |
Reznykov, I.I. |
| spellingShingle |
Reznykov, I.I. On sequences of Mealy automata and their limits Algebra and Discrete Mathematics |
| author_facet |
Reznykov, I.I. |
| author_sort |
Reznykov, I.I. |
| title |
On sequences of Mealy automata and their limits |
| title_short |
On sequences of Mealy automata and their limits |
| title_full |
On sequences of Mealy automata and their limits |
| title_fullStr |
On sequences of Mealy automata and their limits |
| title_full_unstemmed |
On sequences of Mealy automata and their limits |
| title_sort |
on sequences of mealy automata and their limits |
| publisher |
Інститут прикладної математики і механіки НАН України |
| publishDate |
2006 |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/157396 |
| citation_txt |
On sequences of Mealy automata and their limits / I.I. Reznykov // Algebra and Discrete Mathematics. — 2006. — Vol. 5, № 4. — С. 93–111. — Бібліогр.: 3 назв. — англ. |
| series |
Algebra and Discrete Mathematics |
| work_keys_str_mv |
AT reznykovii onsequencesofmealyautomataandtheirlimits |
| first_indexed |
2025-07-14T09:49:57Z |
| last_indexed |
2025-07-14T09:49:57Z |
| _version_ |
1837615386982350848 |
| fulltext |
Algebra and Discrete Mathematics RESEARCH ARTICLE
Number 4. (2006). pp. 93 – 111
c© Journal “Algebra and Discrete Mathematics”
On sequences of Mealy automata and their limits
Illya I. Reznykov
Communicated by V. I. Sushchansky
Abstract. We introduce the notions of n-state Mealy au-
tomaton sequence and limit of this sequence. These notions are
illustrated by the 2-state Mealy automaton sequences that have
the set of finite limit automata.
Introduction
One of the main problem that appears in investigations of the set of
discrete objects — how the properties of certain objects are interrelated
or how to get the properties of an object through the research of close
objects. This problem have been solved by such methods as using op-
erations under these objects that keep the desired properties, selection
of special subsets of objects with similar properties, or analysis of object
sequences and their limits.
The investigators of Mealy automaton growth deal with countable
infinite set of discrete objects. The paper is devoted to consideration
the ideas of Mealy automaton sequences and limit automata of these se-
quences. The limit automaton is constructed over the infinite alphabet,
but there can be found automata over finite alphabets with the same
properties as the limit automaton. Therefore the using of Mealy automa-
ton sequences have two benefits: it allows to join the automata with
similar properties, and to interlink automata-members of a sequence and
automata that have the same properties as the limit automaton.
The paper has the following structure. The notions of Mealy au-
tomaton sequence and limit are introduced in Section 1. As special case,
2000 Mathematics Subject Classification: 20M35, 68Q70.
Key words and phrases: Mealy automaton, growth function, automaton se-
quence.
94 On sequences of Mealy automata and their limits
the expanding automaton sequences are considered, and the limits of the
growth functions and the semigroups are directly constructed. Section 2
describes two sets of automata of exponential growth. We construct the
semigroup, defined by these automata, and calculate their growth func-
tions. These automata are used in Subsection 3.1 for illustrating the
properties of introduced in Section 1 notions. Some remarks that con-
cern limit of Mealy automaton sequences are listed in Subsection 3.2.
1. Mealy automaton sequences and limits
1.1. Sequences of Mealy automata
We will use the definitions from [1]. Let us denote a m-symbol alphabet
by the symbol Xm, Xm = {0, 1, . . . ,m− 1}, and the infinite alphabet
{0, 1, . . .} by X. We denote the set of all infinite to right words over Xm
by the symbol Xω
m. We write a transformation ψ over Xm as
(ψ(0), ψ(1), . . . , ψ(m− 1)) .
Definition 1. Let us fix the positive integers n ≥ 2 and k ≥ 2. We call
the sequence {Am, m ≥ k} of Mealy automata such that the automaton
Am is n-state Mealy automaton over the alphabet Xm by the n-state Mealy
automaton sequence.
Let us introduce the special type of Mealy automaton sequences,
where the next automaton extends the previous one.
Definition 2 ([2]). Let A = (Xm, Q, π, λ) be an arbitrary n-state au-
tomaton over a m-symbol alphabet. The n-state automaton A(X) =
(Xm+1, Q, π1, λ1) over the (m+ 1)-symbol alphabet such that the follow-
ing equalities:
π1(x, q) = π(x, q) and λ1(x, q) = λ(x, q)
hold for all x ∈ Xm, q ∈ Q, is called the extension of A.
The relation of Mealy automaton extension induces the partial order
on the set of all n-state Mealy automata, where A1 < A2 if and only if
A2 is an extension of A1.
Definition 3. The n-state Mealy automaton sequence is expanding if the
automaton Am+1 is an extension of the automaton Am for all m ≥ k.
Let us note that for all q ∈ Q and u ∈ Xω
m the equality holds
f
q,A(X)(u) = fq,A(u).
Therefore the following proposition holds.
I. Reznykov 95
Proposition 1. Let A be an arbitrary Mealy automaton, and A(X) be
an extension of A. Let us denote the semigroups and the growth func-
tions, defined by A and A(X), by the symbols SA , γA and S
A(X) , γA(X)
respectively.
1. The semigroup SA is a factor-semigroup of the semigroup S
A(X).
2. There are two possible cases: either
γA(n) = γ
A(X)(n), n ≥ 1,
or there exists N ∈ N such that
γA(n) = γ
A(X)(n), 1 ≤ n < N,
γA(n) < γ
A(X)(n), n ≥ N.
Proof. Let some nontrivial relation holds in the semigroup S
A(X) :
fqi1
fqi2
. . . fqik
= fqj1
fqj2
. . . fqjl
, (1.1)
where k, l ≥ 1, ip, jt ∈ {0, 1, . . . , n− 1}, 1 ≤ p ≤ k, 1 ≤ t ≤ l. It means
that the following equality holds
fqi1
fqi2
. . . fqik
(u) = fqj1
fqj2
. . . fqjl
(u) (1.2)
for any word u ∈ Xω
m+1. As the equality (1.2) is true for all words u ∈ Xω
m,
then the relation (1.1) holds in SA . Therefore the set of relations of SA
includes all defining relations of S
A(X) , and the semigroup SA is a factor-
semigroup of the semigroup S
A(X) .
It follows from the previous item that there exist the defining relation
sets RA and R
A(X) of SA and S
A(X) respectively such that RA ⊇ R
A(X) .
Here and in the sequel text, the inequality R1 ⊃ R2 denotes that each
relation of R2 follows from the relations of R1. If the equality RA = R
A(X)
holds, then SA and S
A(X) are isomorphic semigroups, and the growth
functions γA and γ
A(X) coincide for all n ≥ 1.
Otherwise, let r : s1 = s2 be the relation from RA\RA(X) with the
minimal length of left-side word. Assign N = ℓ(s1). Then the growth
functions γA and γ
A(X) coincide for all 1 ≤ n < N because the sets RA
and R
A(X) include the same subset of relations that can be applied to
semigroup words of length less than N . Clearly the inequality γA(N) <
γ
A(X)(N) holds. Due to this, the inequality γA(n) < γ
A(X)(n) holds for
all n > N .
The Proposition is completely proved.
96 On sequences of Mealy automata and their limits
1.2. Limit of Mealy automaton sequences
Let us introduce the notion of limit of Mealy automaton sequence. The
transition and output functions of Am are discrete functions, that can be
defined by two sets of (nm) values. Therefore the pointwise limits (in
discrete Hausdorff metrics) of these functions’ values for fixed arguments
as m tends to infinity can be considered. Namely
Definition 4. Let A = {Am = (Xm, Q, πm, λm) , m ≥ k}, k ≥ 2, be
an arbitrary n-state Mealy automaton sequence. The automaton A∞ =
(X,Q, π, λ) is called the limit automaton of the sequence A, if for any
state q ∈ Q and any symbol x ∈ X there exists the number M ≥ k such
that the equalities
πm(q, x) = π(q, x) and λm(q, x) = λ(q, x)
hold for all m ≥M .
It follows from Definition 4 that limit automaton is a unique if it
exists. The limit automaton of Mealy automaton sequence have com-
mon “limit properties”. For example, the pointwise limit of product or
sum of automata equals product or sum of the limit automata of these
sequences respectively. But the pointwise limit does not preserve some
“automaton properties” such as equivalence of states. Let us consider the
2-state automaton sequence {Am, m ≥ 2} such that Am have the follow-
ing automaton transformations:
f0 = (f0, f0, . . . , f0) (0, 1, . . . ,m− 2,m− 1) ,
f1 = (f1, f1, . . . , f1) (0, 1, . . . ,m− 2, 0) .
Obviously, these transformations are different and Am has two inequiva-
lent states. The automaton transformations of the limit automaton A∞
are defined by the equalities
f0 = (f0, f0, . . . , f0, . . .) (0, 1, . . . ,m− 1, . . .) ,
f1 = (f1, f1, . . . , f1, . . .) (0, 1, . . . ,m− 1, . . .) ,
whence f0 = f1 and A∞ contains one state.
Let A be an arbitrary automaton sequence. Each automaton Am
unambiguously defines the automaton transformation semigroup SAm
and
the growth function γAm
. Therefore the automaton sequence A defines
the sequence of the semigroups S = {SAm
, m ≥ k} (where the natural
set of generators is fixed in each SAm
) and the sequence of the growth
functions O = {γAm
, m ≥ k}. Let us define the limit γA of the growth
I. Reznykov 97
function sequence as the pointwise limit of γAm
as m → ∞, if it exists.
Otherwise, we say that the limit of O doesn’t exist.
Let us define the limit of the semigroup sequence S, if semigroups
compose increasing (SAm
is a factor-semigroup of SAm+1) or decreasing
(SAm+1 is a factor-semigroup of SAm
) sequence. Let Ri be the set of
relations of the semigroup SAi
, i ≥ k. Then the following relations
Rk ⊃ Rk+1 ⊃ . . . ⊃ Rm ⊃ . . .
or
Rk ⊂ Rk+1 ⊂ . . . ⊂ Rm ⊂ . . .
hold, and the semigroup SA is defined as the semigroup with the set of
defining relations equals the join or the intersection of semigroups from
S respectively.
It follows from Definition 4 that the limit automaton is considered over
the infinite alphabet. The investigations of automata over the infinite
alphabet are more complicated against automata over finite alphabets.
Therefore, let us introduce the notion of the finite limit automaton.
Definition 5. Let A = {Am, m ≥ k}, k ≥ 2, be an arbitrary n-state
Mealy automaton sequence. We say that the n-state automaton B over
the finite alphabet is the finite limit automaton of the sequence A, if the
equalities γB = γA and SB
∼= SA hold.
Let us note that the finite automaton for certain automaton sequence
is not a unique if it exists. There are many unclear aspects, and some
remarks are listed in Section 3.
Let’s consider the case of expanding automaton sequence. Then there
exist the limits of sequences of semigroups and growth functions. Let
A = {Am = (Xm, Q, πm, λm) , m ≥ k} ,
where k ≥ 2, be an arbitrary expanding Mealy automaton sequence.
There are two possible cases. Let us assume that there exists the number
M such that all growth functions {γAm
, m ≥M} coincide for n ≥ 1.
Then the limit γA is the function γAM
, and each automaton Am, m ≥M ,
can be considered as the finite limit of A. Obviously, all semigroups from
the set {SAm
, m ≥M} are the same.
Otherwise, it follows from Proposition 1 that there exists a unique
infinite sequence
k = m1 < m2 < m3 < . . .
such that the automata Ami
and Ami+1 have different growth functions,
and all automata Am formi ≤ m < mi+1, have the same growth function,
98 On sequences of Mealy automata and their limits
i ≥ 1. For each i ≥ 1 there exists the number Nmi
∈ N such that the
relations
γAmi
(n) = γAmi+1
(n), 1 ≤ n < Nmi
,
γAmi
(n) < γAmi+1
(n), n ≥ Nmi
.
hold. It follows from the choice of mi that the following inequalities
1 ≤ Nm1 < Nm2 < Nm3 < . . .
hold, whence the pointwise limit of the growth functions {γAm
, m ≥ k}
is defined by the equality
γA(n) =
γAm1
(n), if 1 ≤ n < Nm1 ;
γAm2
(n), if Nm1 ≤ n < Nm2 ;
γAm3
(n), if Nm2 ≤ n < Nm3 ;
. . . , . . .
In addition, it follows from Proposition 1 that the defining relations in
each semigroup SAmi
can be choose such that
R1 ⊃ R2 ⊃ R3 ⊃ . . . ,
where Ri is the set of defining relations of the semigroup SAmi
, i ≥ 1.
Then the defining relation set of the semigroup SA is defined by the
equality
RSA
=
⋂
i≥1
Ri.
Let us note, that the growth order [γA] can be not equal to pointwise
limit of growth orders [γAm
] as m tends to ∞. For example, the 2-state
Mealy automaton sequence {Am, m ≥ 3} is considered in [1] such that
[Am] =
[
nm−1
]
, but the equality [γA] = [2n] holds.
2. Sets of Mealy automata Am and B
2.1. Definitions
Let m ≥ 3 and gi, hi, yi ∈ {0, 1}, i = 2, 3, . . . ,m− 1, be arbitrary num-
bers. Consider the following transformations of Xm:
α = (0, . . . , 0, 0) , αp = (0, . . . , 0, 1, 2, . . . ,m− 1 − p) , p ≥ 1;
β = (0, . . . , 0,m− 1) , βp = (0, . . . , 0, 1, 2, . . . ,m− 2 − p,m− 1) , p ≥ 1.
I. Reznykov 99
Clearly the equalities
α
p
1 =
{
αp, if 1 ≤ p ≤ m− 2,
α, if p ≥ m− 1;
β
p
1 =
{
βp, if 1 ≤ p ≤ m− 3,
β, if p ≥ m− 2.
hold.
Let Am be an arbitrary 2-state Mealy automaton over Xm such that
its automaton transformations f0 and f1 are defined by the following
equalities:
f0 =
(
f0, f1, fg2 , fg3 , . . . , fgm−1
)
(0, 0, 1, 2, . . . ,m− 3,m− 2) ,
f1 =
(
f0, f1, fh2 , fh3 , . . . , fhm−1
)
(1, 0, y2, y3, . . . , ym−2, ym−1) .
(2.3)
Let us define the set of all automata Am where gi, hi, yi vary over {0, 1}
by the symbol Am.
Similarly, let Bm be an arbitrary 2-state Mealy automaton over Xm
such that its automaton transformations f0 and f1 allow the following
decompositions
f0 =
(
f0, f1, fg2 , fg3 , . . . , fgm−1
)
(0, 0, 1, 2, . . . ,m− 3,m− 1) ,
f1 =
(
f0, f1, fh2 , fh3 , . . . , fhm−1
)
(1, 0, y2, y3, . . . , ym−2, 0) .
(2.4)
Let us define the set of all automata Bm where gi, hi, yi vary over {0, 1}
and m varies over 3, 4, . . . by the symbol B.
Let Φn denote the Fibonacci numbers, defined by Φn = Φn−1 +Φn−2,
Φ1 = Φ2 = 1. The element Φn is defined by the equality [3]:
Φn =
1√
5
((
1 +
√
5
2
)n
−
(
1 −
√
5
2
)n)
, n ≥ 1.
For any n ≥ m ≥ 0 the following equality holds
n
∑
i=m
Φi = Φn+2 − Φm+1.
Let us note that Φn, n ≥ 2, equals the count of words of length (n− 2)
over {a, b} which don’t include subwords bb.
2.2. Properties of Am and B
Let us consider the semigroup relations
rp : f2
1 f
p
0 f1 = f0f1f
p
0 f1,
where p ≥ 1. The properties of automata from Am and B are described
by the following theorems.
100 On sequences of Mealy automata and their limits
Theorem 1. Let Am be an arbitrary automaton from Am.
1. Am defines the automatic transformation semigroup
Sm =
〈
f0, f1 rp, 1 ≤ p ≤ m− 2; f2
1 f
m−1
0 = f0f1f
m−1
0
〉
.
2. The growth function γm of Am is defined by the following equality
γm(n) = Φn+4 −
{
(n+ 2), if 1 ≤ n ≤ m;
Φn+4−m + (m− 1), if n > m.
3. The growth function γSm
of Sm is defined by the following equality
γSm
(n) = Φn+6 −
{
n2+5n+16
2 , if 1 ≤ n ≤ m;
Φn+6−m + 2n(m−1)+7m−m2
2 , if n > m.
Theorem 2. Let B be an arbitrary automaton from B.
1. The automaton B defines the semigroup
S =
〈
f0, f1 rp, p ≥ 1
〉
.
2. The growth function γ of B is defined by the following equality
γ(n) = Φn+4 − (n+ 2), n ≥ 1.
3. The growth function γS of S is defined by the following equality
γS(n) = Φn+6 −
n2 + 5n+ 16
2
, n ≥ 1.
It follows from Theorems 1 and 2 that the sequences of functions γm
and γSm
have the pointwise limits. Namely,
Corollary 1. The functions γ and γS are the pointwise limits of the
functions γm and γSm
as m tends to infinity respectively. That is for
each n ≥ 1 the equalities hold:
γm(n) −−−−→
m→∞
γ(n), γSm
(n) −−−−→
m→∞
γS(n).
I. Reznykov 101
2.3. Properties of automaton transformations
Let us fix the numbers m ≥ 3 and gi, hi, yi ∈ {0, 1}, i = 2, 3, . . . ,m− 1.
Let Am and Bm be the automata from Am and B respectively, defined
by the numbers gi, hi, fi.
Let [r] denotes integral part of rational number r, and [[p]] denotes
the parity of nonnegative integer p, p ≥ 0, [[p]] ∈ {0, 1}.
Proposition 2. The relations rp, p ≥ 1, hold in the semigroups Sm and
S. In addition, in Sm the relation holds
f2
1 f
m−1
0 = f0f1f
m−1
0 . (2.5)
Let us note, that the relations rp, p ≥ m− 1, follow from the rela-
tion (2.5):
f2
1 f
p
0 f1 = f2
1 f
m−1
0 · fp−m+1
0 f1 = f0f1f
m−1
0 · fp−m+1
0 f1 = f0f1f
p
0 f1.
Proof. Let us consider the automaton Am. It follows from (2.3) that the
following equalities hold:
f
p
0 =
(
f
p
0 , f
p−1
0 f1, f
p−2
0 f1fg2 , . . . , f0f1fg2fg3 . . . fgp−1 ,
f1fg2fg3 . . . fgp , fg2fg3 . . . fgp+1 , . . . , fgm−p
fgm−p+1 . . . fgm−1
)
αp, (2.6a)
where 0 ≤ p ≤ m− 2, and
f2
1 =
(
f1f0, f0f1, fy2fh2 , . . . , fym−1fhm−1
)
(0, 1, 1 − y2, . . . , 1 − ym−1) ,
f
p
0 f1 =
(
f
p−1
0 f1f0, f
p
0 f1, f
p−1
0 fy2fh2 , f
p−1
0 fy3fh3 , . . . , f
p−1
0 fym−1fhm−1
)
α.
(2.6b)
Let us write the unrolled forms of left and right part of rp, p ≥ 1:
f2
1 f
p
0 f1 =
(
f1f
p
0 f1f0, f
p+1
0 f1, f1f
p
0 fy2fh2 ,
f1f
p
0 fy3fh3 , . . . , f1f
p
0 fym−1fhm−1
)
α,
f0f1f
p
0 f1 =
(
f1f
p
0 f1f0, f
p+1
0 f1, f1f
p
0 fy2fh2 ,
f1f
p
0 fy3fh3 , . . . , f1f
p
0 fym−1hm−1
)
α,
whence the relations rp hold in Sm. Let us check the relations (2.5). It
follows from (2.6) that
f2
1 f
m−1
0 =
(
f1f
m
0 , f1f
m−1
0 f1, f1f
m−2
0 f1fg2 , . . . ,
f1f
2
0 f1fg2fg3 . . . fgm−2 , f1f0f1fg2fg3 . . . fgm−1
)
α,
f0f1f
m−1
0 =
(
f1f
m
0 , f1f
m−1
0 f1, f1f
m−2
0 f1fg2 , . . . ,
f1f
2
0 f1fg2fg3 . . . fgm−2 , f1f0f1fg2fg3 . . . fgm−1
)
α,
102 On sequences of Mealy automata and their limits
and therefore (2.5) hold in Sm.
Let us consider Bm. Similarly, it follows from (2.4) that the following
equalities hold:
f
p
0 =
(
f
p
0 , f
p−1
0 f1, f
p−2
0 f1fg2 , f
p−3
0 f1fg2fg3 , . . . , f0f1fg2fg3 . . . fgp−1 ,
f1fg2 . . . fgp , fg2fg3 . . . fgp+1 , . . . , fgm−p−1fgm−p
. . . fgm−2 , f
p
gm−1
)
βp,
if 1 ≤ p ≤ m− 3, and
f
p
0 =
(
f
p
0 , f
p−1
0 f1, f
p−2
0 f1fg2 , f
p−3
0 f1fg2fg3 , . . . ,
f
p−m+2
0 f1fg2fg3 . . . fgm−2 , f
p
gm−1
)
β,
otherwise. Hence for any p ≥ 1 one has
f2
1 =(f1f0, f0f1, fy2fh2 , fy3fh3 , . . . ,
fym−2fhm−2 , f0fhm−1
)
(0, 1, 1 − y2, 1 − y3, . . . , 1 − ym−2, 1) ,
f
p
0 f1 =
(
f
p−1
0 f1f0, f
p
0 f1, f
p−1
0 fy2fh2 , . . . , f
p−1
0 fym−2fhm−2 , f
p
0 fhm−1
)
α,
and it yields the following unrolled forms
f2
1 f
p
0 f1 =
(
f1f
p
0 f1f0, f
p+1
0 f1, f1f
p
0 fy2fh2 , . . . ,
f1f
p
0 fym−2fhm−2 , f1f
p+1
0 fhm−1
)
α,
f0f1f
p
0 f1 =
(
f1f
p
0 f1f0, f
p+1
0 f1, f1f
p
0 fy2fh2 , . . . ,
f1f
p
0 fym−2fhm−2 , f1f
p+1
0 fhm−1
)
α.
Thus the relations rp hold in S. Proposition is completely proved.
Proposition 3. The following equality holds for both Am and Bm:
f
p1
0 f1f
p2
0 f1 . . . f
pk−2
0 f1f
pk−1
0 f1f
pk
0 (0∗) = 0p110p21 . . . 0pk−210pk−110pk · 0∗,
where k ≥ 1, p1, pk+1 ≥ 0, pi > 0, 1 < i < k.
Proof. As the restriction of the automata Am and Bm on a 2-symbol
alphabet coincide, then it’s enough to consider the case of Am. It follows
from (2.6b) that for any k ≥ 2 and arbitrary pi > 0, 1 ≤ i ≤ k − 1, the
following equalities hold:
f
p1
0 f1f
p2
0 f1 . . . f
pk−2
0 f1f
pk−1
0 f1 =
(
f
p1−1
0 f1f
p2
0 f1 . . . f
pk−2
0 f1f
pk−1
0 f1f0,
f
p1−1
0 f1f
p2
0 f1 . . . f
pk−2
0 f1f
pk−1+1
0 f1, . . .
)
(0, 0, . . . , 0) ;
f1f
p1
0 f1f
p2
0 f1 . . . f
pk−2
0 f1f
pk−1
0 f1 =
(
f
p1
0 f1f
p2
0 f1 . . . f
pk−2
0 f1f
pk−1
0 f1f0,
f
p1
0 f1f
p2
0 f1 . . . f
pk−2
0 f1f
pk−1+1
0 f1, . . .
)
(1, 1, . . . , 1) .
I. Reznykov 103
Using the equality fp
0 (0∗) = 0∗, p > 0, one has
f
p1
0 f1f
p2
0 f1 . . . f
pk−2
0 f1f
pk−1
0 f1f
pk
0 (0∗) =
= f
p1
0 f1f
p2
0 f1 . . . f
pk−2
0 f1f
pk−1
0 f1(0
∗) = 0p110p21 . . . 0pk−210pk−110∗,
that was required to prove.
Proposition 4. Let s ∈ S be an arbitrary element. It admits a unique
presentation as the word
s = f
p1
0 f1f
p2
0 f1 . . . f
pk−2
0 f1f
pk−1
0 f
pk
1 f
pk+1
0 , (2.7)
where k = 0, p1 > 0, or k ≥ 2, p1, pk+1 ≥ 0, pi > 0, 2 ≤ i ≤ k.
Proof. Let s is written as the word
s = f r1
0 f r2
1 f r3
0 f r4
1 . . . f
r2l−1
0 f
r2l
1 f
r2l+1
0 , (2.8)
where l ≥ 0, r1, r2l+1 ≥ 0, ri > 0, 2 ≤ i ≤ 2l, and ℓ(s) =
2l+1
∑
i=1
ri > 0. If s
is written in the form (2.7), then Proposition 4 is true.
Otherwise, it follows from rp that for any p1, p2 ≥ 0 the equalities
f
p1
1 f
p2
0 f1 = f
p1−2
1 f0f1f
p2
0 f1 = . . . = f
[[p1]]
1 (f0f1)
[ p1
2 ]fp2
0 f1
hold. Applying the equality at the line above to the word (2.8) from right
to left, s can be written as the following word
s = f r1
0 f
[[r2]]
1 (f0f1)
[ r2
2 ]f r3
0 f
[[r4]]
1 (f0f1)
[ r4
2 ] . . .
f
r2l−3
0 f
[[r2l−2]]
1 (f0f1)
[
r2l−2
2 ]f
r2l−1
0 f1 · f r2l−1
1 f
r2l+1
0 ,
and it doesn’t include subwords f2
1 , may be excepting the last occurrence
— the subword f r2l
1 . The right-side word has the form (2.7), and the proof
is completed.
Proposition 5. An arbitrary element s ∈ Sm admits a unique presenta-
tion as the word
s = f
p1
0 f1f
p2
0 f1 . . . f
pk−2
0 f1f
pk−1
0 f
pk
1 f
pk+1
0 , (2.9)
where k = 0, p1 > 0, or k ≥ 2, p1, pk+1 ≥ 0, pi > 0, 2 ≤ i ≤ k, and
pk = 1 if pk+1 ≥ m− 1.
104 On sequences of Mealy automata and their limits
Proof. It follows from Propositions 2 and 4 that each element s ∈ Sm
can be written in the form (2.7). In the case p2k+1 ≥ m− 1 the rela-
tion (2.5) can be applied to s, and the end f r2l
1 f
r2l+1
0 may be replaced by
f
[[r2l]]
1 (f0f1)
[ r2l
2 ]f
r2l+1
0 . After it, the word s has the form (2.9).
Proposition 6. The count of words of length n, n ≥ 1, written in the
form (2.7), equals
w(n) = Φn+4 − (n+ 2), n ≥ 1.
Proof. Let us separate the words written in the form (2.7) to two types:
the words such that k = 0 or pk = 1, and the words such that k ≥ 2 and
pk > 1. The count of words of length n of first type is equal to Φn+2. An
arbitrary word s of second type can be written as
s = f
p1
0 f1f
p2
0 f1 . . . f
pk−2
0 f1f
pk−1
0 f1 · fpk−1
1 f
pk+1
0 . (2.10)
Each word (2.10) unambiguously corresponds to the word of length (n+ 1):
s
′ = f
p1
0 f1f
p2
0 f1 . . . f
pk−2
0 f1f
pk−1
0 f1 · fpk−1
0 f1f
pk+1
0 .
Hence, the count of the words (2.10) of length n equals the count of words
of length (n+ 1) over {f0, f1} such that they don’t include subwords f2
1
and contain at least two symbols f1. This count is equal to
Φn+3 −
(
n+ 1
0
)
−
(
n+ 1
1
)
= Φn+3 − (n+ 2).
Finally,
w(n) = Φn+2 + Φn+3 − (n+ 2) = Φn+4 − (n+ 2),
for all n ≥ 1.
Proposition 7. The count of words of length n, n ≥ 1, written in the
form (2.9) equals
wm(n) = Φn+4 −
{
(n+ 2), if 1 ≤ n ≤ m;
Φn+4−m + (m− 1), if n > m.
Proof. For 1 ≤ n ≤ m the value wm(n) equals w(n), because the rela-
tion (2.5) can not be applied. For n > m the value wm(n) equals w(n)
minus the count of words written in the form (2.7) such that k ≥ 2,
pk+1 ≥ m− 1 and pk > 1. This count equals the count of words (2.7) of
length (n− (m− 1)) such that pk > 1, that is
Φn−(m−1)+3 − (n− (m− 1) + 2).
I. Reznykov 105
Therefore, for 1 ≤ n ≤ m we have
wm(n) = Φn+4 − (n+ 2),
and for n > m the following equality holds:
wm(n) = (Φn+4 − (n+ 2)) −
(
Φn−(m−1)+3 − (n− (m− 1) + 2)
)
=
= Φn+4 − Φn+4−m − (m− 1).
2.4. Proofs of Theorems 1 and 2
Proposition 8. Let s1, s2 ∈ Sm be arbitrary elements, written in the
form (2.9):
s1 = f
p1
0 f1f
p2
0 f1 . . . f
pk−2
0 f1f
pk−1
0 f
pk
1 f
pk+1
0 ,
s2 = f t1
0 f1f
t2
0 f1 . . . f
tl−2
0 f1f
tl−1
0 f
tl
1 f
tl+1
0 ,
They define the same transformation over the set Xω
m if and only if they
coincide graphically, that is
k = l; pi = ti, 1 ≤ i ≤ k.
Proof. Clearly s1 and s2 define the same transformation over Xω
m, if they
coincide graphically. Therefore it’s enough to prove that if s1 and s2 have
different forms (2.9), then they define different transformations over Xω
m.
Let us assume that elements s1 and s2 define the same transformation
over Xω
m, but written in the different form (2.9). Then for any u ∈ Xω
m
the following equality holds
s1(u) = s2(u). (2.11)
It follows from (2.11) that the equality holds
f0s1f0f1(0
∗) = f0s2f0f1(0
∗). (2.12)
Using Proposition 3, let us rewrite the left- and right-side words of the
equality at the line above:
f0s1f0f1(0
∗) = f
p1+1
0 f1f
p2
0 . . . f1f
pk−1
0 f
[[pk]]
1 (f0f1)
[ pk
2 ]f
pk+1+1
0 f1(0
∗) =
= 0p1+110p21 . . . 0pk−210pk−11[[pk]](01)[
pk
2 ]0pk+1+110∗,
f0s2f0f1(0
∗) = f t1+1
0 f1f
t2
0 . . . f1f
tl−1
0 f
[[tl]]
1 (f0f1)
[
tl
2
]
f
tl+1+1
0 f1(0
∗) =
= 0t1+110t21 . . . 0tl−210tl−11[[tl]](01)
[
tl
2
]
0tl+1+110∗.
106 On sequences of Mealy automata and their limits
As s1 and s2 have the different forms (2.9) then the equality (2.12) can
be true if and only if one of the element, say s1, have the form
s1 = f
p1
0 f1f
p2
0 f1 . . . f
pk−2
0 f1f
pk−1
0 f
pk
1 f
pk+1
0 ,
and the other, s2, is written as
s2 = f
p1
0 f1f
p2
0 f1 . . . f
pk−2
0 f1f
pk−1
0 f
[[pk]]
1 (f0f1)
r1f0f
2r2+1
1 f
pk+1
0 ,
where r1 ≥ 0, r2 ≥ 0, r1 + 1 + r2 =
[
pk
2
]
, pk+1 ≤ m− 2, pk ≥ 2.
It follows from (2.6) and (2.3), that for arbitrary pk ≥ 1, 1 ≤ pk+1 ≤
m− 2, and for all u ∈ Xω
m the equalities hold:
f
pk+1
0 (pk+1 · u) = 1 · fg2fg3 . . . fgpk+1+1(u),
f
pk
1 f
pk+1
0 (pk+1 · u) = (1 − [[pk]]) · f [[pk]]
1 (f0f1)
[ pk
2 ]fg2fg3 . . . fgpk+1+1(u),
f0f
pk
1 f
pk+1
0 (pk+1 · u) = 0 · f [[pk]]
0 f1(f0f1)
[ pk
2 ]fg2fg3 . . . fgpk+1+1(u).
Without restricting the generality, let us assume that pk+1 ≥ 1. Other-
wise, we can repeat sequel speculations for the elements s1f0 and s2f0. It
follows from the equalities at the line above that
f0s1(pk+1 · u) = 0 · s′1(u) and f0s2(pk+1 · u) = 0 · s′2(u),
where
s
′
1 = f
p1
0 f1f
p2
0 f1 . . . f
pk−2
0 f1f
pk−1
0 · f [[pk]]
0 f1(f0f1)
[ pk
2 ]fg2fg3 . . . fgpk+1+1 ,
s
′
2 = f
p1
0 f1f
p2
0 f1 . . . f
pk−2
0 f1f
pk−1
0 f
[[pk]]
1 (f0f1)
r1−1f0·
f0f1(f0f1)
r2fg2fg3 . . . fgpk+1+1 .
For any word u ∈ Xω
m the equality s
′
1(u) = s
′
2(u) holds due by the as-
sumption (2.11). Therefore the following equality hold:
f0s
′
1f0f1(0
∗) = f0s
′
2f0f1(0
∗).
Obviously, right multiplying by f0f1 may change only the ends of semi-
group words s
′
i, i = 1, 2, and affects on the subword f1fg2fg3 . . . fgpk+1+1 .
Hence it follows from Proposition 3 that the elements s
′
1 and s
′
2 define
different transformations over Xω
m. We get the contradiction with the
assumption (2.11).
Proof of Theorem 1. It follows from Proposition 2 that the relations rp,
p ≥ 1, and (2.5) hold in the semigroup Sm. In Proposition 5 these
relations allow to reduce an arbitrary element s ∈ Sm to the form (2.9).
I. Reznykov 107
It is shown in Proposition 8 that two semigroup elements define the same
transformation over Xω
m if and only if they have the same form (2.9).
Therefore, the set of relations
f2
1 f
m−1
0 = f0f1f
m−1
0 , f2
1 f
p
0 f1 = f0f1f
p
0 f1, 1 ≤ p ≤ m− 2;
is the set of defining relations. In addition, the relations do not depends
on the numbers gi, hi, yi, and all automata from the set Am define the
same semigroup, whence Item 1 of Theorem 1 is true.
Let us calculate the growth functions of Am and Sm. As the defining
relations of Sm does not change the length of semigroup words then the
equalities hold
γm(n) = wm(n), γSm
(n) =
n
∑
i=1
wm(i).
Using Proposition 7, we have
γm(n) = Φn+4 −
{
(n+ 2), if 1 ≤ n ≤ m,
Φn+4−m + (m− 1), if n > m;
and Item 2 holds.
Let n ≤ m. Then
γSm
(n) =
n
∑
i=1
(Φi+4 − (i+ 2)) = Φn+6 − Φ6 − 2n− n2 + n
2
=
= Φn+6 −
n2 + 5n+ 16
2
.
Similarly for n > m the following equalities hold
γSm
(n) = γSm
(m) +
n
∑
i=m+1
(Φi+4 − Φi+4−m − (m− 1)) =
= Φm+6 −
m2 + 5m+ 16
2
+ Φn+6 − Φm+6 − Φn+6−m + Φm+6−m−
− (n−m) (m− 1) = Φn+6 − Φn+6−m − 2n(m− 1) + 7m−m2
2
,
that coincides with the formulae in Item 3.
Proposition 9. Let s1, s2 ∈ S be arbitrary elements, written in the
form (2.7):
s1 = f
p1
0 f1f
p2
0 f1 . . . f
pk−2
0 f1f
pk−1
0 f
pk
1 f
pk+1
0 ,
s2 = f t1
0 f1f
t2
0 f1 . . . f
tl−2
0 f1f
tl−1
0 f
tl
1 f
tl+1
0 ,
108 On sequences of Mealy automata and their limits
They define the same transformation over the set Xω
m if and only if they
coincide graphically, that is
k = l; pi = ti, 1 ≤ i ≤ k.
Proof. Proposition 9 can be proved in the same way as Proposition 8. It
follows from (2.3) and (2.4) that the actions of Am and Bm differ only at
the symbol (m− 1). Therefore it’s enough to consider the case when the
elements s1 and s2 are written in the following way:
s1 = f
p1
0 f1f
p2
0 f1 . . . f
pk−2
0 f1f
pk−1
0 f
pk
1 f
pk+1
0 ,
s2 = f
p1
0 f1f
p2
0 f1 . . . f
pk−2
0 f1f
pk−1
0 f
[[pk]]
1 (f0f1)
r1f0f
2r2+1
1 f
pk+1
0 ,
where r1 ≥ 0, r2 ≥ 0, r1 + 1 + r2 =
[
pk
2
]
, pk ≥ 2. Using the unrolled
forms (2.4) the equalities hold for arbitrary pk, pk+1 ≥ 1, and any u ∈ Xω
m:
f
pk+1
0 ((m− 1) · u) = (m− 1) · fpk+1
gm−1(u),
f
pk
1 f
pk+1
0 ((m− 1) · u) = (1 − [[pk]]) · f1−[[pk]]
0 (f1f0)
[
pk−1
2
]
fhm−1f
pk+1
gm−1(u),
f0f
pk
1 f
pk+1
0 ((m− 1) · u) = 0 · f1−[[pk]]
1 f0(f1f0)
[
pk−1
2
]
fhm−1f
pk+1
gm−1(u).
The sequel speculations are carried out similarly to the case of Am.
Proof of Theorem 2. The relations rp, p ≥ 1, hold in S, and an arbi-
trary element is reduced to the form (2.7) by applying these relations in
Proposition 4. It is proved in Proposition 9 that two semigroup elements
written in different form (2.7) define the different transformations over
Xω
m. Therefore, the presentation of the semigroup, defined by Bm, does
not depend on m and the numbers gi, hi, yi, and S have the presentation,
stated in Theorem 2.
The count of words of length n, that written in the form (2.7), is
calculated in Proposition 6, and this count doesn’t depend on m. Using
the equalities
γ(n) = w(n), γS(n) =
n
∑
i=1
w(i),
and the calculations in the proof of Theorem 1, the growth functions of
each automaton from the set Bm and the semigroup S are defined by the
equalities:
γ(n) = Φn+4 − (n+ 2), γS(n) = Φn+6 −
n2 + 5n+ 16
2
,
for all n ≥ 1.
I. Reznykov 109
Proof of Corollary 1. Let us fix n ≥ 1. It follows from Theorem 1 and 2
that for all m ≥M = n+ 1 the equalities hold:
γm(n) = γ(n), γSm
(n) = γS(n).
Hence the functions γ and γS are the pointwise limits of the sequences
{γm, m ≥ 3} and {γSm
, m ≥ 3} as m tends to the infinity respectively.
3. Conclusions
3.1. Examples of expanding sequences
Let us construct examples of expanding sequences, using the automata
from the sets Am and B. Let {g2, g3, . . .}, {h2, h3, . . .}, and {y2, y3, . . .}
be the infinite sequences such that gi, hi, yi ∈ {0, 1}, i ≥ 2. Let us con-
sider the 2-state Mealy automaton sequence A = {Am, m ≥ 3} such that
Am belongs to Am and its automaton transformations are defined by the
numbers {g2, g3, . . . , gm−1}, {h2, h3, . . . , hm−1}, and {y2, y3, . . . , ym−1}.
Obviously, the automaton Am+1 is an expansion of Am for all m ≥ 3.
Therefore A has the limit automaton A∞ such that its automaton trans-
formations are defined by the following equalities:
f0 =
(
f0, f1, fg2 , fg3 , . . . , fgm−1 , . . .
)
(0, 0, 1, 2, . . . ,m− 2, . . .) ,
f1 =
(
f0, f1, fh2 , fh3 , . . . , fhm−1 , . . .
)
(1, 0, y2, y3, . . . , ym−1, . . .) .
Let us note, that all growth functions {γm, m ≥ 3} are different, and let
mi = i+ 2, i ≥ 1. It follows from Theorem 1 that the equalities hold
γAm
(m+ 1) = Φm+5 − Φ5 − (m− 1) = Φm+5 − (m+ 4),
γAm
(m+ 1) = Φm+5 − (m+ 1 + 2) = Φm+5 − (m+ 3),
whence Nmi
= mi, i ≥ 1, (in definitions of Section 1) and we have
γAm
(n) = γAm+1(n), 1 ≤ n ≤ m,
γAm
(n) < γAm+1(n), n > m.
Therefore, the limit growth function is defined by the equalities
γA(n) =
{
γA3(n), if 1 ≤ n < 3,
γAn+1(n), if n ≥ 3;
whence
γA(n) = Φn+4 − (n+ 2), n ≥ 1.
110 On sequences of Mealy automata and their limits
As the relations rp for p ≥ m follow from the relation (2.5) then it is
enough to choose in Sm the set of relations
Ri =
{
rp, 1 ≤ p ≤ m− 2; f2
1 f
m−1
0 = f0f1f
m−1
0
}
,
and these sets form the sequence
R1 ⊃ R2 ⊃ R3 ⊃ . . .
The set of defining relations of SA is defined by the equality
RA =
⋂
i≥1
Ri = {rp, p ≥ 1} .
It follows from Theorem 2 that any automaton B ∈ B can be con-
sidered as the finite limit of the sequence A. In this case, the finite limit
automaton exists.
3.2. Some remarks
The ideas and notions introduced in Section 1 require more attention.
There are appear many questions, that can be separated into the following
groups:
1. the development of constructing methods of Mealy automaton se-
quences such that the limit automaton and the finite limit automa-
ton exist;
2. the research of sequences of automatic transformation semigroup,
defined by Mealy automaton sequences, and research of correlation
between the semigroup defined by the limit automaton and the limit
of semigroup sequence;
3. the investigations of interrelation between sequences and finite limit
automata, the existence of these automata, and constructing meth-
ods of the finite limit automata.
References
[1] Reznykov, Illya I., On 2-state Mealy automata of polynomial growth, Algebra and
Discrete Mathematics, no.4., (2003), pp. 66–85.
[2] A.M. Bogomolov, I.S. Grunsky, The experiments with automata, Naukova dumka,
Kiev, (1973), 200 p.
[3] Vilenkin N. Ya., Combinatorics, Nauka, Moscow, (1969), 328 p.
I. Reznykov 111
Contact information
I. Reznykov 5, Krasnogvardeyskaya st., of. 2
02660, Kyiv
Ukraine
E-Mail: Illya.Reznykov@ikc5.com.ua
Received by the editors: 14.03.2005
and in final form 10.04.2007.
|