Groups of linear automata
The scalar automata as a special class of groups of linear automata over modules are introduced. The groups of scalar automata are classified.
Збережено в:
| Дата: | 2010 |
|---|---|
| Автор: | |
| Формат: | Стаття |
| Мова: | English |
| Опубліковано: |
Інститут прикладної математики і механіки НАН України
2010
|
| Назва видання: | Algebra and Discrete Mathematics |
| Онлайн доступ: | http://dspace.nbuv.gov.ua/handle/123456789/154875 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Groups of linear automata / A. Oliynyk // Algebra and Discrete Mathematics. — 2010. — Vol. 10, № 1. — С. 97–103. — Бібліогр.: 6 назв. — англ. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-154875 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-1548752019-06-17T01:31:51Z Groups of linear automata Oliynyk, A. The scalar automata as a special class of groups of linear automata over modules are introduced. The groups of scalar automata are classified. 2010 Article Groups of linear automata / A. Oliynyk // Algebra and Discrete Mathematics. — 2010. — Vol. 10, № 1. — С. 97–103. — Бібліогр.: 6 назв. — англ. 1726-3255 2000 Mathematics Subject Classification:20E08. http://dspace.nbuv.gov.ua/handle/123456789/154875 en Algebra and Discrete Mathematics Інститут прикладної математики і механіки НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
English |
| description |
The scalar automata as a special class of groups of linear automata over modules are introduced. The groups of scalar automata are classified. |
| format |
Article |
| author |
Oliynyk, A. |
| spellingShingle |
Oliynyk, A. Groups of linear automata Algebra and Discrete Mathematics |
| author_facet |
Oliynyk, A. |
| author_sort |
Oliynyk, A. |
| title |
Groups of linear automata |
| title_short |
Groups of linear automata |
| title_full |
Groups of linear automata |
| title_fullStr |
Groups of linear automata |
| title_full_unstemmed |
Groups of linear automata |
| title_sort |
groups of linear automata |
| publisher |
Інститут прикладної математики і механіки НАН України |
| publishDate |
2010 |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/154875 |
| citation_txt |
Groups of linear automata / A. Oliynyk // Algebra and Discrete Mathematics. — 2010. — Vol. 10, № 1. — С. 97–103. — Бібліогр.: 6 назв. — англ. |
| series |
Algebra and Discrete Mathematics |
| work_keys_str_mv |
AT oliynyka groupsoflinearautomata |
| first_indexed |
2025-07-14T06:56:31Z |
| last_indexed |
2025-07-14T06:56:31Z |
| _version_ |
1837604474888126464 |
| fulltext |
Algebra and Discrete Mathematics RESEARCH ARTICLE
Volume 10 (2010). Number 1. pp. 97 – 103
c© Journal “Algebra and Discrete Mathematics”
Groups of linear automata
Andriy Oliynyk
Communicated by V. I. Sushchansky
Abstract. The scalar automata as a special class of groups
of linear automata over modules are introduced. The groups of
scalar automata are classified.
1. The concept of a linear transformation of the infinite direct power of a
module, defined by an automaton, was introduces by Ahil Nerode in [1].
He considered the notion of a linear automaton in much wider context
than, for example, Samuel Eilenberg in [2, Chapter XVI]. In [3] linear
automata over finite fields and groups of such automata were considered.
The paper is organized as follows. Firstly we recall main definitions
concerning linear automata over modules. In this account we follow [2].
Then we introduce a special class of linear automata, so-called scalar
automata. In such automata the module of inner states is equal to the
module of letters and transition and output functions are the sums of
multiplications by elements of the layer ring. We classify in Theorem 1 the
groups of scalar automata. The proof is based on the technique presented in
[3, Proposition 4.1] and developed in [4, Theorem 4.1] and [5, Proposition
1], where, in fact, groups of some scalar automata were calculated. As
a corollary, we describe in Theorem 2 groups of linear automata over a
finite field whose space of states is equal to this field. These results may
be regarded as a contribution to the theory of self-similar groups ([6]).
2. Let R be a commutative ring with unit, R∗ its group of invertible
elements and M a nonzero module over R. Denote by Mn the direct
sum M ⊕ . . .⊕M
︸ ︷︷ ︸
n times
, n ≥ 1. Let M0 denotes the zero module. One have
2000 Mathematics Subject Classification: 20E08.
Key words and phrases: linear automaton, automaton group, wreath product.
98 Groups of linear automata
an isomorphic embedding of the module Mn into Mn+1 via w 7→ (w, 0),
w ∈Mn. Then we obtain the direct system
M0 →֒M1 →֒M2 →֒ . . . .
Its limit module will be denoted by M∗. Then M∗ =
⋃
∞
n=0M
n. The
module M∗ is naturally identified with R[t]-module M [t]:
M∗ ∋ (m0, . . . ,mn) 7→ m0 + . . .mnt
n ∈M [t], n ≥ 0.
Denote by Mi an isomorphic copy of module M , i ≥ 1. The direct product
∏
∞
i=1Mi will be denoted by M∞. This module is identified with R[[t]]-
module M [[t]] by the rule
M∞ ∋ (m0,m1,m2, . . .) 7→
∞∑
i=0
mit
i ∈M [[t]].
Then M∗ is a submodule of M∞ as an R[t]-module.
Definition 1. A linear automaton (a linear sequential machine as in [2,
p.408]) over M is a tuple
A = 〈Q,M,ϕ, ψ〉,
where Q is an R-module (module of states of A) and ϕ : Q ⊕M → Q,
ψ : Q⊕M →M are homomorphisms of R-modules (transition and output
functions of A).
The transition and output functions of the linear automaton A can
be extended inductively to the module Q⊕M∗ as follows
ϕ(q, 0) = q, ϕ(q, (w,m)) = ϕ(ϕ(q, w),m)
ψ(q, 0) = 0, ψ(q, (w,m)) = ψ(ϕ(q, w),m),
where q ∈ Q, w ∈ Q ⊕ X∗ and m ∈ M . Such extended functions are
homomorphisms of R-modules as well. A state p ∈ Q is called accessible
from a state q ∈ Q if there exist n ≥ 0 and w ∈Mn such that ϕ(q, w) = p.
Every state q ∈ Q defines an endomorphism fq of the R-module M∞
by the rule
fq((m0,m1,m2, . . .)) = (ψ(q,m0), ψ(q, (m0,m1)), ψ(q, (m0,m1,m2)), . . .).
The modules M∗ and Mn, n ≥ 0, are invariant under fq.
A. Oliynyk 99
Proposition 1. The endomorphism fq :M
∞ →M∞ is an automorphism
if and only if for each state p ∈ Q, accessible from q, the endomorphism
λq : M → M , defined by the rule λq(m) = ψ(q,m),m ∈ M , is an
automorphism.
Proof. It is a straightforward verification.
An endomorphism (automorphism) f :M∞ →M∞ is called linear au-
tomaton endomorphism (automorphism) if there exist a linear automaton
A and its state q such that f = fq. Using Proposition 1 one can show that
the automorphism inverse to linear automaton endomorphism is linear
automaton automorphism as well. Denote the set of all linear automaton
endomorphisms (automorphisms) of M∞ by EndLA(M
∞) (AutLA(M
∞)).
For two linear automata over M
A1 = 〈Q1,M, ϕ1, ψ1〉 and A2 = 〈Q2,M, ϕ2, ψ2〉
define their product A1 · A2 as a tuple
A1 · A2 = 〈Q1 ⊕Q2,M, ϕ, ψ〉,
where mappings ϕ : Q1 ⊕ Q2 ⊕M → Q1 ⊕ Q2, ψ : Q1 ⊕ Q2 ⊕M → M
are defined by the rules
ϕ((q1, q2),m) = (ϕ1(q1,m), ϕ2(q2, ψ(q1,m)))
ψ((q1, q2),m) = ψ2(q2, ψ(q1,m)).
These functions are indeed homomorphisms of R-modules. Hence, a prod-
uct of linear automata over M is a linear automaton over M as well. One
can directly verify that for arbitrary states q1 ∈ Q1 and q2 ∈ Q2 the
equality fq2(fq1) = f(q1,q2) holds. This equality immediately imply that
the set EndLA(M
∞) is closed under superposition. Moreover, one can
show that EndLA(M
∞) is closed under addition ([2, Proposition 6.1]).
This means that the following proposition holds.
Proposition 2. The set EndLA(M
∞) form a subring in the ring of
endomorphisms of M∞. The set AutLA(M
∞) form a group of units of
EndLA(M
∞).
A linear automaton A = 〈Q,M,ϕ, ψ〉 is called permutational if for
each state q ∈ Q the mapping fq is an automorphism. The group G(A)
of an invertible automaton A is the subgroup of AutLA(M
∞), generated
by the set {fq : q ∈ Q}.
100 Groups of linear automata
3. Let us fix a module M over a commutative ring with unit R. A linear
automaton A = 〈Q,M,ϕ, ψ〉 will be called scalar if Q = M and there
exist α1, α2, β1, β2 ∈ R such that
ϕ(q,m) = α1q + α2m, ψ(q,m) = β1q + β2m (1)
for arbitrary q ∈ Q,m ∈M . It is easy to see that this scalar automaton
is permutational if and only if the element β2 is invertible in R.
For an element r ∈ R let us denote by rM the image of the module
M under the scalar endomorphism r · id of M . For an invertible r ∈ R we
will use notation 〈r〉 for the cyclic subgroup of R∗ generated by r.
Theorem 1. Let A = 〈Q,M,ϕ, ψ〉 be a permutational scalar automa-
ton over M whose transition and output functions are given by (1) for
α1, α2, β1 ∈ R, β2 ∈ R∗. Then the group G(A) is isomorphic to:
1. the group 〈β2〉 provided β1 = 0;
2. the wreath product 〈β2〉 ≀ (β1M,+) provided β1 6= 0, α2 = 0 and the
order of β2 in R∗ is finite;
3. the restricted wreath product Z ≀̄ (β1M,+) provided β1 6= 0 whereas
α2 6= 0 or the order of β2 in R∗ is infinite.
Proof. Let us fix a series m(t) ∈M [[t]],m(t) =
∑
∞
i=0mit
i. First of all for
arbitrary q ∈ Q we calculate the image m(t)fq . From the definition of
output function we have the equality
m(t)fq = β1mq(t) + β2m(t),
for mq(t) ∈M [[t]],mq(t) =
∑
∞
i=0 qit
i such that
q0 = q, qi+1 = ϕ(qi,mi) = α1qi + α2mi, i ≥ 0.
Then by induction on i we obtain the equality
qi+1 = αi+1
1 q + α2
i∑
j=0
α
i−j
1 mj , i ≥ 0.
Therefore
m(t)fq = β1q + β1
∞∑
i=0
αi+1
1 q + α2
i∑
j=0
α
i−j
1 mj
ti+1 + β2m(t) =
A. Oliynyk 101
β1q
∞∑
i=0
αi
1t
i + β1α2t
∞∑
i=0
i∑
j=0
α
i−j
1 mj
ti + β2m(t) =
β1q(1− α1t)
−1 + β1α2t
∞∑
i=0
i∑
j=0
α
i−j
1 ti−jmjt
j
+ β2m(t) =
β1q(1− α1t)
−1 + β1α2t(1− α1t)
−1m(t) + β2m(t) =
m(t)
(
β2 + β1α2t(1− α1t)
−1
)
+ β1q(1− α1t)
−1.
Since β2 ∈ R∗ the series P (t) = β2 + β1α2t(1 − α1t)
−1 is invertible in
M [[t]].
Let now β1 = 0. Then m(t)fq = m(t)β2, q ∈ Q, and the group G(A)
is isomorphic to the cyclic group generated by the scalar endomorphism
β2 · id of M . Since β2 ∈ R∗ and M 6= 0 the latter group is isomorphic to
the subgroup 〈β2〉 of M∗ and we obtain the first statement of the theorem.
Assume in the sequel that β1 6= 0. Then
m(t)fq = m(t)P (t) + β1q(1− α1t)
−1, q ∈ Q.
This implies
m(t)f
−1
q = m(t)P (t)−1 − β1P (t)
−1q(1− α1t)
−1, q ∈ Q.
In particular, m(t)f0 = m(t)P (t) and m(t)f
−1
0 = m(t)P (t)−1.
For each q ∈ Q, denote by hq the product f−1
0 fq. This product act as
follows
m(t)hq = m(t) + β1q(1− α1t)
−1.
Then the set H = {hq : q ∈ Q} form a subgroup of G(A). This subgroup
is isomorphic to the additive group (β1M,+) of the R-module β1M . The
group G(A) is generated by H and f0. Denote by Hi, i ≥ 1, the isomorphic
copy of H.
For arbitrary k ∈ Z we have
m(t)f
−k
0
hqf
k
0 =
(
m(t)P (t)−k
)hqf
k
0
=
(
m(t)P (t)−k + β1q(1− α1t)
−1
)fk
0
=
m(t) + β1q(1− α1t)
−1P (t)k, q ∈ Q.
Denote by W the normal closure in G(A) of the set {f−k
0 hqf
k
0 : k ∈ Z, q ∈
Q}. We will show, that depending on the order of the series P (t) in M [[t]]∗,
the group W is finite or infinite direct sum of H.
102 Groups of linear automata
Let α2 = 0. Then P (t) = β2. Assume that β2 has finite order equal to
k in R∗. Then the orders of P (t) in M [[t]]∗ and the subgroup C = 〈f0〉
are k as well. The subgroup W in this case consists of the transformations
w acting by the rule
m(t)w = m(t) + β1(1− α1t)
−1
k−1∑
i=0
qiβ
i
2,
where qi ∈ Q, 0 ≤ i ≤ k − 1. This means that the intersection of W and
C is trivial and
W =
k−1⊕
i=0
Hi.
The subgroup C acts on W via conjugation, cyclically permuting compo-
nents of each their element:
m(t)f
−1
0
wf0 = m(t) + β1(1− α1t)
−1
k−1∑
i=0
qiβ
(i+1) mod k
2 , w ∈W.
Hence, the group G(A) splits into the semidirect product W ⋊ C which
isomorphic to the wreath product 〈β2〉 ≀ (β1M,+).
Let α2 6= 0 or the order of β2 in R∗ is infinite. In both cases the
orders of P (t) in M [[t]]∗ and the subgroup C are infinite as well. Each
transformation w ∈W has the form
m(t)w = m(t) + β1(1− α1t)
−1
+∞∑
i=−∞
qiβ
i
2, qi ∈ Q, i ∈ Z,
where all but finite number of qi’s equals 0. This implies that the intersec-
tion of W and C is trivial and
W =
+∞⊕
i=−∞
Hi.
The subgroup C acts by translations on W via conjugation:
m(t)f
−1
0
wf0 = m(t) + β1(1− α1t)
−1
+∞∑
i=−∞
qiβ
(i+1)
2 , w ∈W.
Hence, the group G(A) again splits into the semidirect product W ⋊ C
which isomorphic to the restricted wreath product Z ≀̄ (β1M,+). The
proof is complete.
A. Oliynyk 103
Let now Fq be a finite field, q = pn, p — prime, n ≥ 1. Consider Fq as
a regular module over itself.
Theorem 2. Let A be a linear automaton over Fq such that its module
of states is equal to Fq. Then the group G(A) is isomorphic to one of the
following groups:
1. the cyclic group Zm, where m|(q − 1);
2. the wreath product Zm ≀ Zq, m|(q − 1), m 6= 1;
3. the lamplighter group Z ≀̄ Zq.
Proof. Note, that linear automata mentioned in the theorem are indeed
scalar automata. The result now implies from Theorem 1 and cyclicity of
the group F
∗
q .
References
[1] A. Nerode, Linear automaton transformations. Proc. Amer. Math. Soc., 9, 1958,
541–544.
[2] S. Eilenberg, Automata, languages, and machines. Vol. A. — New York : Academic
Press, 1974, 446 p.
[3] R. I. Grigorchuk, V. V. Nekrashevich, V. I. Sushchanskii, Automata, dynamical
systems, and groups, Tr. Mat. Inst. Steklova, 231 (Din. Sist., Avtom. i Beskon.
Gruppy):134–214, 2000.
[4] P. V. Silva, B. Steinberg, On a class of automata groups generalizing lamplighter
groups. Internat. J. Algebra Comput. 15, 2005, 1213–1234.
[5] L. Bartholdi, Z. Šunić, Some solvable automaton groups, Contemporary Mathe-
matics 394, 2006, 11–29.
[6] V. V. Nekrashevych, Self-similar groups, volume 117 of Mathematical Surveys and
Monographs, American Mathematical Society, Providence, RI, 2005.
Contact information
A. Oliynyk Department of Mechanics and Mathematics
Kyiv Taras Shevchenko University
Volodymyrska, 60
Kyiv 01033
E-Mail: olijnyk@univ.kiev.ua
URL: http://algebra.kiev.ua/oliynyk/
Received by the editors: 31.10.2010
and in final form 31.10.2010.
|