D?m?si P., Nehaniv C.L. Algebraic Theory of Automata Networks. An Introduction
Подождите немного. Документ загружается.
2.5.
Bibliographical
Remarks
71
criterions
or the
semi-Letichevsky criterion, which
is a
contradiction. Therefore,
the
con-
sidered product
is
without Letichevsky criteria.
Proposition 2.76.
Let A be an
arbitrary
noncommutative
strongly
connected
automaton.
Suppose
that
an
automaton
B
homomorphically
simulates
A.
Then
B
satisfies
Letichevsky's
criterion.
Proof.
Consider
a
noncommutative strongly connected automaton
A = (A, X, ).
Suppose
that
A can be
simulated homomorphically
by an
automaton
B = (B, , SB)
under
T\ :
B' A,
TI
: X
XB*. Suppose that
B' is
minimal such that
it has no
proper subset
B" for
which
B
homomorphically simulates
A
under some
( : B" A, : X ->•
XB*.
Then,
by the
strong connectivity
of A, for
every
b\, bi B'
there exist
x\,...
,Xk
€ X
with
. In
addition, because
01 the
noncommutativity
01 A,
there
are
a
state
and
input words
having
Consider
the
natural
extension
with
Then
tor
every
In
addition,
by the
minima-
lity
or B ,
there exist words
with
On
the
other hand.
implies that
Indeed
leads
esultmg
in
a
contradiction.
Therefore, there
are
such
that
and, moreover,
Let
Obviously, then
and
The
proof
is
complete.
2.5
Bibliographical
Remarks
Section
2.1. Extensive treatment
of
graph theory
is
given
by F.
Harary
[1969].
Theorem
2.1 is
from
K.
Kuratowski
[1930].
A
nice presentation
of
this result
was
developed
by
G. A.
Dirac
and S.
Schuster [1954], Theorem
2.2 was
found
by G.
Chartrand
and F.
Harary
[1967]. Lemmas
2.6,2.7,2.8,2.9,
and
2.10, Theorem 2.11, Proposition 2.13,
and
Theorems
2.15
and
2.16
can be
found
in
Ananichev, Domosi,
and
Nehaniv
[in
press]. Lemmas
2.8
and
2.9 can
also
be
derived
from
Z.
Esik [1989b].
The
concept
of
digraph completeness
is
from
Z.
Esik [1991a]. Corollaries 2.19
and
2.20
are in
Esik
[1991a].
The
other parts
of
this
section
are
essentially new.
Section
2.2. Many books have given accounts
of
various aspects
of the
algebraic the-
ory
of
automata—for example, Bavel [1983], Eilenberg [1974], Gecseg
and
Peak [1972],
Gecseg
[1986],
Ginzburg
[1968],
Hartmanis
and
Steams
[1966],
Holcombe
[1982],
Nelson
[1968],
Salomaa [1969],
and
Simon [1999].
The
concept
of
automaton mapping
is
given
and
intensively studied
in
Raney
[ 195 8] and
Horejs
[
1963].
The
generating systems
of
semi-
groups
and
groups
of
automaton mappings
are
intensively studied
in
Csakany
and
Gecseg
[1965],
Gecseg [1965],
and
Zarovnyi [1965]. Theorem 2.30
is due to S. V.
Alesin [1970a]
and
P.
Domosi [1972].
(In the
present book
a new and
simpler proof
of
this statement
has
been produced.)
S. V.
Alesin
[1970b]
stated that
the
answer
to
Problem 2.31
is in the
affir-
mative. But,
unfortunately,
there
is a gap in the
proof
of his
Lemma
3, and so the
validity
of
72
Chapter
2.
Directed
Graphs,
Automata,
and
Automata
Networks
his
results
may be
questionable. (See also Csakany, Mathematical Reviews
45
1687.)
The
other results
are new but
elementary.
Section2.3. Proposition 2.34 issued
from
Eilenberg[l 974]. Proposition 2.47
is
new. Propo-
sition 2.49
was
proved
by Z.
Esik
[199la].
All the
other statements
are
folklore.
Section
2.4. Investigation
of finite
automata networks goes back
to W. S.
McCulloch
and
W.
Pitts
[1943],
J. von
Neumann [1966],
E. F.
Codd
[1968],
M.
Minsky
and S.
Papert
[1969],
A. W.
Burks
[1970],
and C.
Choffrut
[1986].
An
extensive algebraic treatment
of
automata networks
was
given
by M.
Tchuente
[1979,1982,1983,1985,1986]
and by
F.
Fogelman-Soulie,
Y.
Robert,
and M.
Tchuente
[1987].
Structural
and
behavioral equiv-
alence relations
in
automata networks were studied
by T.
Saito
and H.
Nishio
[1989].
A
verification
tool
for
distributed systems using reduction
of finite
automata networks
was
described
by E.
Madelaine
and D.
Vergamini [1989]. Finite (and
infinite)
automata systems
as
parallel communicating
finite
(and
infinite)
automata networks were intensively investi-
gated
by Z.
Fiilop
[1991],
C.
Martin-Vide
and Gh.
PSun
[1999],
C.
Martin-Vide
and V. Mi-
trana
[2000,
2001],
C.
Martin-Vide,
A.
Mateescu,
and V.
Mitrana [2002],
and I.
Babcs&ryi
and
A.
Nagy
[2004].
Product
and
completeness
of
automata were intensively investigated
by
F.
Gecseg
and I.
Pea*
[1972],
S.
Eilenberg
[1974,1976],
J.
Dassow
[1981],
and F.
Gecseg
[1986].
The
concept
of the
Gluskov-type product
is
introduced
by V. M.
Gluskov
[1961].
Several specialized types
of the
Glu§kov-type product were
defined.
The
concepts
of D-
product
and
A-product were proposed
by Z.
Esik [1991b].
The
quasi-direct product
was
given
by F.
Gecseg
and I.
Peak [1972].
The
cascade product
is
from
M.
Yoeli
[1961].
The
loop product
was
defined
by Z.
Esik [1987a].
The
family
of
a,-products
was
introduced
and
intensively studied
by F.
Gecseg [1974,1976a,
1986].
The
family
of
v,-products
is due
to P.
Domosi
and B.
Imreh
[1989].
The
family
of
a,-v,-products
was
given
by F.
G6cseg
and
H.
Jiirgensen
[1991].
Products
of
automata with identity
are
from
Z.
Esik
and J.
Viragh
[1986].
Theorem 2.68
was
proved
by V. M.
GluSkov
[1961].
Theorem 2.69
can be
found
in
Letichevsky
[1961].
The
proof
of
Proposition 2.76
is
new.
Chapter
3
Krohn-RhodesTheory
and
Complete
Classes
While
the
fundamental
information
concerning complete classes with respect
to
homo-
morphic representations under
the
general (Gluskov-type) product
is
concentrated
in the
celebrated classical criterion
of
A. A.
Letichevsky,
the
well-known Krohn-Rhodes decom-
position
theorem
is the
basis
for
studying
the
cascade product
of
automata.
The
cascade
product
of
automata
is a
general model
of
automata networks without feedback,
and the
theorem describes
how to
synthesize
any finite
state automaton using such
a
cascade, and,
moreover,
it
describes
the
necessary irreducible components
in
detail.
We
shall derive
the
Krohn-Rhodes decomposition theorem from
a
sophisticated result called
the
holonomy
decomposition theorem, which generally yields much more
efficient
decompositions than
in the
original
proofs
of
the
former.
Characterization ofhomomorphic representation
is
important since
one
of
the
major
tools
for
representations
is
homomorphism.
While
it is not too
general,
it is
powerful
enough.
We
study
homomorphic representation
in
networks
of
automata with
no
feedback (cascade
and
quasi-direct products)
and
with
low
bounds
on
feedback length
(a
-products
for i 2)
here.
3.1
Krohn-Rhodes
and
Holonomy
Decomposition
Theorems
Theorem
3.1
(Krohn-Rhodes
decomposition
theorem).
Given
a finite
automaton
A,
let
F be the flip-flop
monoid (the smallest monoid with
two
right-zero elements); moreover,
let
GI, ... ,G
n
denote
all
simple groups that divide
the
characteristic semigroup S(A).
Then
A can be
represented homomorphically
by a
cascade product
of
components from
{Af,
Ad, • • •, Ac
n
}•
Moreover,
if
A is a
nontrivial
permutation
automaton, then
the
factor
AF
may be
excluded.
Conversely,
let
i
be a
cascade product
of
automata
which homomorphically represents
the
automaton
A.
If
a
subsemigroup
S
of
the flip-flop
monoid
or a
simple group
S is a
homomorphic image
of
a
subsemigroup
of
S(A), then
S
is
a
homomorphic image
of
a
subsemigroup
of
S(B
t
)
for
some component automaton
B
t
(t
€
{1,...,
n}).
In
addition,
a
subsemigroup
S
of'the
monoid¥with
two
right-zero elements
73
74
Chapter
3.
Krohn-Rhodes Theory
and
Complete
Classes
can be
embedded
isomorphically
into
a finite
semigroup
T
whenever
T has a
subsemigroup
that
can be
mapped
homomorphically
onto
S.
Irreducibility.
A finite
semigroup
S is
irreducible
if
whenever
S
divides
a
wreath product
of
finite
transformation semigroups (x2,
s2)
(X\, S\), then
S
divides
s2 or S
divides
S\.
Equivalently,
if 5
divides
the
cascade product
of finite
automata
A and B,
then either
S < A
or
S < B. Or
again, equivalently,
"S is
irreducible"
means that
if S
divides
the
-product
of
finite
automata, then
it
divides
one of the
factors.
For
any finite
automaton
A, let
PRIMES(A)
denote
the set of
simple groups that
divide S(A). This notation also applies
to
transformation semigroups viewed
as
automata.
We
will derive Theorem
3.1
from
the
following,
for
whose proof
we
shall rely
on the
holonomy decomposition theorem
and a
series
of
lemmas.
Theorem
3.2.
(Krohn-Rhodes
prime
decomposition
theorem
for
transformation semi-
groups).
Let (A, S) be a finite
transformation
semigroup.
Then
(A, S)
divides
a
wreath
product
of
transformation
monoids
(M,-,
M/)
such that each
M, 6
PRIMES(S)
or M{
is
the flip-flop
monoid.
In the
case that
(A, S) is a
permutation group, then
the flip-flop
monoid
is not
required
and the
division
can be
chosen
to be an
embedding.
Conversely,
for
every
wreath product
of finite
transformation
semigroups (Bi, s
i
,)
which
(A, S)
divides,
we
have that
G
PRIMES(S)
implies that
G
divides
s
i
, for
some
i.
Moreover,
if
M is any
divisor
of
the flip-flop
monoid which divides
S,
then
M
embeds
into
some
5,.
The
subsemigroups
of flip-flop
monoid
F are the
monoid
F
with two-right-zero ele-
ments itself,
the
two-element monoid with zero elements,
the
semigroup with
two right-zero
elements,
and the
trivial monoid.
It is
clear that
any
divisor
of F is
actually isomorphic
to one
of
these. Thus
the
second part
of
this theorem characterizes
the
irreducible
finite
semigroups
as
the finite
simple groups
and the
subsemigroups
of the flip-flop
monoid.
We
will
say
that
the
class
JC
of
automata
satisfies
Krohn
and
Rhodes' criterion
if for
every
finite
simple group
S
there
is an
automaton
A
tC
having that
5 is a
homomorphic
image
of a
subsemigroup
of
S(A), and, moreover, following
the
last part
of the
Krohn-
Rhodes decomposition theorem,
a
class
K,
satisfying
the
Krohn-Rhodes
criterion, must
contain
an
automaton
A
such that
a
subsemigroup
of
S(A)
is
isomorphic
to the
monoid
F
with
two right-zero
elements.
These
two
forms
of the
Krohn-Rhodes theorem yield
an
immediate corollary.
Corollary 3.3.
A finite
transformation
semigroup
(resp.,
finite
automaton) divides
the
wreath
product
(resp.,
cascade
product)
of flip-flops
if
and
only
if
it has no
nontrivial
group
divisors,
or,
equivalently,
if
and
only
if
it has no
simple
group
divisors.
Such
transformation semigroups (resp., automata)
all of
whose group divisors
are
triv-
ial are
called aperiodic,
and the
result shows that they
can be
represented homomorphically
by
cascades
of flip-flops
(resp., divide
a
wreath product
of flip-flops).
We
begin with last part
of
Theorem 3.2.
3.1.
Krohn-Rhodes
and
Holonomy Decomposition
Theorems
75
Lemma 3.4.
If
S is a
subsemigroup
of
the
flip-flop
monoid
F and S
divides
a finite
semigroup
T,
then
S is
isomorphic
to a
subsemigroup
ofT.
Proof.
with
identity
e and xy = y for any
We
have
Take
such that
maps them
to e, I, and r,
respectively.
By
replacing
e by its
unique idempotent power
and r and by the
unique idempotent powers
of
ere and
ete,
we may
assume that
ere = r and ele = 1. Let f =
(lr)
m
be the
unique
idempotent power
of
Let
be the
unique idempotent power
of fl.
Then
and
and
Clearly
ana
and
g are
distinct. Thus
{e, /, g}
makes
up
a
subsemigroup
of T
isomorphic
to F.
Simplifications
of
this proof establish
the
result
for
the
other
subsemigroups
of F.
Next
we do
some work toward establishing which semigroups
are
irreducible.
Lemma 3.5.
The flip-flop
monoid
F and all its
subsemigroups
are
irreducible.
Proof.
Suppose
F
divides
a
wreath product
of
transformation semigroups
(X x Y, W) =
(X,
S) z (Y, T);
then
by the
above lemma
F W. Let (E, e) be the
identity
and (L, 1}
and
(R, r) be the two right-zeros in the
embedded copy
of the flip-flop.
Case
1. r t.
Since
(R,
r)(L,£)
= (L, ), we
have
rt = l
and, similarly,
re = r,
whence
t
cannot equal
e.
Similarly
one
shows
r
cannot equal
e.
Thus
e, r, l T are
pairwise distinct,
so the
projection
from
W to T is
injective
on the
embedded copy
of F.
Thus
F
embeds
in T.
Case
2. r = t. We
examine
the right
coordinates
of the
embedded
flip-flop
monoid.
We
have E,R,L
: Y S.
Since
(L, l) and (R, r) = (R, t) are right-zeros in the
embedded copy,
for all y e Y,
L(y)L(y
• I) =
L(y), R(y)R(y
• t) =
R(y), L(y)R(y
• I) =
R(y),
R(y)L(y
• t) =
L(y). Similarly, since
(E, e) is the
identity
in
this copy
of F,
also
E(y)F(y
• e) =
F(y)
and
F(y)E(y
• e) =
F(y)
for
each
F e {E, L, R}, y € Y.
Since
r = t, R
cannot equal
L, so
there exists
a yo e Y
with R(yo)
=£
L(yo).
We
have
R(yo)R(yo
' I) =
R(yo)
and
R(y
0
)L(y
Q
• t) =
L(J
O
), whence R(y
0
- £) ^
L(y
0
• t). Let
yi
= yo -1.
Since
te = t — et, we
have
y\ • e = y\ = y\ • t.
Thus,
the
above equations
applied
to y = yi
show that (L(yi), R(yi),
£(ji)}
has the
multiplication table
of F. We
already know that L(yO
/=
R(yi),
so
L(yi)E(yi)
=
L(yi) andL(yi)R(yi)
—
R(y\) imply
E(yi)
^
R(y\). Similarly E(y\)
^
L(y\).
Thus
we
have
an
embedded copy
of F in S.
The
proofs
of
irreducibility
of
other subsemigroups
of F are
simplifications
of
this
one.
Lemma 3.6.
A
nontrivial
finite
group
is
irreducible
if
and
only
if
it is a
simple
group.
Proof.
Let G be a
nontrivial
finite
group.
If a
group
G is not
simple, then
it has a
proper
normal subgroup
N, so by
Lemma 1.16
G is not
irreducible. Conversely,
if G is a
simple
group
and G
divides
(X, 5) =
(^2,
52)
2
(Xi,
Si) for
some
finite
transformation semigroups
(Xi,
Si) (i = 1, 2),
then
by
Proposition 1.11 there exists
a
permutation group
(Z, G)
with
Z
c Xi x X\ and
subgroup
G of S
mapping homomorphically onto
G.
<p
: G -» G.
76
Chapters. Krohn-Rhodes Theory
and
Complete
Classes
Consider
the
projection homomorphism
TT\
from
S to S\
restricted
to G. Let N = ker n\.
Let
lg =
(i,e) denote
the
identity
of G.
Clearly,
e
2
= e Si.
Define
a
homomorphism
:
ker i -+ ' = x • • • x (\ \
times)
by
\jr(h,
e)fa)
= hfa • e) for all xi e XL
(This defines each jci-coordinate
of the |Xi
(-tuple.)
Of
course
ty(h, e) can be
considered
a
function
from
X\ to Si.
Now, given
(h, e),
(h
f
,
e) e N = ker n\, if
\j/(h,
e) =
i/r(h',
e),
then
for all fa,x\) e X
2
x X\ we
have
(xi,x\)
• (h, e) =
(x2,x\)
•
(i,e)(h,e)
=
(x
2
•
ifa)hfa
•
e),xi
• e) = fa •
ifa)h'fa
•
e),x\
• e) = fa,x\) •
(i,e)(h',e)
=
(x
2
,x\)
•
(h',e),
whence (h,e)
=
(h',e),
and so ^ is
injective.
We
also have,
for
each
*i € Xi,
ir((h,e)(h',e))fa)
= hfa •
e)h'fa
• e • e) = hfa •
e)h'fa
• e) =
(ty(h,
e)(xi))(ifr(h',
e)fa)).
Thus
iff
is an
injective homomorphism
on N.
Thus
G/N is
isomorphic
to the
subgroup
n\ (G) of Si and N is
isomorphic
to the
subgroup
ty (N) of
S*
1
.
Therefore
every
Jordan-Holder
factor
of G
occurs
as a
Jordan-Holder
factor
of G/N or of
N,
then hence divides
G/N or N, and
hence divides
S\ or
S*
1
.
But
since
= G
is
simple,
G is a
Jordan-Holder
factor
of G.
This proves
G
divides
S*
1
or Si. In the
latter case,
we are
done.
In the
former case,
G
divides
S = S
2
x • • • x S
2
.
Take
H
a
subgroup
of the
direct product mapping onto
G,
say,
r] : H G, and let HI
denote
the
subsemigroup
of S
2
consisting
of
those elements
s, of S
2
such that
s,
occurs
as the ith
component
of
some element
of H.
Consider
the
homomorphisms
p
t
: H, G
given
by
Pi(si)
=
r/(l,...,
1, Sj,
1,...,
1), si
HJ-,
1 in
each coordinate
j i
denotes
the
idempotent
of S
2
occurring
in
that position
in the
identity element
of the
group
H. Let
k
=
\Xi\. Then
TJ(SI,
...,
sjO =
PI(SI)
• • •
Pk(sk)
for all
(s\,...,
Sk)
€ H, and
since
the
Pi(Si)Pj(sj)
=
Pj(sj)pi(si)
(si €
Hi,Sj
e
Hj)
always holds
for / / j, it
follows that
77(51,...,
s
k
)pi(sf)ri(s\,...,
s
k
)~
l
=
Pi(si)pi(s-)pi(si)-
1
e
pi(H
{
). Thus each /?,(#/)
is
a
normal subgroup
of G.
Since
G is not
trivial
and n is
surjective, these subgroups cannot
all be
trivial.
Therefore
by
simplicity
of G
there
is an /
such that
pi(Hj)
= G,
whence
G
divides
S
2
.
This proves that
G is
irreducible.
Lemma 3.7.
If (X, G) is a
permutation-reset
transformation
semigroup, then
(X, G)
<(X,{U})KG,G).
Proof.
Recall that
(X,
{I*})
has a
semigroup consisting
of the
identity permutation
1* and
all
constant maps
c
x
: X • X,
with c
x
(x'}
= x for all x' e X.
Define
TJS
: X x G -» X
by (x, g) t-+ x • g. For g e G c G,
define
g by fa, gi) • g = fa • l
x
, gi • g) =
fa,
gig)-
For c
x
€ G,
define
c
x
by fa, gi) • c
x
= fa •
c
x
.
g
-i,gi
• 1) = (x •
gf
1
, gi).
Then
^((*i,
gi) • I) = x\ • gig =
Vfa,
gi) • g, and
^(fa,
gi) • c
x
) =
ir(x
•
gf
1
,
gO =
x
'
g^gi
= x =
i/ffa,
gi) • c
x
.
This proves
the
lemma.
D
Lemma 3.8.
If
(X,
{lx})
is a finite
transformation
semigroup
with
transformations
consist-
ing
of
the
identity
transformation
and all
constant
maps
on X,
then
(X,
{lx}) embeds into
the
direct
product
of
copies
of
the flip-flop.
Proof.
Let A =
{0,1}; then
the flip-flop is (A,
{1
A
}).
Let n be
such that
2
n
>
|X|.
Let
/ : X -» A" be any
injective function.
Let // : X ->• A be the /th
component
of /.
Let
x' € X and s €
{lx}- Then
s = c
x
for
some
x e X, or s = \x- Let
^(c
x
)
=
(c/^),...,
c/
n
(
X
))
and
^(Ix)
=
(!A»
• • •
>
IA)-
Then
ty is an
injective homomorphism.
3.1.
Krohn-Rhodes
and
Holonomy Decomposition
Theorems
77
We
have
On
the
other hand,
This establishes
the
embedding.
Holonomy.
We
introduce
the
holonomy groups
and
related
notions.
First,
fix a finite
transformation
semigroup
(A, 5). The
holonomy decomposition theorem (Theorem 3.9),
from
which
we
shall derive
the
Krohn-Rhodes prime decomposition theorem,
is
proved
by
a
detailed study
of how 5
acts
on
subsets
of A.
Recall that
if q A and s € S,
then
Let
In
this section,
we
write
A,
for the
identity
transformation
on A.
Then
clearlv
acts
on Q as
just
described.
We
have
a
reflexive
and
transitive relation
on Q
given
by
there exists
Consequently,
we
have
an
equivalence relation
on Q,
and
For
each equivalence class
in
choose
a
unique representative
Observe that
always
holds, since
then
tor
appropriate
we
have
and
implying
whence
Bv
svmmetrv.
it
follows
that
Thus,
the set of
representatives
of the
equivalence classes
is
partially ordered
by
We
also write
if
but
not
Thus,
We
say p is a
tile
of q and
write
and
for
all
i
implies
The set of
tiles
of q for any
is
denoted
by
Since
Q
contains
the
singletons,
for
equals
the
union
of its
tiles,
Define
H
q
to be the set of
permutations
of B
q
induced
by
elements
of s S
x
.
That
is, if for s € S\ the
function
s
q
: Q Q
defined
by
s
q
(z)
= z • s = {a • s \ a € z] (z € Q)
restricts
to s
q
: B
q
B
q
and
permutes
the
elements
of B
q
,
then
s
q
H
q
. H
q
is
called
the
holonomy
group
ofq in (A, 5), and
clearly
H
q
divides S,
16
and
(B
q
,
H
q
)isa
permutation
group
called
the
holonomy
permutation
group
of q.
Suppose
and
then
we can
wnte
and
for
some
Let
then
we
claim
Since
q is finite,
implies
This shows that
s
permutes
the
elements
Let
; we
have
and
so
Suppose
with
Let
be
such that
is
the
identity permutation
on q, and let
Then Since
, we
have
16
In
the
exceptional
case
H
q
= [
q
], we
have that division
of 5 is
guaranteed
since
5
contains
an
idempotent.
In
all
other
cases,
the
identity
transformation
on B
q
is, of
course,
represented
by the
idempotent
power
of any
nontrivial
s
q
H
q
,so
that
H
q
is a
quotient
of the
subsemigroup
of 5
consisting
of
those elements
s for
which
s
q
permutes
B
q
.
78
Chapter
3.
Krohn-Rhodes Theory
and
Complete
Classes
and
so
We
have
and. since
z is a
tile
of a. it
follows that
or
whence
This proves
if z is a
tile
of a,
then
z • s is
also
a
tile
of q.
Moreover,
if
and
,
then
Since
B
q
is finite,
this proves
s
permutes
the
elements
of B
q
.
Thus
s
q
H
q
as
claimed.
Furthermore,
q = p
implies that, say, (B
q
,
H
q
) is
isomorphic
to
(B
p
, H
p
).
We saw
s
=
u
q>p
v
q>
p
permutes
the
elements
of q
and, similarly,
v
qtp
u
qtp
permutes those
of
p.
Take
n > 1
such that
(u
q
,
p
v
qtp
)
n
is the
identity permutation
of q.
Letu
q
,
p
=
v
q
,
p
(u
q
,
p
v
q<p
)
n
~
l
.
Then u
q<p
u
q<p
acts
as the
identity
on q and
also
u
q
,
p
u
q
,
p
acts
as the
identity
on p.
Forz
6 B
q
,
then
z i-> z •
u
q
,
p
e B
p
is
bijective with inverse
z' *-> z' •
u
q
,
p
.
For s
q
e H
q
, the map
s
q
i->>
Uq,
p
s
q
Uq
tp
€ H
p
is an
isomorphism
of
groups with
(z-u
q
,
p
)-u
q
,
p
s
q
u
q
,p
=
(z-Sq)'U
qtp
.
Hence,
we
have
an
isomorphism
of
permutation groups.
Now
for
each
q let u
q
=
u
q<q
and u
q
=
u
q
,
q
be
elements
of 5
A
determining iso-
morphisms
as
above between
the
holonomy permutation group
of q and
that
of its
unique
representative
q.
Observe that since
A is
equivalent only
to
itself,
we can
take
U
A
and U
A
to be the
identity.
Define
the
height
of a
member
q of Q by
h(q)
= 0 if q is a
singleton
and
otherwise
inductively
by
h(q)
= i
when
qo < q\ < • • • < q
l
\ — q is a
longest such chain
in Q
ending
in
q
with h(qo)
= 0 and
h(qj)
= j (j =
0,...,/
—
1). The
singletons
are
exactly
the
elements
of
height zero,
and we
call
h =
h(A)
the
height
of (A, 5).
Note that h(q)
=
h(A)
implies
A = q.
Note also that
if q is
equivalent
to q,
then
we
have h(q)
=
h(q) (using
the
fact
that
p < p' if and
only
if < p'
applied
to the
elements
in the
maximal chains
up to
q and
~q).
It is
important
to
note that
if
h(p)
=
h(p')
> 1 and p p'. s,
then actually
p'
is
equivalent
to p:
ifh(p)
= i, we
have
qo < •• • < qi = p < p', and so by
h(p')
= i the
last
inequality cannot
be
strict, i.e.,
p = p'.
Clearly,
for
each
i
with
0 / h, Q
contains
at
least
one
element having height
i.
For
each
i (1 < i < h),
define
(#,-,
%•) to be the
direct product
of the
holonomy
permutation groups
of the
height
i
representatives
in Q.
Then
#, =
fl/tcp)^
Bj
an
^
Hi
=
Y[h(j)=i
HP-
Th
en
(#/»%•)
is a
permutation group
and
(#,, 'H,)
is the
associated
holonomy permutation-reset transformation semigroup obtained
by
adjoining
all
constant
maps taking values
in #,.
Denote elements
of #, by
boldface variables
b or b/.
Notation. Suppose that
b is a
tile
of
some
p Q
with height
i and the p
represents
its
equivalence class. That
is, b - p and p =
JJ.
Then
we
denote
by
[b]
p
any
arbitrary element
of
fy
containing
tile
b in the
p-position.
Also,
if g € H
p
,
then
we
write [g]
p
for any
arbitrary element
of ,
containing
g
in
the
^-position
and
identity elements
in all
other positions. Observe that
BH
= B
A
and
/
H
h
= HA
since
A is the
only
set of
height
h.
Thus
b/, =
[b
h
]
A
=J h for all
tiles
bh of A and
[g]
A
= g for all
permutations
g in the
holonomy group
of A = A.
Theorem
3.9
(holonomy
decomposition
theorem).
Let (A, S) be a finite
transforma-
tion
semigroup;
then
(A, 5)
divides
a
wreath product
of its
holonomy
permutation-reset
transformation
semigroups
(B\,
Hi)l"'l
(Bh,
'Hh)-
3.1.
Krohn-Rhodes
and
Holonomy Decomposition
Theorems
79
Proof.
Let * be a new
symbol
and
define
inductively
as i
goes
from
h to 1 by
and,
letting
,
which
we
suppose
has
already been well
defined
for
we
define
(It
is
understood that
the
last case will apply also
if /? = *.)
Observe that
in the
second case
is
the
representative
of the
equivalence class
of p, and so
and in
fact
Observe
that
if
is not
then
.Thus
is
eithe
or a
singleton.
If
then
can
have
no
effect
on the
value
of
in
the
above definition.
If
h(p)
= i,
then only
the
-position
of b, may
affect
the
value
of
ni. In all
cases
at
most
one
position
of b, can
affect
the
value
of n
(
.
Let
* be the set of
(bi,...,
b/J
such that ni(bi,..., b/,)
is a
singleton.
The
17,-'s
will give
our
covering
map n by
"successive approximation." Indeed,
an
easy induction
establishes that
for
every
Let
be
given
by
letting
be
the
unique element
of the
singleton
We
show that
is a
surjective
function:
given
an
arbitrary
a € A, we
choose
containing
a.
Then
a
and
Now
assuming
are
defined
and
with
we
proceed
by
induction
for
and
let
In
the
case h(p)
< i,
existence
of
elements
of
height
i in Q
guarantees that
an
arbitrary
fixed
b*
exists.
In the
case h(p)
= i,
since
i > 0 the
fact
that
p is the
union
of its
tiles
guarantees
the
existence
of a
tile
b' of p
containing
a, so b may be
taken
to be b' • u
p
.
It
is
clear that
a e
ni,
(b,,...,
b/,)
and h(^
(b,,...,
b/,))
< i
since either
(1)
h(p)
< i,
and
so
?/,-(b,-,...,
b/,)
= p
which contains
a, or (2)
h(p)
= i, and
then
/7,(bi»...,
b/,)
is a
tile
b • u
p
of p
containing
a. It
follows
by
induction that
a e
f?i(bi,...,
b/,)
and
h(rii(bi,...,
b/,))
< 1,
whence »/i(bi,..., b/,)
is the
singleton {a}. This proves that
r\ is
surjective.
We
shall
use
Proposition
1.10
to
establish
the
division.
In the
terminology
of
Proposition
1.10,
surjectivity
of r\
gives
an
element
(bi,...,
b/,)
e as a
lift
of
state
a.
Recall that
an
element
of the
wreath product
is
given
by
describing
its
component
actions.
(See
the
discussion
following
the
definition
of
wreath product
in
Section
1.3.)
Thus
to
specify
lift
of an s € 5 to the
wreath product
we
need
to
give appropriate functions
fori
For
is mst an
element
of
Such
an h
-tuple
of
functions
determines
a
transformation
in the
wreath product.
80
Chapter
3.
Krohn-Rhodes Theory
and
Complete
Classes
We
define
a
lift
for a
member
s of S to the
wreath product
by
defining
for
i
=
h,...
,1
inductively, First,
We
record
that
which
has
height less than
This
is
just
the
observation that
Fixing
tor the
moment, write
for
for
Then, wnting
p for
ana
for
define
inductively
as i
goes down
from
h — 1 to 1, by
Of
course h(p)
and
h(q)
are
necessarily less than
/ + 1. It is
understood that
the
third case
applies also
if p = *. In the first
case, constant
[b •
u
q
]~
is a
constant
map
taking
a
value
in
Bi
whose
g-position
is a
particular tile
of q.
Clearly this constant
map
lies
in Hi. In the
second
case,
we
have h(D\
= i =
h(a}
= h(n • s} > 1.
whence
a = D • s
==
».
Therefore
This
implies
that
represents
an
element
of
so
that
In
all
cases.
as
required.
Now
we are
ready
to
establish
the
division. Fixing
we
again write
and
suppose
by
induction
for
that
for
as
defined
above
we
have
We
have already observed that this holds with
/ + 1 = h, and now
assuming induc-
tively that
it
holds
for i + 1, we
establish
it for i (i > 0). We
must show that
holds.
Now
we
shall
consider
four
cases.
Case
1.
and
We
have
-lest
imply
contradicting
since
by
definition
of n/
since
Now
since
where according
to the
definition
Therefore,