D?m?si P., Nehaniv C.L. Algebraic Theory of Automata Networks. An Introduction
Подождите немного. Документ загружается.
3.1.
Krohn-Rhodes
and
Holonomy
Decomposition
Theorems
81
Case
2.
Now
by
definition
of
ni,
since h(p)
= i. And
since h(q}
= i, by
definition
of ni, we
have
where
by
definition
of
So
Case
3.
We
have
This
implies
that
s
maps
B
p
bijectively onto
B
q
.
Again
and
since
and
by
definition
of
since
acts
as the
identity
on B
q
.
Therefore
Case
4.
and i
Then
by
definition,
and
so the
conclusion holds
by
induction hypothesis.
By
induction
we
conclude that
for
all
all
and
all
In
particular,
it
follows
from
that
the
height
of the
latter
is
less
than
i and
from
the
case
i = 1
that
lies
in
and
that
holds
for all
and
Moreover,
lifts
of
distinct members
of A are
distinct since
n]
is a
function,
and
lifts
of
distinct members
of 5 are
distinct.
If s\ 82
(s\,
S2 € 5),
then there
is an a € A
such
that
a • s\ a - S2.
Taking
a
lift
a of a we
have
n(a • J/) = (0) •
s,•
= a • s,, but
these
are
distinct
for i =
1,2,
and
therefore
the
lifts
s{ and are
also distinct.
By
Proposition 1.10,
this establishes
the
division
and
proves
the
holonomy theorem.
We
now
derive
the
Krohn-Rhodes theorem
as a
consequence
of
the
holonomy theorem.
Using
the
lemmas above,
the
following theorem implies
the
Krohn-Rhodes
decomposition
theorem
for
transformation semigroups.
Theorem
3.10.
A finite
semigroup
is
irreducible
if
and
only
if
it is a
nontrivial
simple
group
or a
subsemigroup
of
the flip-flop
monoid.
Proof.
By
Lemmas
3.5 and
3.6,
the
nontrivial simple groups
and
subsemigroups
of the
flip-flop
monoid
are
irreducible.
Let 5 be any
irreducible
finite
semigroup;
( , 5)
divides
a
wreath product
of
permutation-reset transformation semigroups
of the
form
( ,, ) by
the
holonomy theorem. Since
5 is
irreducible
it
divides
one of the HI. Now
(#,,
Hi) <
(
, { ,}) l
(Hi,
HI) by
Lemma 3.7.
So
either
S
divides {IgJ
and by
Lemma
3.8
embeds
82
Chapter
3.
Krohn-Rhodes
Theory
and
Complete
Classes
in
the flip-flop
monoid,
or 5
divides
the
group
%,. In the
latter case
S is a
group and,
by
Lemma 3.6,
S is a
simple group
or the
trivial group. This completes
the
proof.
From
the
holonomy decomposition theorem,
the
Jordan-Holder
coordinate theorem
for
finite
groups,
the
preceding lemmas,
and
Fact 1.15,
we
obtain
the
Krohn-Rhodes
prime
decomposition theorem
for
transformation semigroups.
The
corresponding result (Theorem
3.1)
for a finite
automaton
A =
(A,X,8)
follows
by
taking
the
transformation semigroup
(A,
S(A))
and
using
the
result
for
transformation semigroups.
3.2
Some Results
Related
to the
Krohn-Rhodes
Decomposition
Theorem
In
this section
we
characterize
the
complete classes
of finite
automata with respect
to the
homomorphic representation under
the
or,
products
for i = 0,
1,2. First
we
show
an
applica-
tion
of the
Krohn-Rhodes
theory.
Theorem
3.11.
Let
be an
oiQ-product.
IfG is a
simple
group
with
then
either
Proof.
First,
we
note that
if we
restrict ourselves
to a
noncyclic simple group
G,
then
our
statement
is a
direct
consequence
of the
Krohn-Rhodes
theorem
and
Proposition 2.49.
We
consider
a
direct proof
of our
statement which does
not use
this direct consequence.
Let
,
and
.
Obviously,
the man
with
and
is
a
well-defined semigroup homomorphism.
For
each
be the
collection
of
those transformations
8
with
If
Sb is
nonempty, then
it is a
subsemigroup
of
S(A)
and the
mapping
with
is
a
homomorphism. Since
there
is a
subgroup
H of
S(A) such that
G is a
homomorphic image
of H and
Since
H is a
subgroup
of
SL4),
by
Proposition 2.36, there
is a
nonempty
set
with
the
following properties:
(a)
The
restriction
of
each
is a
permutation
of W.
(b) The
mapping
with
.
is an
isomorphism
of H
onto
a
permutation group over
W.
Thus
for
we
have
if
and
only
if
for
all
Let B\ be the set of the first
components
of the
elements
of
W.
For
each
define
to be the
permutation
of B\
obtained
by
taking
the
restriction
of
Then
with
is a
well-defined homomorphism
of H
onto
a
permutation group
over
B\. Set N = ker , so
that
N
is
a
normal subgroup
of H and HIN = P. Let
be the
homomorphism taking
Clearly,
is a
subgroup
of
S(B).
We can
consider
as
a
homomorphism
of H
onto
. If
tor
some
i
then
also Therefore
ker
Moreover,
factors
through
. it
follows
that
H
/N
is a
homomorphic image
0f H\.
From
we
also have Since
3.2.
Some
Results
Related
to the
Krohn-Rhodes Decomposition Theorem
83
the
simple group
G is a
homomorphic image
of H and N is a
normal subgroup
of H,
either
G is a
homomorphic image
of H/N or N
maps homomorphically onto
G. In the
former
case
G is a
homomorphic image
of HI and
therefore G||
(n)
H. From
now on we
assume that
G is a
homomorphic image
of N. Let b e B\ be any fixed
state.
If N
for
a
word
p X
+
,
then 8i(b,
<pi(p})
= b,
i.e.,
AT
c S
b
.
Define
fa : N -*
S(C)
by
fa(
)
= ( ) for all N
with
p €
X
+
.We
already know that
fa is a
well-
defined
homomorphism
of N
into S(C). Therefore
Hb = ( ( ) : e N, p X
+
}
must
be a
group,
a
subgroup
of
S(C).
We
also view
fa as a
homomorphism
of N
onto H
b
,.
If
p,q
X
+
with
<5
P
,
^ G
N,and
q
,
then there
is a
pair
(b, c) e W
withS((&,
c), p) /
«((*,
c),
<?).
But
S((b
t
c), p) = (b,
8
2
(c,
<p2(b,
p)))
and
8((b,
c),
<?)
=
(ft,
8
2
(c,
(p
2
(b,
<?))),
so
that
fa(8
p
) = (8
)^
(b
,
) ^ ?) =
ifo(^).
Thus
n(ker
fa : b z #0 is the
trivial normal subgroup consisting
of the
identity
of N.
Since
n(ker
fa : b e #1) is
trivial,
N is
isomorphic
to a
subdirect product
(i.e.,
a
subgroup
of the
direct product)
of
the
groups
Hb, b B\,
Since
the
simple group
G is a
homomorphic image
of N, it is
also
a
homomorphic
image
of a
subgroup
of
some
H
b
,
i.e.,
G
divides
Hb. The
group
h
b
consists
of the
transformations
of the
form
(<$2)<p
2
(fc,p)>
where
p e X
+
and ^ e
AT.
Since
each member
of N is
induced
by
some word
of
length
n, the
same holds
for Hb,
i.e.,
H
b
c
{(($2X7
: e Z+, |?| = n}.
Because
G
divides #
ft
,
we
obtain
G\\
W
C.
D
Corollary
3.12.
Lef G be a
nontrivial simple
group.
If
G\\Afor
an
ctQ-product
A of
automata
in /C,
where
/C is any
class
of
automata, then
G\
\Bfor some
B € /C. n
Theorem 3.13.
Let S be an
irreducible
semigroup.
IfS
\
\Afor
an
oiQ-product
A
of
automata
in /C,
where
/C is any
class
of
automata, then S\\B
for
some
B e /C. In
addition,
if
S\\B
for
some
B € /C and S is a
subsemigroup
of
the flip-flop
monoid, then
S
embeds
in
S(B)
in
equal
lengths with
respect
to B.
Proof.
If S is an
irreducible semigroup, then
by
Theorem 3.10,
5 is
either
a
simple group
or a
subsemigroup
of the flip-flop
monoid.
If S is
either
a
noncyclic simple group
or a
subsemigroup
of the flip-flop
monoid, then
we can
apply Proposition 2.49.
If 5 is a
(cyclic
or
noncyclic) simple group, then
we can
apply Corollary 3.12.
This
completes
the first
part
of
the
nroof.
For the
second nart. assume that
S\ \B for
some
B = (B. X. 8} K
such that
S
is
a
subsemigroup
of the flip-flop
monoid.
First
we
suppose that
S = {e, t, r] is the flip-flop
monoid. Using Lemma 3.4, there exists
a
subsemigroup
with
M,
v, w €
navmg
an
isomorphism
K
onto
S.
Let, say,
such
that
e is the
identity
of 5. We
shall
use the
obvious
facts
that
for
every pair
i, j of
positive integers,
Let
Then
and
Therefore,
such
that
w',
v', w'
have equal lengths
and
K
is an
isomorphism. This completes
the
proof
if 5 is the flip-flop
semigroup.
We can
give similar treatment
for
the
subsemigroups
of
5. n
Proposition
3.14.
Every
reset
automaton
can be
represented
isomorphically
by a
direct
power
of
the two
state reset automaton.
84
Chapter
3.
Krohn-Rhodes Theory
and
Complete
Classes
Proof.
Let
be an
arbitrary reset automaton with state
set
Consider
the nth
direct power
of the two
state reset automaton
for
which
Let
be
mappings
such
that
for
every
and
furthermore,
if
and
only
if
Clearly
then
A can be
embedded isomorpmcally into
under
Take
two
alphabets
X and Y. For a fixed
positive integer
n,
consider
a
mapping
Moreover,
be the
automaton,
where
and,
for
arbitrary
and
Lemma 3.15.
For
every
can
be
represented
homomorphically
by a
cascade
product
of
an
n-state counter
and
two-state
reset
automata.
Proof.
Of
course,
a
direct product
of
automata
can be
considered
as a
special type
of
their cascade product. Therefore, using Proposition 3.14, every
reset
automaton
can be
represented homomorphically
by a
cascade product
of
two-state reset automata.
To
prove
our
lemma, therefore,
it is
enough
to
show that
can be
represented homomorphically
by
a
cascade oroduct
of an
n-state counter
and
certain reset automata.
Let
be
a
counter. Moreover, take
the
automata
and
where
* is an
arbitrary symbol with
moreover,
for
arbitrary
and
Clearly,
all the
are
reset automata. Take
the
cascade product
with
where
and
3.2.
Some
Results
Related
to the
Krohn-Rhodes Decomposition Theorem
85
Now
we
define
a
subautomaton
with
X' = X of B and
that
of a
mapping
under
which
R.
r
is a
homomorphic image
of B'. Let B'
consist
of all
b 6 B for
which there
are
words
and
with
such
that
Moreover,
let
where
denotes
the
mirror image
of p. It is
routine work
to
show that
B
f
is a
subautomaton
of B, and
is a
homomorDhism
or
onto
We
will also
use the
following lemma.
Lemma 3.16.
Let
and
be
automata. Assume that
for
an
integer
there
exist
mappings
and
such
that
the
following
two
conditions
are
satisfied:
for
arbitrary
b B and
Then
a
cascade product
o R
T
by B
homomorphically
represents
A.
Proof.
Form
the
cascade product
where,
for
arbitrary
and
To
an
arbitrary state
d =
((D. va).
b) of P we
correspond
the
state
of
A.
Assume that
D
receives
an
input signal
x in
this state
d. If
then
to
which
the
state
of
A is
corresponded.
In the
opposite
state,
i.e.,
if
then
The
state
of A
corresponding
to
this
is
which
is
equal
to
since,
for
arbitrary
b € A.
(Observe that
in the
second case
a = X.) In
both cases
we
have that
the
mapping
given
by
is a
homomorphism
of D
into
A. By
(2),
y is a
mapping onto
A.
We
are
ready
to
give
a
proof
of the
next statement.
Theorem
3.17.
A
class
JC
of
automata
is
complete with
respect
to
homomorphic
represen-
tations
under
the
cascade product
if
and
only
if
(1) the
two-state reset automaton
can be
represented
homomorphically
by a
cascade
product
of
automata
from
K,
(2)
every
counter
(of
prime power length)
can be
represented
homomorphically
by a
cascade
product
of
automata
from
/C,
86
Chapter
3.
Krohn-Rhodes Theory
and
Complete
Classes
(3a)
there
is an
automaton
A K
such that
a
subsemigroup
S
ofS(A)
is
isomorphic
to
the
monoid with
two
right-zero elements,
and
(3b)
for
every
simple
group
G
there
is an
automaton
with
Proof.
The first two
conditions
are
obviously necessary.
17
The
necessity
of
(3a)
and
(3b)
comes directly
from
the
Krohn-Rhodes decomposition theorem. (Actually, (3a)
and
(3b)
constitute
Krohn-Rhodes'
criterion.)
For the
converse,
first
note that every counter
can be
represented homomorphically
by a
cascade product
of
counters with prime power length.
(We
omit
the
easy proof
of
this statement.) Thus
we may
assume
by the
conditions (1),
(2),
and
Lemma 3.15 that
for
every
r : [p• e X
+
: \p\ — n} -+ [p Y
+
: \p\ = n},
the
automaton
R
T
can be
represented homomorphically
by a
cascade product
of
automata
from
K,. Let 5 be an
arbitrary noncyclic, irreducible monoid.
By our
conditions (3a), (3b),
and
Proposition 2.49
we
have that
S\ \A for
some
A K.
Using
Proposition
2.47,
we
then
get
As\\B^
n
,
where
H
An
denotes
the nth
diagonal power
of an
appropriate subautomaton
B = (B, Y,
SB)
of the
automaton
A
satisfying
the
conditions
of
Proposition 2.47
and n is the
number
of
states
of A.
Thus,
let AS\ |
n
under
the
mappings
r\ : B
n
S, r
2
: S -> Y
+
.
Then, denoting
by e the
identity element
of S, we get
{S
s
(Ti(8'(b, r
2
(e))),
e) : b e B
n
} =
{riO$'(b,
T
2
(e)))
: b e B
n
} =
{^(b)
: b B
n
] = S.
Therefore (taking
a, T, A, B of the
lemma
to be i\, 12, AS, B,
respectively),
we
have
the
conditions
(1) and (2) of
Lemma 3.16.
Then
AS can be
represented
by a
cascade product
of the
automaton
K
T2
by the
direct power
B
n
.
Therefore, combining this with (2),
for
every irreducible semigroup
5, we
conclude
that
As can be
represented homomorphically
by a
cascade product
of
automata
from
K,
for
every irreducible semigroup
S.
Using
the first
part
of the
Krohn-Rhodes
decomposition
theorem, this implies that
/C
is
complete with respect
to
homomorphic representations under
the
cascade product.
The
proof
is
complete.
D
Theorem
3.18. None
of
conditions
(1), (2), (3a),
and
(3b)
of
Theorem
3.17
can be
omitted.
Proof.
For
(3a)
and
(3b),
the
statement comes directly
from
the
Krohn-Rhodes decompo-
sition theorem. (See Theorem 3.1.)
For
(1),
we now
show that there exists
a
class
/C
satisfying
(2), (3a),
and
(3b), which
is not
complete with respect
to
homomorphic representations under
the
cascade product.
Let
be a
(countable) system
of
automata
with
moreover,
let
be
defined
by
Then
and
Thus
a
subsemigroup
of
S(A\)
is
isomorphic
to the
monoid with
two
17
Although
it may be
counterintuitive
to
those
used
to
transformation semigroups rather than automata,
to
obtain
(2),
it is not
sufficient
to
homomorphically represent
all
prime-length counters with
single-letter
input
sets.
For
example, using such counters,
the
single-letter-input modulo-four counter cannot
be
homomorphically
represented.
3.2.
Some
Results
Related
to the
Krohn-Rhodes Decomposition
Theorem
87
right-zero
elements.
On the
other hand,
by
Proposition 1.5,
for
every
n = 2,
3,...,
the
degree-n
+ 1
symmetric group
is
isomorphic
to
S(A
n
).
Since
the
degree-two symmetric
group
can be
embedded isomorphically into
a
larger symmetric group, and, furthermore,
every
simple group
can be
embedded isomorphically into
a
symmetric group, then
/Co
satisfies
(3b). Therefore, {.4o}
U /Co
satisfies
(3a)
and
(3b).
Let
A =
({0,1},
[x, y}, 8) be an
automaton having S(i,
x) = 1 and
8(i,
y) = 2, i =
1,
2.
Then
A is a
two-state reset automaton.
For
every positive integer
n, set B
n
= (A x
{1,...,
n + 1} U
{*},
A x
{jc,
y},
8'
n
), where
* is a new
symbol
and
with
(a, b)
{0,1}
x
{1,...,
n + 1}, (c, z)
{0,1}
x {x, y}.
Let
K,
consist
of the
counters
and all
automata B
n
,n
=
1,2,—
It is now
obvious that
/C
satisfies
(2).
For
(3a)
and
(3b),
first
note that
for
every
n, A
n
is a ho-
momorphic image
of a
subautomaton
of a
cascade product
A x
B
n
({x,
y}, \, )-
(Hint:
(z)
= z,
<p2(a,
z) = (a, z), a e
{0,1},
z e {x, y}, and the
state
set of the
subautomaton
is
just {(a,
(a, b)) \ a e A, b e
A
n
}.)
But the
monoid
F
with
two right-zero
elements
can be
embedded isomorphically into
S(A\).
Thus,
from
the
Krohn-Rhodes theorem,
F is
isomor-
phic
to a
subsemigroup
of
S(A)
or to a
subsemigroup
of
S(Bi).
The first
case
is
impossible
by
the
choice
of A;
hence,
/C
satisfies
(3a). Similarly,
let G be a
noncommutative simple
group. Since
/Co
satisfies (3b),
we may
assume
G < A
n
for
some
A
n
e
/Co,
n > I. But
then
we
have again that
A
n
is a
homomorphic image
of a
subautomaton
of a
cascade
product
A x
B
n
({x,
y},
<p\,
<p2).
Hence
G < A x
B
n
({x,
y},
<p\,
$2) and G < A is
impossible. Then
G < B
n
follows
from
the
Krohn-Rhodes theorem.
We
have seen that
/C
satisfies
all of the
conditions (2), (3a),
and
(3b).
To
see
that
/C is not
complete
we
prove
the
following: every strongly connected
subautomaton
of a
cascade product
of
factors
in /C is
autonomous.
Of
course, this also
shows
that
/C
does
not
satisfy
condition (1).
Assume
the
contrary.
Let
T>\
x • • • x
T>
m
(X,
<p\,...,
(p
m
)
be a
cascade product
of
automata
of
factors
/C
having
a
strongly connected nonautonomous subautomaton
and
such
that
m is
minimal with this property. First
we
assume that either
m = 1 or m > 1
and
T>i,...,
T>
m
-\
are
counters. Then
a
cascade product
C x
T>
m
(X,
\jr\,
^2)
also
has
a
nonautonomous strongly connected subautomaton, where
C is a
counter
Ck. (C can be
a
trivial counter having only
one
state
if m = 1). Let us
denote this subautomaton
by
D= (D, X,
8").
The
automaton
D
m
cannot
be a
counter,
so it is B
n
for a
partic-
ular
n.
Since
D is a
nonautonomous strongly connected automaton,
no
state
in D has
the
symbol
* as its
second
component.
Let
and
be fixed
with
Put
Thus,
If
=
a-y. then,
bv A
and
the
definition
of B
n
, we
have
But
then
b\
= bi
follows. Therefore,
»
and, consequently,
one of
and
has
the
symbol
* as its
second component.
Hence,
m > 1 and
there exists
a k, 1 k < m,
such that
£>* = BI for £
particular
1.
Denote again
D =
(D,X,
8") a
nonautonomous strongly
connected
88
Chapter3. Krohn-Rhodes
Theory
and
Complete
Classes
subautomaton
of D
1
x • • • x
D
m
(X, (p
1
,...,
pm).
If V has a
state
for
which
its th
compo-
nent
is *,
then
all
state
of V has
this property. Clearly, then
D can
also
be
represented
by a
cascade product
D
1
x • • • x D
-1
x
D
l+1
x • • • x
D
m
(X, (p(,..., <p'
m
),
which
is
impossible
by the
minimality
of m.
Then every state
(d
1
,...
,d
m
)
ofD has the
property
d € A x A .
Suppose that there
are
(d
1
,...,
d
m
) e D
1
x • • • x D
m
,
z
1
,Z
2
€ X
with
"((d
1
,...,
d
m
},
z
1
)
"((d
1
,...,
d
m
), z
2
)- Similar
to the first
case,
it can be
easily seen
that
one of
"((d
1
,...
,d
m
),
z
1
Z
1
)and
"((d
1
,...
,d
m
),
Z
2
Z
1
) has the
symbol*
as its lth
com-
ponent.
But
then
all
states
of D
have this property
and
thus
D can
also
be
represented
by a
cas-
cade product
D
I
x • • • x D _i x D +1 x • • • x D
m
(X,
(p{,..., <p'
m
),
which
is
impossible
by the
minimality
of m.
Hence
we
then obtain
for
every
(d
1
,...,
d
m
) e D
1
x • • • x D
m
, z
1
, Z2 € X,
"((d
1
,...,
d
m
),
z
1
) =
"((d
1
,...,
dm),
z
2
)-
But
then, contrary
to our
assumptions,
D is
autonomous.
It
remains
to
show that there exist
a
class
k
satisfying
(1), (3a),
and
(3b), which
is not
complete
with respect
to
homomorphic representations under
the
cascade product.
Now
we
consider
a
(countable) system
of
automata
k
1
= {A
n
=
({1,...,n},
x, y, w},
n
) | n = 1,
2,...}
with
n
=
1,2,....
Moreover,
let A
0
=
({I,
2}, {x,
y},
1
) be
defined
by (i, x) = 1,
0
(i,
y) =
2,i{1,2}.
By
Proposition 1.5,
for
every
n 1,
S(A
n
)
is
isomorphic
to the
degree
n
symmetric
semigroup. Thus both
of the
monoid
F
with
two
right-zero elements
and the
degree-n
symmetric group divide S(A
n
) if n > 1. On the
other hand,
A
o
is a
two-state reset automaton.
Therefore, {Ao}
U K\
satisfies
the
conditions (1), (3a),
and
(3b).
Let m be an
arbitrary positive integer with
m > 1, and for
every positive integer
n set
B
n
=
({1,...
,m] x
(1,.
..,n}U{*},
{1,...
,m} x {x, y, w},
n
),
where
* is a new
symbol
and
Krohn-Rhodes
theorem,
F is
isomorphic
to a
subsemigroup
of
S(C
m
)
or to a
subsemigroup
of
S(B
n
).
The first
case
is
impossible; hence,
/C
satisfies
(3a). Similarly,
let G be a
nontrivial
simple group. Since every group
can be
embedded
in a
larger noncommutative simple group,
we
may
assume without loss
of
generality that
G is
noncommutative (and simple).
We may
with
(a, b) e
{I,...,
m} x
{1,...,
n}, (c, z) e
{1,...,
m} x {x, y, w}.
Let
K
2
consist
of all
automata
B
n
, n =
1,2,
It is
obvious that
k' =
{Ao}
U k
2
satisfies
(1).
For
(3a)
and
(3b),
first
note that
for
every
n > 1, A
n
is a
homomorphic image
of
a
subautomaton
of a
cascade product
C
m
x
B
n
({x,
y, w}, p
1
,
p
2
), where
C
m
is a
counter with
m
states. (Hint: ^i(z)
= z,
<pi(a,
z) = (a, z), a 6
{1,...,
m}, z . {x, y, w}, and the
state
set
of the
subautomaton
is
just
{(a,
(a, b)) | a €
{1,...,
m}, b
{1,...,
n}).
But
for
every
n > 1 the
monoid
F
with
two
right-zero elements
is a
submonoid
of
S(An). Thus,
from
the
3.2.
Some
Results
Related
to the
Krohn-Rhodes Decomposition Theorem
89
assume that
G < A
n
for
some
n > 1. On the
other hand,
we
have again that
A
n
is a
homomorphic image
of a
subautomaton
of a
cascade product
-
Hence, and, using that
G is
noncommutative,
G < C
m
is
impossible. Then
G < B
n
follows
from
the
Krohn-Rhodes
theorem.
We
have seen that
satisfies
all of the
conditions (1), (3a),
and
(3b).
To
see
that
K' is not
complete
we
prove that none
of the
nontrivial counters
can be
represented homomorphically
by a
cascade product
of
factors
in K'.
This also shows that
K!
does
not
satisfy
condition (2).
Let
us first
note that
if a
counter
C is a
homomorphic image
of an
automaton
A,
then
A
has
a
subautomaton
B
isomorphic
to a
counter which
can be
mapped homomorphically onto
C.
Moreover,
the
number
of
states
in C
always
divides
the
number
of
states
in B.
Therefore,
it
is
enough
to
show that whenever
B =
({x},
B, a') is a
subautomaton
of a
cascade product
and
B is
isomorphic
to a
counter, then
the
number
of
states
in B is not
divisible
by m. For
this,
take
a b =
(b
1
,...,
b
k
) € B. For
every
j €
{1,...
k},
denote
by tj the
least positive integer
such
that
. We
prove that
m
does
not
divide
lj, j = 1,
...,k,
which
in the
case
j = k
means that
m
does
not
divide
.
Obviously,
if
7
= 1,
then either
D
1
= A
0
or b
1
= * and
thus
t\ = 1. We
prove that
e
j
= 1
whenever
tj-i
= 1 and 7 > 1.
Indeed,
TV-Hi
= 1
implies that
(b
1
,...
,b
k
,x)
=
t =
l,...,l
j
,(
) =
8'((b
1
,...,
b
k
), x
n
),
n 1. But
then either
D
j;
= A
0
or
b
j
= *.
Thus,
we get l
k
= 1 by
induction.
Therefore,
if B
homomorphically
represents
a
counter
C,
then
C is
trivial (having only
one
state).
The
proof
is
complete.
Proposition
3.19.
There
exists
a
class
K,
of
automata which
is
complete
with
respect
to
homomorphic
representations
under
the
cascade
product such that
all
elements
of
1C
have
two
input
letters.
Proof.
We
consider again
a
two-state reset automaton
A
0
(having
two
input letters)
and
define
K
0
as the
above proof
of
Theorem 3.18.
Let
K
0
with
n
= 2,
3,...;
moreover,
let A\ =
({1,2},
{x, y}, ) be
defined
by (l, x) = (2, x) =
2,
<$i(l,
y) = 2,
5i(2,
y) = 1. We
prove
the
completeness
of
1C"
=
{Ao}
U Ko- Of
course,
it
trivially
satisfies
conditions
(1) and (2) of
Theorem 3.17.
On the
other hand,
by (l, x) =
Si(2,jc)=2,5i(l,xy)
=
(2,xy)
= 1,
(l,yy)
= 1, and (2, yy) = 2. The
monoid
F
with
two
right-zero
elements
can be
embedded
isomorphically
into
A
1
, as we
proved
in the
previous proof
of
Theorem 3.18. Thus
we
obtain (3a). Finally, Proposition
1.5
implies that
S(A)
n
is
isomorphic
to the
degree-n+1
symmetric group
(as we
have also already mentioned
in
the
previous proof
of
Theorem
3.18).
Since every simple group
can be
embedded into
an
appropriate symmetric group
and
every symmetric group
can be
embedded into
a
larger
symmetric group,
we
also have condition (3b).
The
proof
is
complete.
d
90
Chapter
3.
Krohn-Rhodes
Theory
and
Complete
Classes
By
an
elementary computation
we
obtain
the
next observation.
Proposition
3.20.
Let C
n
be a
nontrivial counter,
i.e.,
n > 1, and let
1C
be a
class
of
automata.
C
n
can be
represented homomorphically
by a
cascade
product
of
factors
from 1C
if
there
is a
multiple
ofm
such
thatC
m
can be
embedded isomorphically
by a
cascade
product
of
factors from
1C.
Further,
C
m
can be
embedded isomorphically into
a
cascade
product
of
factors from
K
if
and
only
if
there
are
automata
A
i
=
(A
i
,
X
i
, , ) K, i =
1,...,
k, k > 0,
and
integers
1 = mo <m\ < • • • < m
k
= m
such that
(1)
m
i
_1
is a
divisor
of
mi (i e
{1,...,k}),
and
(2) for
every
i e
{1,...,
k}
there
are
distinct states
a
1
,...,
a
mi
/
mi
_
1
A
i
, and a
word
u
€ X*
with
|u| =
w,-_i
and
Let us
call
1C
of
automata
precomplete
if it
satisfies
the
following conditions:
(i)
There
is an
automaton
A
such that
F is
isomorphic
to a
subsemigroup
of
S(A).
(ii)
For
every simple group
G
there
is an A e
1C
with
G <
S(A).
The
Krohn-Rhodes decomposition theorem readily implies that every complete class
for
the
cascade product
is
precomplete,
but the
converse
fails
in
general.
It may
well happen
that
although
1C
is
precomplete,
any
strongly connected automaton
is
trivial,
i.e.,
a
one-state
automaton
if it can be
represented homomorphically
by a
cascade product
of
factors
in
1C.
Proposition
3.21.
Let q = p
l
be a
prime
power. There exists
a
precomplete class
K'
such
that
for any K
o
, C
q
cannot
be
represented homomorphically
by a
cascade
product
of
factors
from
K' U Ko
unless
C
q
can be
represented homomorphically
by a
cascade
product
of
factors
from /Co.
Proof.
Define
the
automata
A
n
, n > 3, as
follows:
A
n
=
({1,...,
qn} U
{*},
{jci,...,
x
q
,
y}, ),
where,
for
every
i
{1,...,
qn} and j
{1,...,
q},
Observe that
the
word
x
1
,
...,x
q
induces
a
cyclic permutation
of the
states
in A' = {1, q +
1,...,
q(n
—
1) + 1}.
Moreover,
yx2
--'X
q
induces
the
transposition
y (1) = q + 1, y
(q
+
1)
= 1,
y(a')
= a', a'
A'\{1,
q+1}
of
A'.
Consequently,
by
Proposition 1.5,thedegree-n
symmetric group divides S(A
n
).
In
addition
to the
automata
A
n
define
A =
({1,...,
2q] U
{*},
(x, y,
z,*2,
...,x
q
,},
5) by the
following rules: 5(1,
x) =
(q
+
l,x)
=
(q
+
l,z)
=
2,
(1, y) = (1, z) = (q +
l,y)
=q+2,
(i,xi)
= i + 1
(mod 2q),
(q +
/,*,-)
=