D?m?si P., Nehaniv C.L. Algebraic Theory of Automata Networks. An Introduction
Подождите немного. Документ загружается.
3.3.
Homomorphically Complete
Classes
Under
the
Quasi-Direct Product
101
To
prove this fact,
we
consider
a
game similar
to
that
in the first
part
of
Section 2.1:
let us
place
n
—
1
coins
c,
onto
the
vertices
1',...,
(n
—
1)' so
that
c, is
placed onto i'.lt
is
sufficient
to
prove that every pair
of
coins
can be
interchanged
so
that
the
others
get
back
to
their initial locations.
We can
restrict ourselves
to the
case that
c\ and ci are the
coins
to
be
interchanged.
Let us first
move
c\ to n' in
four
steps along
the
path 1'lOnn'; meanwhile
all
other coins
are
rotated around
the
cycles
i'li',
i =
2,...,
n
—
1,
since there
are no
loop
edges.
After
this transformation
we see
that
c\ is on n', and for
every
i =
2,...,
n — 1,
c,-
is
back
on
vertex
i'.
Next,
in a
similar way, move
ci to 1'
along
the
path
2'2011'
and
rotate
the
coins
c\,c3,...,
c
n
-\ around
the
cycles n'nn',
3'33',...,
(n
—
l)'(n
—
l)(n
—
1)',
respectively.
Now the
placement
of the
coins
is
this:
c\ is on the
vertex
n',
GI
is on 1', and
for
/ =
3,...,
n
—
1, c, is on /'.
Finally, with
a
similar procedure, move
c\ to 2' so
that
all
the
coins
c, get
back
to i', i =
3,...,
n
—
1, and ci
gets back
1'.
This completes
the
proof
that
JC
satisfies (2).
To
see
that
k = [A
n
\ n > 2}
does
not
satisfy
(1) we
show that
for
every ai-product
B of
factors
from
JC,
none
of the
counters
of
length greater than
2 can be
represented
homomorphically
by B.
Assume
to the
contrary that there
is
such
a
counter.
By
Propositions
2.59
and
3.20, there
are a
single-factor product
A =
(A
n
,
X, 8) = A
n
(X,
(p),
distinct states
a\,
...,<zjt
€
A
n
,k
3,
andaword
u € X*, \u\ = 2,
with (ai,u)
=
ai,...,
8(ak-i,
u) =
ak,
8(ak,
w)
= a\. Put u —
jcy.
If a\ = i',
then
ai = 0 and a3 = /
with
j '. But
then (a
3
,u)
{0,
j'},
a
contradiction.
If a\ = i
with
i 0,
then
02 = j so
that
j
i, j
{1,...,
n}. We see
that
(i, x) = 0, and
whether 8(j,
x) = 0 or
(j,x)
= j',
we
have
ai = a$, a
contradiction.
The
last case
is
that
a\ = 0. But
then clearly
02 = i' for
some
i
{1,...,
n} and
either
a3 = a\ or a$ = ai,
completing
the
proof.
Cl
The
following problem remains open.
Problem 3.38. Does
there
exist
a
minimal
homomorphically
complete
class
of
automata
under
the
a\-product?
3.3
Homomorphically
Complete
Classes
Under
the
Quasi-Direct
Product
Recall that
a
quasi-direct product
of
automata
is a
special type
of the
general product
such
that
the
feedback
functions
of the
component automata
are
really independent
of
the
state components. Therefore,
a
quasi-direct product
of
automata
At —
(A
t
,
X
t
, ,), t =
1,...,
n, can be
given
as an
automaton
A = (A, X, 8) =
A
t
(X, ,...,
<p
n
)
with
A =
AI
x • • • x A
n
and8((ai,...,
a
n
),
x) =
(8i(ai,
(x))
t
...,
8
n
(a
n
,
(p
n
(x))),
(a\,...,
a
n
)
A,
x € X
(where
the
feedback functions
: X ->
X
t
,t
=
1,...,
n, do not
depend
on the
state variables).
The
following statement
is
obvious.
Proposition
3.39.
The
quasi-direct
product
of
automata
A
t
=
(A
t
,
X
t
, 8
t
)
given
by X and
:
X -> X
t
, t =
1,2,
is
isomorphic
to the
quasi-direct
product
of
automata
AI and A\
given
by X and
<p2,<pi-
n
Next
we
prove
the
following theorem.
102
Chapter
3.
Krohn-Rhodes
Theory
and
Complete
Classes
Theorem
3.40.
There
exists
no
minimal complete class
of
automata
with
respect
to
homo-
morphic
representations
under
the
quasi-direct
product.
Proof.
Consider
an
arbitrary complete class
k of
automata with respect
to
homomorphic
representations under
the
quasi-direct product.
It is
enough
to
show that
for
every automaton
A = (A, X',
8A),
the
class
K \ {K}
also
is a
complete
class
of
automata with respect
to
homomorphic representations under
the
quasi-direct product.
Let A = {a\
,...,«„}
and
take
two
distinct symbols
X0,
x\ X'.
Consider
an
automa-
ton
B = (B, X,
B
) for
which
B =
{1,...,
n
2
+ 1}, X = X' U
{x
0
, xi}; moreover,
for all
b
e B and x X,
Consider
a
subautomaton
B" =
({1,...,
n}, X',
8'
B
)
of B. It is
clear that
B" is
iso-
morphic
to A.
Therefore,
for our
theorem
it is
enough
to
prove that
B can be
represented
homomorphically
by an
appropriate quasi-direct product
of
automata
from
k \
{A}.
It can
be
seen that
B
satisfies
the
following condition:
(1)
For
every
b, c e B
there exists
ape X
+
with
8&(a,
p) =
8&(b,
p).
Indeed,
in
case
b = c
this
is
obvious.
Now let b ^ c.
Using
the
definition
of
,
we
have that
by b < c, p =
(xiXQ
-l
y-
b
and,
similarly,
by b > c, p =
x£
+l
-
c
(xix£-
l
)
b
-
c
satisfy
condition
(1).
We
show that
for all
distinct states
a/,
aj•
e A of A and
also
for
every word
p'
0
=
x{...
x'
t
,
x(,...,
x'
t
e X'
satisfying
<$B(a,,
p') =
SB
(a/,
p'),
there exists
a
word
p €
[x(,...,
x'
t
Y such that 65(0,,
p) =
SB(OJ,
p) and \p\ < n(n — 1).
Indeed, assume that
for an
appropriate index
r, 1 < r < t,
there exists
an s, 1 < s <
t
—
r,
such that
(a,<,
x{...
x'
r+s
)
=
%(o,,
x{...
x'
r+s
)
=
SB(OJ,
x{...
x
f
r
).
Then,
by the
input
word
x'
r+s+l
...
x'
t
,
S
B
(a,,
x{...
x'
r+s
x'
r+s+l
...
x'
t
)
=
8
B
(a
i
,x'
l
...
x'
r
x
f
r+s+l
...
x'
t
)
and
8s(aj,
x{...
x'
r+s
x'
r+s+l
...
x'
t
}
=
8B(aj,x{...
x'
r
x'
r+s+l
...
x'
t
}. Consequently,
the
word
p
can
be
constructed such that
its
length does
not
exceed
the
number
of
pairs
(a
r
,
a
s
)
A
x A, a
r
^ a
s
.
Thus,
\p\ < n(n — 1)
holds.
Let
Dt,
=
(D
t
,
X
t
,
f
), t =
1,...,
m, be
finite
automata having
an
index
t
{1,...,
m}
with
D
t
= A.
Suppose that
a
quasi-direct product
M. = , • • • m} can be
given
such that
it
homomorphically represents
B. By
Proposition 2.52,
we may
also assume
thatjVfhasastate-subautomatonA/'
=
(N,X,
)
with
a
state-homomorphism
: N B
onto
B.
(And then
Y = X.)
Assume that
A/"
is
minimal
in the
sense that
B is not a
state-
homomorphic image
of a
proper
state-subautomaton
of M. By the
definition
of SB, B is
strongly
connected. Thus, using Proposition 2.25,
N is
also strongly connected. Because
of
Proposition 3.39,
we can
assume that either every
D
t
, t =
I,...,
m, is
equal
to A or
there
exists
an
index
k €
{1,...,
m}
such that
A £
[D
1
,..., D
k
},
but A =
D
k+
\
= •• • = D
m
.
Especially, thus
D
m
= A
necessarily holds. Since
|A| <
|B|,
by the
assumption that
M.
state-homomorphically represents
B, it
follows that
m > 1.
3.3.
Homomorphically Complete
Classes
Under
the
Quasi-Direct Product
103
Consider
the
quasi-direct product
Mi =
D
t
(X,<pi,...,
m
-\).
We now
show
that
for all
pairs
(d\,...,d
m
-i,a,-), (d\,...,d
m
-i,aj)
e N,
t{r((d]_,...,d
m
-i,a,))
=
i}r((d\,...,
d
m
-\,
dj)),
i.e.,
the
homomorphism
^ is
independent
of the
last
factor
of the
quasi-direct product
M.
To
this,
first we
assume
the
contrary
of
this statement,
i.e.,
for a
suitable pair
of
states
(d1,...,
d
m
-i,a
{
),
(di,..., d
m
-i,
aj) € N,
suppose that
\j/((di,...
,d
m
-i,ai))
•ft
((d\,...,
d
m
-i,
dj)). Then,
by the
definition
of SB,
there
exists
a
positive integer
t
such
that
8s(
((di,...,
d
m
,ai)),
XQ)
= n + 1
and, using again
the
definition
of SB, and
taking
into consideration
((d\,...,
d
m
-\,
ai,))
((di,...,
d
m
-i,
dj)),
we
obtain
However, using that
for
every
b, c e B
there exists
a p e X
+
having
8
B
(b,
p) =
8
B
(c,
p), we
obtain
the
existence
of a
word
q X
+
with 8
B
(\js((di,
...,d
m
,
ai)),
) —
SB(
((di,...,
d
m
,
aj)),
x'
0
q). Since
JV is
strongly connected,
an r e X
+
can be
found
such
that8tf((di,
...,d
m
,
a,-),x*
Q
qr}
=
((di, ...,d
m
,ai),
)-
Hence, ((d1,..., dm), x'
0
qr)
=
S
Ml
((d\,...,
d
m
),
X'Q),
where
5^,
denotes
the
transition
function
of the
quasi-direct product
MI .
On
the
other hand, using,
in
order,
and
we
get
For
every
u =
1,...,
m we
extend
the
function
u
: X -+ X
u
to X
+
such that
for all
x'
lt
...,x'
k
X,
u
(x{...x'
k
)
=
u
(x{)...(p
u
(x
f
k
).
Continuing
the
proof, that
t/f((di,...,
d
m
-i,di))
=
^f((d\,...,
d
m
-i,aj))
holds
for
all
pairs
(d\,...,
d
m
-\,«,-),
(d\,...,
d
m
-i,Oj)
e N, we
show that
(2)
for
every positive
integers
and r' e X
+
,
8
A
(aj,
Vm^r'))
^
8
A
(a
jt
^(x^qrYr')).
Indeed,
by
virtue
of
<5
B
(^((di,...,
d
m
,
a
;
)),
x'
0
qr)
=
8
B
(if((di,
...,d
m
,
a,-)),
x'
Q
)
=
n
+ 1 and
8*f((di,
...,d
m
,a,),x'
Q
qr)
=
8j^((di,
...,d
m
,a
(
),x'
0
),
we get
8
B
(^((di,...,
d
m
,aj)),
X
'
0
(qr)
z
)
=
S
B
W((di,... ,d
m
,
ai)),xl(qr)*-
1
)
= ••• =
8
B
W((di,...
,d
m
,
a
i
)),x
t
0
)=n
+ l.
Consequently, because
of
8&(\ls((d\,
...,d
m
,
a,-)),
XQ)
= n + 1 ( ((
i,...,
dmtOj)),
X'Q),
8
B
(ir((di,...,
d
m
,dj)),
X'Q)
^ n + 1 =
8
B
(\(f(di,
...,d
m
,
a,-), x'
0
(qr)
z
).
Thus, according
to the
definition
of 8
B
, for
every word
r' € X
+
with
\r'\ <n(n
— 1)
we
have ((d
1
,
...,
)),
*{r')
£
«
B
(^((rfi,
...,*,,
fly)),
x
f
0
(qr)
z
r').
Simultaneously,
by
SMI
(d1.
• • •. ). ) =
5
M.
(Wi»
• • •. ) )
(
wnere
5
M,
denotes
the
transition
function
of the
quasi-direct product
MI),
it
follows that
for
every
inputwordr
//
6X
+
of
M
1,
((d1,...,J
m
),
r") =
1
((
1
<k), JcJfoiOV).
104
Chapter
3.
Krohn-Rhodes Theory
and
Complete
Classes
From this,
by the
substitution
r" = r', we
obtain 8
u
(d
u
,
<p
u
(xQr'})
=
8
u
(d
u
,
<p
u
(xQ(qryr')),
u =
1,...,
m — 1,
where
5,
denotes
the
transition function
of the fth
factor
T>
t
of the
quasi-direct product
M\.
Hence,
by
&t3(ilr((d\,...,
d
m
,
a;)),
jc^r')
^
8BW((di,
...,d
m
,
ay)),
x'
0
(qr)
z
r")
we
have
8
A
(a
jt
<p
m
(x
f
Q
r'))
£
SA(<*J,
<p
m
(4(tfr)V)),
that
is, for
every input word
r' e X
+
with
\r'\
< n(n — 1),
8
A
(aj,
<p
m
(xQ)<p
m
(r'))
^
SA(<*J,
<Pm(Xo)((p
m
(qr)Y
m
(r'}} holds.
Now
we
suppose that there exists
a
word
r" e X
+
for
which
8
A
(aj,
<p
m
(XQ)^
(r"))
=
A(aj,<pm(x
t
)(Vm(qr))
z
m
(r"')).
As we
have already established, then there exists
such
a
word
r" e X
+
having
|r"|
< n(n — 1),
contradicting
8
A
(aj,(
m
(x
)(p
m
(r'))
^
SA(<*J,
Vm(J$)(<Pm(qr»
z
9m(r'»,
r' e X*,
|r'|
< n(n - 1).
Herewith
it is
proved that
SA(OJ,
p
m
(xo)0m(
r
'))
^
8
A
(aj,
<p
m
(xQ)(<Pm(qr)y<Pm(r'))
and5^t(a
;
,
))
(fl
;
,
<p/n(Xo(#
r
)
Zr
)) for
every
r' X
+
hold
and
this implies (2).
Because
of
8
A
(a
jt
<p
m
(x'
0
r'))
/ (
;
,
<Pm(xQ(qrYr')),
by
choosing
r' =
(qr)
k
,
we
have
that
for
every pair
z, k > 0,
8
A
(aj,
<p
m
(xQ(qr)
k
))
^
8
A
(aj,
(p
m
(xQ(qrY
+k
)).
Thus
the
elements
8
A
(a
h
(p^qr)),
8
A
(dj,
^(x^qr}
2
)},...,
SA(OJ,
(p
m
(x
t
0
(qr)
n+l
))
are
distinct
states
of
A
contradicting
the
assumption
| A | = n.
This contradiction shows that
for
every pair
(di,...,d
m
-i,ai),(di,...,d
m
-i,aj)
e N,
(O/i,... ,d
m
_i,a
(
))
= ty((d\,...
,d
w
-i,
a
;
)), that
is, i/f is
independent
of the
last
factor
of the
quasi-direct product
M.
By
this
fact,
we
prove that
M. i
homomorphically represents
B. To
this, take
the
subset
N' c DI x • • • x
D
m
_i
of the
state
set of M.\
consisting
of all
elements
(d\,...,
d
m-1
)
e
D\ x • • • x
D
m
_i
for
which there exists
an a
t
e A
such that
(d\,...,
d
m
-\ ,a
t
)
N
holds.
Consider
the
mapping
ty'
defined
by
\lf'((d\,...,
d
m
-\)}
= (( • • •
>
d
m
-\,a
t
y)
for all
(d\,...,
d
m-1
)
N',
where
a
t
A, is an
arbitrary state such that
(d\,..., d
m
-\,
a
t
) 6 N.
It is
clear that
the
mapping
\jf'
is
well
defined
according
to the
fact
that
for
every pair
(di,...,d
m_1
,fl,-),
(di,...,d
m
-i,aj)
€ N,
ilr((di,...,d
m-1
,a
i
))
=
((di,..
.,d
m
-i,
fl
;
)).
By
an
easy computation
we
obtain that
V' is s
homomorphism
of a
subautomaton
N' =
(N',
X,
N'
) ofM
onto
B.
Therefore,
if the
automaton
B can be
represented homomorphically
by a
quasi-direct
product
M
having
t
factors equal
to A,
then
B can be
represented homomorphically
by a
quasi-direct product
M.\
having
£.
—
1
factors equal
to A,
too.
If
D
m-\
= A,
then, similar
to
M i, we can
construct
a
quasi-direct product
M.2 = • • •
m-2)
such that
5
can
be
represented homomorphically
by
A^2
and M2 has
£—2
factors equal
to A
Repeating
this procedure,
finally we get a
quasi-direct product
M
m
-k
=
FIf=i
A(X
^>i,...,
^>jt)
which
homomorphically represents
B and
V\,...,
T>k
€
/C
\
{^4}.
Consequently,
/C
\
{^4}
is
also
a
complete class with respect
to the
homomorphic representation under
the
quasi-direct
product
and
this completes
the
proof
of our
theorem.
3.4
Homomorphically
Complete
Classes
Under
the
Cascade
Product
The
following statement
is a
direct consequence
of
Theorem 3.1.
Lemma 3.41.
Let
K,bea
class
of
automata
having
fewer
states than
an
appropriate
prime
number
p and let C be a
counter with
p
number
of
states.
Then
C
cannot
be
represented
homomorphically
by a
cascade product
of
factors
from
1C.
3.4. Homomorphically Complete
Classes
Under
the
Cascade Product
105
The
next statement
is
obvious.
Lemma
3.42.
Let
Cbea
nontrivial counter
and
take
a
cascade product
M. = (Mi x • • • x
M
n
, X, 8)
of
automata
M
t
=
(M
t
,
X
t
,
8
t
),
t —
1,...,
n,
with
the
following properties:
(1) C can be
represented homomorphically
by M..
(2)
There
exists
a
positive integer
k and a fixed-state m of an
appropriate
M
s
, s
{1,...,
n},
such that
8((mi,...,
m
n
),
x
k+£
)
e MI x • • • x
M
s
_1
x {m} x
M
s
+\
x
•
• • x M
n
,
(m1,...,
m
n
) € MI x • • • x M
n
, x € X, t = 0, 1,
Then
C can be
represented homomorphically
by a
cascade product
of
factors
Mi,...,M
s
-i,M
s+
i,...,M
n
.
Now
we
prove
the
following.
Lemma
3.43.
LetC
= (C,
{xc},
8c) be a
nontrivial counter
and let k be a
class
of
automata
such that
(1)
C can be
represented homomorphically
by a
cascade product
of
factors from
/C,
(2) N € k
implies that
C
cannot
be
represented homomorphically
by a
cascade product
of
factors from
K \
{N}.
Then
for
every automaton
A=(A,
XA, A)
there exists
an
automaton
B=(B,
X
B
, )
and
a
nontrivial counter
D = (D,
{X
D
},
) as
follows:
(3) B is a
two-degree weakly nilpotent automaton.
(4) A and D can be
represented homomorphically
by a
cascade product
of
components
from
K, U
{B}.
(5) D
cannot
be
represented homomorphically
by a
cascade product
of
factors from
/C.
(6)
If
any
nontrivial counter
£ can be
represented
homomorphically
by a
cascade product
of
factors from
(K \
{N}}
U {B} and
A/"
e /C,
then
£ can be
represented homomor-
phically
by a
cascade product
of
factors from
k \
{N}.
Proof.
Denote
p a
prime number
for
which every
element
of K has
fewer
states
than
p.
Construct automata
D =
({!,...,
p],
{*£>},
<$£>)
and B = (B, X
B
, B) in the
following way.
Set
moreover,
let B
with
and
Obviously,
and
Thus,
(3)
holds.
106
Chapter
3.
Krohn-Rhodes
Theory
and
Complete
Classes
To
(4), take
a
cascade product
of
factors
from
K and
let N = (N,
{x
c
},
) be a
(state-)subautomaton
of N
having
a
(state-)homomorphism
:
N --> C
onto
C.
Because
of (1)
there exists such
an N,
obviously. Denote
(C
0
,
X
0
) a
fixed
element
of C x X
A
and
construct
the
ao-product
M. =
with
M
n+i
= B as
follows:
For
any
state
(m
1
,...
,m
n
,(c,a,
d)) and
input letter
x of M. let
and
Take
the
subset
M' of
state
set of M
with
M' =
{(m
1
,...,
m
n
, (c, a, d)) \
(m
1
,...,
m
n
, (c, a, d)) € N, (c, a, d) B \
{(a
0
,
a
0
,
a
0
)},
(m
1
,...,
m
n
) = c}. By an
easy com-
putation
we get
that
: M' -> A
with
((m
1
,
...,m
n
,(c,a,d)))
= a is a
state-
homomorphism
of a
suitable state-subautomaton
of M.
(with state
set M')
onto
A
Take
an
arbitrary
fixed
element
x
A
of X
A
and let be a
cascade product,
for
which
(m
1
,...,
m
n
, (c, a, d), xc) =
(m
1
,
• • •, m
n
, (c, a, d),
X
A
),
t =
1,...,
n + 1,
holds
for
every state (mi,...,
m
n
, (c, a, d))
of
M.'.
It can be
easily
shown
that
: M' -> D
with ((m
1
,...,
m
n
, (c, a,
d)))
= d is a
state-homomorphism
of
an
appropriate state-subautomaton
of M!
(with state
set M')
onto
D.
This ends
the
proof
of
(4).
In
consequence
of
Lemma 3.41
we
receive (5).
To
(6) let us
take
a
cascade product
M = (M
1
x • • • x M
n
, X, ) = ,
,...,
of
factors
M
t
=
(M
t
,
X
t
, ), t =
1,...,
n,
from
(K \
{N})
U {B} and
suppose
that
a
nontrivial counter
C' can be
represented homomorphically
by M.
Obvi-
ously,
by M
1
= B the
first
components
of
states ((m
1
,...,
m
n
),x
2+i
),
(m
1
,... ,m
n
)
e
M
1
x • • • x M
n
, x e X, e = 0,
1,...,
are
equal
to
(a
0
,,
a
0
,
a
0
).
Thus,
by
Lemma 3.42,
we
can
suppose
M
1
B.
Let
s, 2 < s < n, be the first
index
(if it
exists) with
M
s
= B. By (2) we
obtain that
C
cannot
be
represented homomorphically
by a
cascade product
of
factors
M
1
,...,M
s-1
•
Consequently,
for
every pair
c e C,m M
1
X---x
M
n
and
input letter
x X
there
exist positive integers
k
1
, k
2
such that
the first 5
—
1
factors
of (m,
x
kl
)
and
SM
(m,
x
k2
)
coincide
but .
Then either
the sth
factor
of
(™,
x
kl+l
)
or the
sth
factor
of (m,
x
k2+l
)
coincides with
(a
0
,
a
0
,
a
0
).
Obviously, then
the 5th
factor
of
(m,
X
max
(*i.*2)+^)
)
i — i
2,...,
coincides
with
(OQ,
OQ,
ao). Therefore, there exists
a
positive
integer
k,
such that
for
every state
m and
input letter
of M., the 5th
factor
of
&M
(m, x
k
)
coincides with
(a
0,,
a
0
,
a
0
).
Then, using Lemma 3.42,
we can
suppose
M
s
B.
Repeating this procedure
we
have that
C' can be
represented homomorphically
by a
cascade
product
of
factors
from
K \ N.
This
ends
the
proof
of
Lemma 3.43.
n
Lemma 3.44. Assume
that
for
a
given
finite
list
C
0
,
...,
C
j
of
nontrivial
counters
there
canbe
found
a finite
list
B
1
,...,
B
j
,
B
i+1
, ...,
B
i+j
of
automata
having
the
following
properties:
(1) For
arbitrary
k
{0,...,
j], C
k
can be
represented
homomorphically
by a
cascade
product
of
factors
from
{B
1
,...,
B
i+k
}.
3.4.
Homomorphically Complete
Classes
Under
the
Cascade
Product
107
(2)
ByN
(B\,...,
B
i+k
},
k =
0,...,
j,
none ofCk,..
-,
Cj
can be
represented
homo-
morphically
by a
cascade
product
of
factors
from
(B\,...,
Bt+j
}\N.
Then
for
every
automaton
A
there
exists
an
automaton
Bt+j+i
and a
nontrivial
counter
Cj+i
as
follows:
(3)
Bi+j+i
is a
two-degree
weakly
nilpotent
automaton.
(4) A and
Cj+i
can be
represented
homomorphically
by a
cascade
product
of
factors
from
(5)
IfJ\f
€
{Bi,...,
Bi
+
k},
k =
0,...,
j+1,
then none
of
Ck,...,
Cj+1
can be
represented
homomorphically
by a
cascade
product
of
factors
from
{B\,...,
Bi+j+1]
\{N}.
Proof.
Considering
/C =
(B\,
. . . ,
Bi+j;}
and C = Cj, we
obtain conditions
(1) and (2) of
Lemma
3.43. Then, using
the
notation
#,•+_/+!
= B and
Cj+1
= D, it can be
assumed that
properties
(3)-(6)
of
Lemma 3.43
are
satisfied. Because
of (3) and (4) of
Lemma 3.43,
we
can
see the
validity
of (3) and (4)
directly.
It
remains
to
show (5).
Suppose that
to the
contrary
of our
statement,
for an
appropriate
k,0 <k < j + l, and
A/"
€
{Bi,
. . . ,
Sj+jt},
the
counter
Ci,
k t <
j+l,
can
be
represented homomorphically
by
a
cascade product
of
factors
from
[B\ , . . . ,
Bi+j+i
}
\
{.A/"}-
Then, using
(6) of
Lemma 3.43,
Ct
can
be
represented homomorphically
by a
cascade product
of
factors
from
{B\
, . . . , B
i+j
} \
N
By
(5) of
Lemma 3.43, then
t = j + 1,
that
is, C
t
= D
does
not
hold.
But t < j + 1
contradicts (2). Therefore,
(5)
holds
necessarily.
Thus
our
Lemma 3.44
is
true.
D
Theorem 3.45.
Let C be a
nontrivial counter
and let K, be a finite set
of
automata
such
that
C can be
represented
homomorphically
by a
cascade
product
of
factors
from K, and
for
every
N
1C
the set K, \
{.A/"}
does
not
preserve this
property.
Then
it can be
found
an
enumerable
set
1C\
of
two-degree
weakly
nilpotent
automata such
that
K, U K,\ is a
minimal
homomorphically
complete
class
under
the
cascade
product.
Proof.
Take
a set F of
automata such that
the
elements
of F are
pairwise
not
isomorphic
and
for
every automaton
A
there
exists
a B e F
such that
A is
isomorphic
to B. It can be
easily
seen that
F is
enumerable. Take
an
arrangement
F =
[A\,
AI, . . .} of
this enumerable
set
and
construct
the set
K,\
=
(B\
, BI, . . .} of
two-degree weakly nilpotent automata
and the
set
K,2
=
{Ci,
€2, . . .} of
nontrivial counters such that
(1)
every
At e F and
C,-
€ £2, i = 1, 2, . . . , can be
represented homomorphically
by a
cascade product
of
factors
from
JC
U /Ci ;
(2)
if N K,
then none
of
elements
of
{C}
U £2 can be
represented homomorphically
by a
cascade product
of
factors
from
(/C U /CO \
{N};
(3)
if
BI
e
/Ci
, i =
1,2,...,
then none
of
elements
of {C, ,
C,+i
, . . .} can be
represented
homomorphically
by a
cascade product
of
factors
from
(/C U
1C\)
\ { }.
Using Lemma 3.44,
the
existence
of
such
sets
K,\ and K2 is
shown directly.
On the
other hand,
by (2) and (3) it
holds that
for
every automaton
M e /C U
1C\
there exists
an
automaton
M
which cannot
be
represented homomorphically
by a
cascade product
of
factors
from
(/C
U
1C\
) \
{AT}
.
Consequently,
if
(/C
U
K,\
) is
homomorphically complete under
108
Chapter
3.
Krohn-Rhodes
Theory
and
Complete
Classes
the
cascade product, then
it
should
be a
minimal homomorphically complete class under
the
cascade product too. Thus,
it is
enough
to
prove that every automaton
A = (A, X,
<5)
can be
represented
homomorphically
by a
cascade product
of
factors
from
(JC
U
/Ci).
Consider
for an
arbitrary automaton
A the
automaton
Ai =
(Ai,
Xi, ;) in F
having
an
isomorphism onto
A.
Using (1),
we
have that
Ai can be
represented homomorphically
by
a
cascade product
of
factors
from
K U K
1
.
Therefore
A
also
has
this property. This ends
the
proof.
We
obtained
the
following direct consequence
of
this result.
Corollary 3.46.
There
exists
a
minimal
homomorphically
complete
class
under
the
cascade
product.
Finally,
we
note that,
by
Lemma 3.41, there exists
no finite
homomorphically complete
class
of finite
automata under
the
cascade product.
3.5
Bibliographical
Remarks
Section
3.1. Theorem
3.1
issued
from
K. B.
Krohn
and J. L.
Rhodes [1962
and
1965].
A
more detailed description
of
this result
was
developed
by K. B.
Krohn,
J. L.
Rhodes,
and
B.
R.
Tilson
[1968].
It has a new
proof
in
Esik [1999].
An
extension
of
Theorem
3.1 was
given
by Z.
Esik [1989a].
An
attractive presentation
of the
Krohn-Rhodes theory
was
given
by
A.
Ginzburg
[1968].
The
proof
of
Theorem
3.2 was
described
in
Lallement [1971]
and
Eilenberg
[1976].
Some aspects
of the
Krohn-Rhodes theory were studied
by J. L.
Rhodes
and
B. R.
Tilson [1989],
B.
Austin
et al.
[1995],
C. L.
Nehaniv [1996],
and Z.
Esik
[2000].
Results
in
this section (with
the
notable exception
of the
holonomy decomposition theorem)
are
mostly originally
due to and
derived
from
K. B.
Krohn
and J. L.
Rhodes [1962
and
1965]
and
appear
in the
book edited
by
Arbib
[1968].
They have been reformulated
and
treated
by
many authors, e.g.,
A.
Ginzburg [1968]
and S.
Eilenberg [1976]. Lemmas 3.4,
3.5, 3.6,
and 3.7 can be
derived
from
the
results
of A.
Ginzburg [1968]. Theorem
3.8 is due
to H. P.
Zeiger [1967]. Theorem 3.10 issued
from
K. B.
Krohn
and J. L.
Rhodes
[1962,
1965].
The
original idea
of the
holonomy decomposition theorem (Theorem 3.9)
is due to
H. P.
Zeiger
[1967],
with
a
correct proof
for
partial transformation semigroups given
by
S.
Eilenberg
[1976].
Our
proof, which makes reference only
to
fully
defined
transformation
semigroups,
is
inspired
by
Eilenberg's.
Section
3.2. Proposition 3.11
and
Corollary 3.12 were discovered
by Z.
Esik [1991b].
Theorem 3.13
can be
derived
from
Z.
Esik
[1989a].
Proposition
3.14
was
found
by
H. P.
Zeiger [1967]. Lemma 3.15 appears
in
Domosi [1984]. Lemma 3.16
is an
extended
form
of the
Lemma
1.3 of F.
Gecseg's book [1986,
p.
25]. Lemma 3.16
was
also proved
by
P.
Domosi [1984]. Theorem 3.17
was
elaborated
by Z.
Esik
and P.
Domosi [1986]. Theorem
3.18
was
shown
by P.
Domosi
and Z.
Esik [1988a]. Proposition 3.19
was
found
by Z.
Esik
and
J.
Vkagh
[1986].
Proposition 3.20
was
developed
by Z.
Esik
and P.
Domosi
[1986].
Lemmas 3.22, 3.23, 3.24, 3.25,
and
3.26 were proved
by P.
Domosi
and Z.
Esik [1988a].
Lemma
3.27
is a new
result. Theorem 3.28
is a
strengthening
of
Theorem 3.17
and can
be
derived
from
Theorem 3.17 using results
in
Esik
and
Domosi [1986] with results
from
3.5.
Bibliographical
Remarks
109
Domosi
and
Esik [1988a]. Theorem 3.29
is from Z.
Esik
and P.
Domosi [1986]. Some
related connections were described
by P.
Domosi
and Z.
Esik
[1986]
and P.
Domosi
and
Z.
Esik [1988b, 1988c]. Lemmas 3.31, 3.32, 3.33,
and
3.34
are
essentially
new
results.
Theorem 3.35
is a
direct consequence
of
Theorem 3.17. Theorems 3.36
and
3.37 were
shown
by Z.
Esik [1986].
Section
3.3. Theorem 3.40
was
shown
by P.
Domosi
[1980].
Section
3.4.
A
minimal homomorphically complete system under
the
«o-product
was
pre-
sented
by P.
Domosi [1976].
A
nice presentation
of
this result
is in
Gecseg
[1986].
The
results
of
this section
are
based
on
Domosi
[1982].
This page intentionally left blank