D?m?si P., Nehaniv C.L. Algebraic Theory of Automata Networks. An Introduction
Подождите немного. Документ загружается.
Chapter
4
Without
Letichevsky's
Criterion
In
Chapter
5 we
will
see the
importance
of
Letichevsky's criterion
in the
composition
of
automata networks.
In
this chapter
we
consider networks
of
automata without Letichevsky
's
criterion.
In
particular,
we
describe several
types
of
networking with
very
restricted struc-
ture
of the
permitted links. Assuming that
the
component automata
are
rather simple
of
particular
types,
the
resulting networks that
can be
constructed
are
already computation-
ally
as
general (with respect
to
homomorphic representation)
as
what
can be
constructed
with unrestricted networking.
We
also show that
the
hierarchy
of v
i
-products (automata
networks
in
which there
are at
most
i
links
to an
automata from components
of
the
net-
work)
is
strict
for
this
type
of
representation.
We
prove even more:
The
ao-V
i
-hierarchy
is
strict
for
both homomorphic representation
and
homomorphic simulation.
In
addition,
the
v/
-hierarchy also
has
this property.
This
means that
the
number
of
permitted links
may
have
a
strong
influence
on the
computational capacity
of
the
network
if
component automata have
a
certain structure (i.e.,
satisfy
the
so-called semi-Letichevsky criterion).
4.1
Semi-Letichevsky
Criterion
We
start
with
the
following
statement.
Proposition
4.1.
Let A = (A, X, 8) be an
automaton having
the
semi-Letichevsky criterion
and
let a € A, jc, y e X, p e X*, (a, x) (a, y), (a, xp) = a
(such that
for
every
q e X*, a (a,
yq)).
For
every automaton
A'
there exists
a
single-factor
product
M. of
A
such that
A can be
represented homomorphically
by a
diagonal product
of
its
connected
state-subautomata
andM..
Moreover,
we
also have this
property
for a
single-factor
loop-free
product
M.
of
A
whenever
(a, x
k
) = a
holds
for
some
positive
integer
k.
Proof.
Let A =
(A',
X', ') be an
arbitrary
automaton.
Assume
that
(a, x
k
) = a
holds
for
some
positive
integer
k and
then
construct
M. =
A(X',
(p)
such that
for
every
b 6 A, x' €
X', (b, x') = x. In
this
case,
M. is a
single-factor
loop-free
product
of A.
Otherwise,
put
p
= x
1
...x
m
withai
=
(a,x),a
2
=
(a
1
,x
1
),
...,am
=
(a
m-1
,x
m-1
),a
=
(a
m
,x
m
),
111
112
Chapter
4.
Without Letichevsky's
Criterion
and
for
every
b e A, x' e X', let
Then
At is a
single-factor product
of A.
In
both
cases
we
have S(8(a,
x),
(p(8(a,
x), q)) ^
8(8(a,
y),
<p(&(a,
y),
r)),
q, r e
X*.
(Otherwise, contrary
of our
assumptions,
A
could
satisfy
Letichevsky's criterion.)
By
Proposition 2.28, this implies
the
validity
of our
statement.
Recall that
the
automaton
£
2
=
({0,
1},
{*i,
x
2
},
<$£
2
),
%((),
*i) = 0,
«$£
2
(0,
x
2
) =
5f
2
(l,
*i) =
5£
2
(1,
#2) = 1 is
called
the
(two-state) elevator.
Let
£ be
the
class
of
all
automata
A =
({0,
...,n},X, 8
A
),
n =
l,2,...,
8
A
(0,
x) =
0,
5.4(n,
x) = n, and
for
all x e X. We
have
the
following.
Lemma
4.2.
Every
automaton
in C. can be
represented
isomorphically
by an
otQ-V2-power
of
the
elevator.
Proof.LetA
=
({0,...,
n}, X, 8
A
) e
C.lfn
= 1,
then
A
can
be
represented isomorphically
by
a
quasi-direct power
of the
elevator having
a
single factor. Thus
we may
suppose that
n > 1.
Consider
the
ao-vz-power
£%
+1
(X,
<p\,...,
(p
n
+i)
of €2 in the
following way.
For
arbitrary (£1,...,
4+0 e {0,
l}
n+l
,x
e X,
andf
e
{1,...
,n + 1}, let
Clearly then
we can
assume that
<p
t
(t\,...,
l
n
+\,
x)
really depends only
on the
input letter
iff
= 1;
moreover,
it
depends only
on the
input letter
and its (t
—
l)th
variable
if 1 < t < n.
In
addition,
it
depends only
on the
input
letter
and its (n
—
l)th
and nth
variables
if t = n +1.
Thus
it is
true that
££
+1
(^>
<P\»•
•
•»<Pn+i)
is an
«o-V2-power
of £2
-
One can
also
verify
by a
trivial computation that, using
the
short notation
d\...
d
n+
\
for
(d\,...,
d
n+
\)
{0,
l}
n+l
,
the
mapping
4> : A ->• {0,
l}
n+1
given
by
is a
state-isomorphism
of A
onto
a
subautomaton
of
4.1
.
Semi-Letichevsky Criterion
113
Lemma 4.3.
Every
monotone
automaton
can be
represented
homomorphically
by a
diagonal
product
of
automata
from
L.
Proof.
Let £' be the
class
of all
automata
A =
({0,
. . . , n}, X,
8
A
),
n =
1,2,...,
S*(0,
*) = 0,
8
A
(n,
*) = n and
8
A
(j,
jc)
€ {0, ;, j + 1}, 0 < j < n, for all x e X.
First
we
prove that
all
elements
in £' can be
represented homomorphically
by a
diagonal
product
of
factors
from
£.
Consider
an
arbitrary automaton
A =
({0,
. . . , n}, X, 84) e £'
with
n > 1. (We can
take
out of
consideration
the
trivial
case
n = 1.)
Define automata
t),
= 2,
...,n,
having
A(j,x)
ifj =
t-l,
S
for
all
jc
e X.
Clearly then
A
t
e £ for all t = 2, . . . , n.
AUTOMATON
A
n
Letfi
c
A
2
x-
•
-xA
n
withB
=
{(1,...,
1),
(2,....
2), (2,
3,....
3),....
(2,
...,£,
...,€),...,
(2,...,
n)} U
{(l1...,
ln) | 0 e
{€1,...,
€„}}.
By an
elementary computation
we
have that
the
mapping
\js
: AI x ... x A
n
->
{0,...,n} with
is a
state-homomorphism
of an
appropriate state-subautomaton
of the
diagonal product
Ai A • • • A A
n
onto
A.
Using
the
transitive property
of the
diagonal product,
to
establish
our
assertion
we
shall prove that every monotone automaton
can be
represented homomorphi-
cally
by a
diagonal product
of
factors
from
CJ.
Consider
a
monotone automaton
D = (D, X,
8-p)
and
denote
a
partial ordering
on
D
for
which
d
-
D
(d,x),d
D,x X.
Take
a
rearrangement
d\,...,
d
n
of the
elements
of
D
such that
for
every
d
t
,
dj
D, di dj, and d, < dj
implies
i < j.
Consider
all
bijective mappings
of the
form
f
s
:
{di,
...,d
n
}
{1,...,
n], s =
!,...,«!.
For
every
mappuig
f
s
(1 s
n!),
define
an
automaton
A
s
=
({0,
...,n},X,8
s
)
having
It is
clear that
A
s
e £', 1 < 5 < «!.
Take
the
diagonal product
M — A\ A • • •
A.A
n
.
We
shall prove that
M.
homomorphically represents
the
automaton
A.
Define
the set B C
{0,...,
n}
nl
as
follows:
(1)
For
every
d^ € D
there
exists
a
(b\,...,
b
m
) e B and an s e
{!,...,«!}
having
f,(<to
= b,.
114
Chapter
4.
Without
Letichevsky's
Criterion
(2)
For
every (b1,...,
b
m
) e B and s, t
{1,...,
n!},
0
{b
s
,, b
t
,} implies
f
(b
s
)
=
f
t
-l
(b
t
).
(3) For
every pair (£1,...,
)) e B, t
{1,..., n\],
b
t
0
implies that
for
arbi-
trary
xi,...
,x
r
e X
there exists
an s
{!,...,«!}
with
f
(b
s
)
= f
(b
t
)
and
f
(8
s
(b
s
,
x
1
.
..x
j
))
=
8
v
(f (b
t
),
Xl
.
..*,-),
7 = 1,
....
r.
Let
i/r : B
{d\,...,
d
n
] be a
mapping
for
which
((b\,...,
b
n
\))
= dk
whenever
(b\,...,
b
n
\)
e B has a
component
b
t
, t
{1,...,n!} with
f
(b
t
)
= dk.
By
conditions
(1) and
(2),
\jf
is a
well-defined surjective mapping. Using
(3) and the
definitions
of the
mappings
S
, s =
1,...,
n\,
\lf((&i(b\,x),...,
8
m
(b
n
\, jc)))
=
8x>(if((bi,
...,
b
n!
)},
x),
(b
1
,
...,
b
n
\)
€B,xeX.
Therefore,
the
diagonal product
A\ A • • • AA
n
has
a
state-subautomaton (with state
set B)
having
a
state-homomorphism onto
A.
By
Lemmas
4.2 and 4.3 we can
immediately derive
the
next statement.
Theorem
4.4.
Every monotone automaton
can be
represented
homomorphically
by an
-V2-product
of
the
elevator.
Now
we
turn
to the
automata having
the
semi-Letichevsky criterion.
Let A =
(A, X,
<5)
be an
automaton satisfying
the
semi-Letichevsky criterion. Given
a
state
a € A,
put
A'
a
=
A'a
= 0 if
there exists
no x e X, p e X*
having
(a, xp) = a.
Otherwise,
let
p
e X* be the
shortest word having this property
for an
appropriate
x e X, and put
Given
a
positive integer
r, a
nonnegative integer
s, we say
that
A is (r,
sO-weighted
if
there
exists
an a e A
with \A'
a
\
= r and
|A£|
= s. (Of
course,
it may be
possible that
A
is (r,
5)-weighted and, simultaneously,
(r',
s')-weighted such that
(r, s) /=
(r
;
,
5')
(with
r,
r' >
0).)
Proposition
4.5.
Let A be an (r,
s)-weighted automaton
(having
the
semi-Letichevsky
criterion).
There
exists
a
single-factor
product
B
of
A
such that
B is an (r, r —
l)-weighted
automaton.
Proof.
Let A = (A, X, 8) be an (r,
s)-weighted automaton (having
the
semi-Letichevsky
criterion). There
are a e A, x, y e X, p €
X*,8(a,x)
^
8(a,y),8(a,xp)
= a
with
\A'
a
\
=
\xp\
= r,
IA^I
= s
(such that
for
every
q € X*, a ^
8(a,yq)).
Put xp =
xi • • • x
r
,
xi,...,
x
r
€ X.
Define
(p
: A x X -> X
such that
for
every
a' e A, x' € X,
It is
clear that
the
single factor product A(X,
(p)
of A is an (r, r —
l)-weighted
automaton.
Define
the
automaton
£'
k
=
({1
,...,/:,*},
{xi, x
2
},
8'
k
)
with 8'
k
(i,xi)
= i + l
(mod
k),
<%(*>
*i)
=
*>
^fe(
1
'
*2) =
<%(*'
JC
2)
= *,1 <i <k. We say
that
£'k is the
semi-elevator
of
length
k.
4.1.
Semi-Letichevsky
Criterion
115
SEMI-ELEVATOR
£'
k
Lemma
4.6.
Let A =
(A,X,8)
be an (r,
s)-weighted automaton
(having
the
semi-
Letichevsky
criterion).
The
semi-elevator
of
length
r can be
represented
homomorphically
by
a
diagonal
power
B
s+1
,
where
Bis a
single-factor
product
of'A.
In
particular,
ifs = r
—
l,
then
we may
assume that
B is an
input-subautomaton
of
A.
Proof.
By
our
conditions, there
are a € A, x, y e X, p e X*,
8(a,
*) ^
8(a,
y),
8(a,
xp) =
a
with \A'
a
\
=
\xp\
= r,
\A'^\
= s
(such that
for
every
q X*, a
8(a, yq)).
For
technical
reasons,
we put a\ = a and xp =
z\*--Zk such that
z\,...,
Zk
€ X, k > 1.
Moreover,
we
put
a,
+1
=
8(a,
z\ • • •
z/),
1 < i < k, and A' =
[a\,...,
ak}.
Let us
consider
the
semielevator
£'* of
length
k
having
£'
k
=
({1,...,
k, *},
[xi, X2\,
8'
k
)
with
8
k
(i,
x\) =
i
+ 1
(modfc),
8'
k
(*,
*1 = *,
8
k
(i,
*
2
) =
8
k
(*,
x
2
) = *, 1 < i < k.
We
prove that
£'k can be
represented homomorphically
by an
appropriate diagonal
power
B
s+l
such that
(1)
B is an
input-subautomaton
of A if s =
\p\,
and
(2)
# is a
single
factor product
of A if s <
|/?|.
Let
a,,,...,
a,-,
€ A' be
distinct states such that
8
(a
fj
,
yi
j
)
e A' for
every y
ij
.
e X, j =
l,...,s.
Ifs
=
\p\,
then
let B be the
input-subautomaton
of A
with input
set {x, y}.
Obviously,
then
8(at,x)
=
a
i+
i(modk)
A' and
(aj,
y) =
a,+i(mod*)
A'
hold
for
every
i €
{!,...,
k}, j
{2,...,
k}. In
addition, (a1,
y) i A'.
Ifs<
\p\,
then
let B =
A({x,
y},
<p)
defined
by
Clearly, then
B has a
state-subautomaton
B' =
(B',
{x, y}, 8')
generated
by its
state
a\
such that
for
appropriate distinct states
a\,...,
a^ we
have
5'(a,,
x) = fl,+i(
m
odik)>
and
simultaneously,
for
every
j e
{!,...,*},^
e X*,
8'(ai
r
yq)
£ A'.
Consider
the
state-subautomaton
D = (D, Y, 8") of the
diagonal power (B')
s+l
generated
by the
state
(0i,
...,a
s+
i).
For
every positive integer
m, we
obtain
8"((a\,...,
a
s
+i),x
m
)
=
(flm+KmodJt),
•••, «m+5+i(mod*))-
Simultaneously,
if r =
x
u
y,
then
for
every
q € [x,
y}*,
there exists
a t €
{1,...,
s + 1}
with 8'(a
t
,
rq) £
(a\,...,
a
k
}.
Hence
8"((ai,...,
a
j+
i),
rq)
(a|rq|+l(mod/fe)»
• • • ,
a\rq\+s+l(modk))-
116
Chapter
4.
Without Letichevsky's
Criterion
Define
the
mappings
: D
{1,...,
k, *}, :
{x,y}
{x
1
,
x
2
}
with
fa(x) =
jci,
(y) = x
2
- By an
elementary checking,
we get
that
is a
state-homomorphism
of
a
state-subautomaton
of
B
s+l
onto
£'*.
The
proof
is
complete.
Proposition
4.7.
Let A = (A, X, 8) be an (r,
s)-weighted automaton
(having
the
semi-
Letichevsky
criterion).
Every
monotone automaton
can be
represented
homomorphically
by
an
cti-v
2 +l)
-product
of B,
-where
B is a
single-factor
product
of A. In
particular,
if
s
= r — 1,
then
we may
assume that
B is an
input-subautomaton
of
A.
Proof.
Using Theorem 4.4,
it is
enough
to
prove that
the
two-state elevator
can be
represented
homomorphically
by a
diagonal power
B
s+1
such that
(1)
Bis
input-isomorphic
to an
input-subautomaton
of A if s = r — 1 , and
(2)
Bis a
single factor product
of A if s < r — 1 .
But
it is
evident that every semielevator
of
length
k > 1 can be
mapped homomor-
phically onto
the
elevator. Thus, using Lemma
4.6,
the
proof
is
complete.
D
Next
we
prove
the
following lemma.
Lemma
4.8.
Let A =
(A,X,8)
be an (r,
s)-weighted automaton
(having
the
semi-
Letichevsky
criterion).
Then
every
product
C x
T>(Y,
<p\,
$2) of a
counter
C of r
states
and
a
monotone automaton
D can be
represented
homomorphically
by an -v
(s+l)
-power
of
A. In
particular,
ifs — r — 1,
then
C x
D(Y,
, ) can
also
be
represented
homomor-
phically
by an
ao-V2(
s
+i)+i-power
of
A.
Proof.
By
our
conditions,
there
area
A, x, y e X, p e X*,
8(a,
x) ^
8(a,
y),
8(a,
xp) =
a
with \A'
a
\
=
\xp\
= r,
|A£|
= s
(such that
for
every
q e
X*,a 8(a,
yq}}.
Ifr = 1,
i.e.,
\p
| =0,
then
our
statement
is a
direct consequence
of
Proposition
4.7.
Thus
we
assume
r
> 1
(i.e.,
\p | > 0). For
technical reasons,
we put a\ — a and xp = x\-
--x
r
such
that
xi,...,x
r
€ X, r > 1.
Moreover,
we put
a
(+
i
=
8(a,
x\ • • •
jc
(
),
1 < i < k, and
A'
=
{fl
1(
...,0r}.
First
we
recall that
all
counters have singleton input sets
and
thus they
are
autonomous
automata.
But
then
an
arbitrary product
of a
counter
and any
other automaton coincides with
the
«o-product
of the
considered counter
and the
considered automaton.
By
Proposition 2.65,
this single-factor product
is
also
a
monotone automaton. Thus
we
will assume without
any
restriction that
C x
T>(Y,
<p\
, ^2) is an
ao-product.
If
s = r — 1,
then
8
(a,-,
x) =
a,+i(
m
odr)
holds
for
every
a, € A'. In
this
case,
the
subautomaton
of A
with
the
state
set A' and the
(singleton) input
set {x}
forms
a
counter
of
r
states.
In
addition,
if s = r
—
1 ,
then
by
virtue
of
Proposition 4.7,
we can
also represent
D
by an
oro-V2
(s+1)
-power
of A.
Thus,
C x
D(Y,
, ) can be
represented homomorphically
by
an
ao-product
of two
automata such that
the first one is an
ao-product
of A
with
a
single factor
and a
second
one is an
ao-V2
(s+1)
-power
of A. But
then,
by
Proposition
2.63,
4.1.
Semi-Letichevsky
Criterion
117
C
x
T>(Y, <p\,
<p2)
can be
represented homomorphically
by an
ofo-V2(j+i)+i
-power
of A.
Thus
we are
ready
if s = r — 1.
Now
let s < r — 1.
Then, applying Proposition 4.5,
we can use the
above treatment
for
a
single-factor product
B of A.
We
also need
the
following.
Lemma 4.9.
Let
CA
be the
least
common
multiple
of
the
length
of
all
cycles
in the
automaton
A
having
the
semi-Letichevsky
criterion.
Then
A can be
represented
homomorphically
by
an
oiQ-pwduct
of
a
counter with
CA
states
and a
monotone automaton.
Proof.
If A
consists
of a
single cycle, then
it
does
not
satisfy
the
semi-Letichevsky criterion,
a
contradiction.
If A is
monotone, then
our
statement
is
trivial. Therefore,
we may
assume
that
A has a
nontrivial cycle,
and
simultaneously, there exists
a
state
of A
which
is not a
member
of
this
cycle.
In
this case,
we
shall show
the
existence
of
automata
A
0
,
...,
A
s
such that
AQ
= A,
the
automaton
A
s
is
monotone,
and
furthermore,
for
every
i e
{0,...,
s — 1}, A{ can be
represented homomorphically
by an
ao-product
of
At+i
and a
counter
C
CA
with
CA
states.
Thus, using
the
obvious
fact
that
the
ao-product
is
associative,
by
consecutive applications
of
Proposition 2.53
we can
represent homomorphically
the
automaton
A by an
ao-product
of
automata
D and A
s
,
where
P is an
ao-power
of
C
CA
and, simultaneously,
A
s
is a
monotone
automaton.
If
A is not
connected, then consider
a
connected automaton
B
having
the
semi-
Letichevsky
criterion such that
A is a
subautomaton
of B. We can
apply
the
above treatment
substituting
A
with
B.
Indeed, then
A can be
represented homomorphically
by an
ao-product
of
C
CA
and Ay
whenever
B has
this property.
Now
we
show
the
existence
of B
provided that
A is not
connected.
Let A be not
connected
and
consider
an
arbitrary automaton
B =
({ao,
...,a
n
},
X U
{jq,...,
x
n
],
SB)
with
(ai,...,
a
n
} = A, £ A,
[x\,...,
x
n
] n X = 0
such that
8e(ao,
x) e A if
jc
e X, and
8s(a,
x) e
[8(a,
x') \ x' e X} if a € A, jc e
{;ci,..., x
n
}.
Clearly then
A is a
subautomaton
of B,
where
B is a
connected automaton
satisfying
the
semi-Letichevsky criterion.
It
remains
to
prove
the
existence
of
automata
A
0
,...,
A
s
having
the
above properties.
To
this statement
we
shall show
the
existence
of A\
such that
the
number
of
nontrivial cycles
in AI is
fewer
than
the
number
of
nontrivial cycles
in AQ.
Applying this result inductively,
we
can
reach that
A
s
does
not
contain
any
nontrivial cycle;
i.e.,
it is a
monotone automaton.
Let
a\,...,
a,-
and
b\,...,
b
}
; be two
cycles
of A
with
a\
—b\.
Observe that
in
this
case
a* 7^ bk, 1 < k <
min(z,
y),
would imply that, contrary
to our
assumptions,
A
satisfies
Letichevsky's criterion with &(at-\,
x) ^
8(at-\,
y) and
8(ai-i,
xp) =
8(ai-\,
yq) = a
for
some
ai-\
€
A,x,y
e
X,p,q
€ X*. We
also have this consequence
if a^ =
bk,
1 < k <
min(z,
j) but i ^ j.
Therefore,
if two
cycles have
a
common element,
then
these cycles should coincide.
Let
a
u
+i,...,
a
v
be a
nontrivial cycle
in A. If
there
are
a
state
a 6
A\{a\,
...,a
n
]
and
words
p, q e X*
with S(a,
p) €
{fl«+i,
...,a
v
]
and
a
€
{8(a
u+
i,
q),...,
(a
v
, q)}, then
A
satisfies Letichevsky's criterion,
a
contradiction.
118
Chapter
4.
Without
Letichevsky's Criterion
Therefore,
for
every
a e
A\{ai,...,
a
n
}
and
words
p,
q e X*
with
(a, p) 6
{a
u+
\,...,
a
v
},
it
holds that
a £
(8(a
u+
i,q),...,
8(a
v
, q)}.
Let
a\,...,
a
u
e A
denote
all
states
for
which
there
are
words
p\,...,
p
u
€ X*
having 8(at,
pi) 6
{««+i,
•..,
a
v
},
i =
!,...,«.
(We
note
that
{a\,...,
a
u
} = 0
may
be
possible.)
Finally,
let A \
{a\,...,
a
v
} =
{a
v+
\,...
,a
n
}
for
appropriate
a
v
+1>
• • • ,a
n
£ A.
(Note that
{a
v+
\,...
,a
n
}
= 0 may be
possible
but
{«!,...,
a
u
,
a
v+
i,...
,a
n
]
^0
because
A
satisfies
the
semi-Letichevsky criterion.)
Hence,
we can
consider
an
arrangement
a\,...,
a
u
,
a
u+
\,... ,a
v
, a
v+
\,...,
a
n
of
the
set
of
states
in A = (A, X, 8)
such that
a
u+
i,
...,a
v
form
a
cycle
of
length
v — u > 1;
moreover,
5(a,,
x)
/ a
;
for
either
l<j<u<i<voru<j<v<i<n.
By
these properties,
we can
define
the
automaton
A\ = (A,
{1,...,
c^} x X, 8') in
the
following way:
For
every pair
a,-
€ A, (7, *) €
{1,...,
CA}
x X let
Consider
the
counter
with
Let
be an
-product
with
and
whenever
be a
mapping with
otherwise.
It
is
routine work
to
show that
iff
is a
state-homomorphism
of Mi
onto
A.
Next
we
show
the
following corollary.
Corollary 4.10. Given
a finite set
/C
of
automata
satisfying
the
semi-Letichevsky
criterion,
let
c
k
be the
least common multiple
of
all
positive integers which
are
lengths
of
cycles
of
auto-
mata
in /C.
Moreover,
let mjc be the
minimal number
of
cycles
of
automata
in K.
such that
every
prime power divisor
ofcjc
divides
at
least
one
of
these lengths
of
cycles.
18
Consider
an
(r,
s)-weighted automaton
A = (A, X, 8) € /C
(with semi-Letichevsky criterion,
s < r).
If
an
automaton
B can be
represented
homomorphically
by a
general product
of
automata
from
/C,
then
it can be
represented
homomorphically
by an a
i-vj-product
of
factors
in K,
with
i < 1
and
j <
mjc
+ 2(5 + 1) + !.
In
particular,
ifs
= r
—
1
and
for
every cycle
of
length
k
in B, the
counter with
k
states,
as
well
as the
counter with
r
states,
can be
represented
homomorphically
by an
oiQ-product
of
automata
in 1C,
then
B can be
also represented
homomorphically
by an
UQ-VJ-product
of
factors from
/C
with
j < m^, + 2(5 + !) + !.
Proof.
Suppose
that
B
satisfies
the
semi-Letichevsky
criterion
and let r'
denote
the
least
common multiple
of the
lengths
of all
cycles
in B.
Then
r' \
c/c- Therefore,
by
Lemma 4.9,
B can be
represented homomorphically
by an
oro-product
of a
counter with
r'
states
and a
monotone automaton
M. On the
other hand,
by
Proposition
4.7,
for
every
(r,
s)-weighted
18
Thus
m/e = 0 if all
cycles
are
trivial (having length
of 1).
4.1.
Semi-Letichevsky
Criterion
119
automaton
A e /C, M. can be
represented
homomorphically
by an
cto-V2(
S
+i)
-power
of a
single-factor product
A' of A,
where
A may be an
input-subautomaton
of A if s = r
—
1.
In
addition,
by our
assumptions,
mjc is the
minimal number
of
cycles
of
automata
in /C
such that every prime power divisor
of
CK.
divides
at
least
one of
these lengths
of
cycles.
If
w/c
= 0,
then
c/c = 1,
leading
to r' = 1.
Therefore,
in
this case
we are
ready.
Consider
the (r,
s)-automaton
A = (A, X, 5) e /C
(having
the
semi-Letichevsky
criterion) with
a € A, x, y € X, p e X*,
8(a,
xp) = a,
8(a,
x) ^
8(a,
y), and
\A'
a
\
=
r,
\A'a\
= s
(such that
for
every
q e X*, a ^
8(a, yq)). Again,
for
technical reasons,
we
put fli = a and xp = z\ • • • z
r
such that
zi,.
•., z
r
e X (r > 1).
Moreover,
we put
a
i+
i
=
8(a,
zi • • •
Zi),
I < i < r, and A' =
{a\,
...,
a
r
}.
Let c
denote
the
least common
multiple
of r and the
lengths
of
cycles
in B and
define
the
ao-product
B' = C
c
x
A(X,
(p\,
^2)
of
the
counter
C
c
=
({I,
...,c},{x
c
},8
c
)
(with
c
states)
and A
such that
for
every
x € X,
V\(x}
is the
(only) input letter
x
c
ofC
c
;
moreover,
for
every
i e
(1,...,
c}, x e X,
Since
r |c, it is
obvious that
for
every
if
and
only
if t = 1 and
8(j,
^(tr
+ j, j,
;c))
j +
l(mod
r). By
this observation,
B' is
a (c,
s)-automaton
with
c\cjc.
Suppose
m/c > 0 and let AI,
...,
A
m
, m < m/c € /C,
denote automata
for
which
c
divides
the
least common multiple
of
c\,...,
c
m
,
where
c,
denotes
the
length
of an
appro-
priate cycle
in
A,•,
i —
1,...,
m.
Obviously,
the
counter
C
c
with
c
states
can be
represented
homomorphically
by a
direct
product
of
counters
with
c\,...,c
m
states.
On the
other
hand,
for
every
i =
1,...,
m, the
counter
C
Ci
with
c,
number
of
states
can be
represented
isomorphically
by a
single-factor product
#, of A{.
Therefore, using Proposition 2.53,
an
appropriate
a
0
- v
m
-product
of
B\,...,
B
m
and a
single-factor product
A' of A
(which
may be
an
input-subautomaton
of A if s = r
—
1)
homomorphically
represents
the (c,
s)-automaton
B'
(having
the
semi-Letichevsky criterion).
We
prove that every single-factor product
B"
of
B' can be
represented homomorphically
by an
appropriate
ciQ-v
m
-product
ofBi,...,B
m
and
a
single-factor product
A' of A.
Recall that
B' is an
ao-product
of a
counter
and A.
On
the
other hand,
all
counters have singleton input sets,
and
thus they
are
autonomous
automata.
But
then
an
arbitrary product
of a
counter
and any
other automaton coincides
with
the
ao-product
of the
considered counter
and a
single-factor product
of the
considered
automaton. Therefore,
B" can be
represented homomorphically
by an
a
0
-product
of C
c
and
a
single-factor product
A
of
A.
Hence,
we can see as
before that, indeed, every single-factor
product
B" of B' can be
represented homomorphically
by an
appropriate
<xo-v
m
-product
of
BI
,...,
B
m
and a
single-factor product
A of A.
Applying Lemma
4.8,
an
«
0
-product
T of a
counter with
r'\c
states
and a
mono-
tone automaton
M. can be
represented homomorphically
by an
«o-v>2(.y+i)+i
-product
B",
where
B" is a
single-factor product
of B'. As we
proved before,
B' can be
represented
homomorphically
by an
appropriate
aQ-v
m
-product
ofBi,...,B
m
and a
single-factor prod-
uct
A' of A.
Thus,
by
Proposition
2.63,
F can be
represented
homomorphically
by an
120
Chapter
4.
Without Letichevsky's Criterion
ofo-v
m
+20r+i)+i
-product
of
automata
Bi,...,B
m
and A'
(where
B{
is a
single-factor product
of
A, , i = 1 , . . . , m, and .A' is a
single-factor product
of
.4).
Hence,
F can be
represented
homomorphically
by an
«i-v^
+2(j+1)+1
-product
of AI, . . . , Am and A. In
addition,
also
by
Lemma
4.8,
if s — r — 1,
then
f can be
represented homomorphically
by an
ao-V2(H-i)+i~
power
of B'
too.
Therefore, applying again Proposition
2.63,
if for
every cycle
of
length
k
in B, the
counter with
k
states,
as
well
as the
counter with
r
states,
can be
represented
homomorphically
by a
single-factor ao-product
of an
automaton
in K,
(and
s = r — 1),
then
T can be
represented homomorphically
by an
ao-v
m+2
(
S
+i)+i
-product
of m
factors
in
1C,
and
A. But
then
we are
ready because
m < mjc and F
homomorphically represents
B.
Suppose that
B = (B, X&,
SB)
is
without
any
Letichevsky criteria
and
that
it can be
represented homomorphically
by a
product
of
factors
in
/C.
By
Propositions
4. 1 and
2.54,
we
can
restrict
our
investigations
to the
case when
B is
connected.
If B is
strongly connected,
then
it
forms
a
cycle
of
length
| B \ and
then
our
statement obviously holds. Otherwise,
it has
a
state
bo e B
which generates
all
states and, simultaneously,
<$/?(£,
p) ^ p
holds
for
every
p
€ Xg.
Then
B can be
embedded isomorphically into
the
automaton
B' = (B,
XgUfe],
8'),
where
for
every
b e B,
Let m
denote
the
least common multiple
of all
positive integers which
are
lengths
of
cycles
in
the
automaton
B.
Then,
by the
construction
ofB',m
also
is the
least common multiple
of all
positive integers which
are
lengths
of
cycles
in the
automaton
B'. By
Lemma
4.9,
B' can be
represented homomorphically
by an
or
0
-product
of a
counter with
m
states
and a
monotone
automaton. Because
B can be
represented homomorphically
by a
product
of
factors
in
1C,
it
is
easy
to see
that
the
counter
of m
states also
has
this property.
On the
other hand,
by
Lemma
4.7,
every monotone automaton
can be
represented homomorphically
by a
product
of
factors
in
1C.
Thus
we
have that
the
automaton
B' can be
represented homomorphically
by a
product
of
factors
in
1C.
Observe that
B'
satisfies
the
semi-Letichevsky criterion
(by
Se(bo,
z) = b
0
and
SB^Q,
x'q)
^ b
0
, x' e X
B
, q e
(X&
U
{z})*).
Thus
we can
apply again
Lemma
4.9,
Lemma
4.8,
and
Proposition
2.63.
The
proof
is
complete.
We
have
the
following conjecture.
Conjecture
4.11.
Given
a finite
class
1C
of
automata,
let
CK
denote
the
least common
multiple
of
all
positive
integers
which
are
lengths
of
cycles
of
automata
in
1C.
Moreover,
let
mjc
be the
minimal number
of
cycles
of
automata
in
1C
such that
every
prime power divisor
ofcjc
divides
at
least
one
of
these lengths
of
cycles.
For
every
nonnegative
integer
s,
there
exist
an
integer
r > s, a finite set
1C
of
automata,
an (r,
s)-weighted automaton
A e
1C
(having
the
semi-Letichevsky
criterion),
and an
automaton
B
such that
B can be
represented
by
a
general product
of
factors
from
1C
but B
cannot
be
represented
homomorphically
by
an
ai-Vj-product
of
factors
in K ifi < 1 and j < mjc +
2(,s
+ 1).
Problem
4.12.
Prove
or
disprove
Conjecture
4.11.
The
next observation gives
a
partial solution
of
Conjecture
4.11.