D?m?si P., Nehaniv C.L. Algebraic Theory of Automata Networks. An Introduction
Подождите немного. Документ загружается.
4.3.
Networks
of
Automata
Without
Any
Letichevsky
Criteria
131
Suppose\pi\
=
\p2\
>
min(|px1u|,
|px
2
u
'
)-Ifi
?//
isa(proper)subwordofi',then|M|
<
\u'\
should
hold.
In
other
words,
there
exists
a
nonempty
q e X*
with 8(a, P2q)
=
8(a,
p\).
By
Proposition
4.21,
8(a, p^q)
=
8(a,
p\) =
8(a,
p2)
would imply that 8(a,
p\) is a
state
of a
strongly connected subautomaton
of A. But
then 8(a,
px\r)
also should have
this property, contrary
of our
assumptions. Hence,
we
obtain 8(a,
p\) ^
8(a, p2).
Now
we
study when
v" = vz for
some nonempty
z e X*.
Then
\u\ >
\u'\.
We may
suppose
\P\\
=
\P2\
>
min(|/>jciM|,
Ip^w'l) again.
But
then there exists
a
nonempty
q e X*
having
8(a,
p\q)
=
8(a, p-i). Hence, similar
to
before,
we
also
receive
8(a,
p\) ^
8(a, p-i)
as a
consequence
of
Proposition 4.21.
Thus,
we may
assume
for the
considered words
r, r'
that
for
every
z, z\,
Z2,z',
z\, z'
2
with
r =
zziZ2,
r' =
z'z'iZ
2
we
obtain
z\ = z\
whenever 8(a,
px\uz)
=
8(a, px2u'z') with
max(|w|,
|M'|)
> 0 and
\z\\
=
\z\\.
In
other words,
if p' is a
subword
of
px\r
or
px2r'
and
there
are x, x' X
having 8(a, p'x) 8(a,
p'x'),
then
p' = p
should hold.
Of
course,
we
also have this property ifthere
are no
prefixes
u
of
r or u'
of
r'with
(a,
px\u)
=
8(a, px2u').
Therefore,
we can
define
(p
: A x X -> A and
<p'
: A x X -> A hi the
following manner.
Let
x', y' € X be an
arbitrary
fixed
input
letter;
moreover,
for
every pair
b e A, y e X, let
Then, similar
to the
proof
of
Lemma 4.27, because
of
Proposition 4.16, 8(a,
p'} $
[8(a,
p"),8(a,
px\z),8(a,
px2z')
\ z, z' e X*, z is a
prefix
of
r,z'
is a
prefix
of r'}
holds
for
every pair
of
distinct
prefixes
p', p"
of
p. On the
other hand,
by our
assumptions,
for all
prefixes
z of r and z' of r'
with
|z| =
\z'\,
it
holds that 8(a,
px\z)
8(a, px2z'}. Therefore,
8(a,
pxiz
1
)
8(a,
px
2
z').
But
then (8(a,
px1z),
5(a,
pxiz))
(&(a,
px\z), 8(a, px
2
z')}
is
valid
for
every
prefix
z of r and z' of r'.
Therefore,
by a' = a, the
single-factor products
B =
A(X,
(p)
and C =
A(X,
')
satisfy
the
conditions
of our
Lemma 4.30.
4.3
Networks
of
Automata
Without
Any
Letichevsky
Criteria
In
this section
we
show that some very restricted types
of
networking
(in
terms
of the
number
of
incoming links
and
feedback) already
suffice
for
realizing
the
computational capacity
obtainable
by
unrestricted networking
of
automata that
satisfy
neither
the
Letichevsky
nor
the
semi-Letichevsky criterion.
In
particular, automata networks whose components have
no
more than
one
incoming link
and
receive
no
feedback
at all
(even about their
own
states)
are all
that will
be
required. Thus,
if
components
are too
simple (without
any
Letichevsky
criteria), then
no
amount
of
cleverness
or
complexity
in
networking
can
achieve more
computationally than this simple restricted type
of
networking.
Let A = (A, X, 5) be an
arbitrary automaton without
any
Letichevsky
criteria.
Con-
sider
a
pair
a A, p e X* and
suppose
p =
x\.....x
m
with
x\,.. .,x
m
e X. Put
132
Chapter
4.
Without
Letichevsky's
Criterion
po
= A and pk = x\ • •
-Xk,
1 < k < m. By
Proposition 4.16,
for
every
0 < k < t <
m,
8(a,
pk) =
8(a,
pt)
implies 8(a, ptf}
=
8(a,pty),x,y
€ X.
Therefore,
we can
define
the
automaton Aa,
p
=
(A
0tp
,
X,
8
a
,
p
) such that A
fl;p
= {a} U
[8(a,
x\ • •
•*,)
\
i =
1,...,
m} U
{8(a,
x\ •
'-x
m
q)
\ q e
X*}; moreover,
for any x e X,
&
a<p
(a,
x) =
8(a,
x\),
8
a,p
(a,
x\ • • •
x
f
-ix)
=
8(a,x\---
*,•),
i =
2,...
,m, and
8
a
,
p
(a,
xi---
x
m
q)
=
8(a,xi---
x
m
q). Given
an
automaton
A = (A, X, 8)
without
any
Letichevsky criteria,
let
HA
denote again
the
minimal nonnegative integer such that
8 (a, p)
generates
an
autonomous
state-subautomaton
for
every
a e A, p e X*. We
shall
use the
following.
Lemma
4.31.
Let A = (A, X, 5) be an
arbitrary
automaton without
any
Letichevsky
criteria.
For
every
pair
a € A, p e X*
with
\p\ >
n^.,
we
have that Aa,
p
is an
autonomous
automaton
which
can be
represented
by a
single-factor
product
of
A.
Proof.
By
Proposition 4.16,
for
every
a €. A, p\, pi e X*,
x\,X2
€ X,
8(a,
p\x\p2)
=
8(a,
p\}
implies 8(a,
p\x\)
=
8(a,
p\X2).
Hence,
for
every pair
yi, yz e X, we
obtain
8(a,q\yi)
=
8(a,q2y2) whenever 8(a,
q\) =
8(a,q2) such that
q\ and qi are
distinct
prefixes
of the
same word. Then,
for
every pair
a e A, p e X*, we can
define
the
single-
factor
product
B —
A(X,
(p)
such that
for
every pair
b € A, x € X,
By the
construction
of
13
and
Proposition 4.17,
the
state
8 (a, p) of the
automaton
B
generates
an
autonomous state-subautomaton. Clearly, then
the
state
a of the
automaton
B
also gen-
erates
an
autonomous state-subautomaton
B'. It is
easy
to
prove that
the
state-subautomaton
B'
of B
coincides with
the
automaton Aa,
p
.
n
Proposition
4.32.
Let B = A\ x • • • x
A
n
(X,
tp\,...,
<p
n
)
be a
product
of
automata
such
that
each
of
its
factors
is
without
any
Letichevsky
criteria and, simultaneously,
the
product
B is an
autonomous automaton.
Then
every
connected state-subautomaton
ofB
coincides
with
a
(connected)
state-subautomaton
of
a
diagonal
product
of
autonomous
automata such
that
each
of
its
factors
is a
single
factor
product
of
one
of
the
automata
At, t =
1,...,
n.
29
Proof.
Consider
the
product
B = A\ x • • • x
A
n
(X,
<p\,..., <p
n
)
of the
automata
A
t
=
(A
t
,
X
t
,8
t
),t
=
1,...,
n,
such that
all of
them
are
without
any
Letichevsky criteria and,
simultaneously,
B is an
autonomous automaton.
Put m =
maxCn^,,..., w^J.
If m = 0,
then
all of the
factors
of B are
(connected) autonomous automata,
and
then
our
statement
trivially holds. Thus
we may
assume
m > 0.
Let
there
be
given
a
positive integer
t e
{l,...,n},
a
state
a € A
t
, and a
nonempty
word
p = z\ • • • z
m
,
z\,...
z
m
£
X
t
.lf
there exists
a
state
a'
with double occurrences
in
the
sequence
a,
8
t
(a,
z\), ...,8
t
(a,zi---
z
m
), then,
by
Proposition 4.16,
a'
generates
an
autonomous state-subautomaton
of A-
Put,
in
order,
A
t
,
a
,
p
=
(A
t
)
a
,
P
,
A,,
a<p
=
(A,)«,
P
,
8
t
,
a>p
—
(8
t
)
a
,
p
.
Therefore
A
t>a
,
p
=
(A
t
,
a
,
p
,
X
t
,
8
t
<a<p
)
is
defined
in the
following
manner:
A
t<a>p
=
{a}U{8(a,
z\ • •
-z,)
| i = 1,
29
Recall
that
a
diagonal
product
of
automata
with
a
single
factor
coincides
with
a
^-product
of
these
single
factors. (See
Proposition
2.57.)
4.3. Networks
of
Automata Without
Any
Letichevsky Criteria
133
...,
m] U
{S(a,
zi • • •
z
m
q)
\ q e
X*},
and,
moreover,
for any x e X
t
,
8
t
,
aip
(a,
x) =
8
t
(a, zi), 8
t
,
a<p
(a,
zi • • •
z,-i*)
=
8
t
(a,
z\--z«),
i = \ m, and
8
t
,a,
P
(a,
zi • • •
z
m
q)
=
8
t
(a,
zi • • •
Z
m
q),
q € X*.
Then S
t
(a,
qx) =
8
t
(a,
qy) for
every
t =
1,...,
n, a € A,, q e
X,*,
Itfl
> m, x, y e X,.
Thus,
for
every
r e
{1,...,
n}, a e A
t
, p e
X,*,
|p| = m,
A,a,
P
is
an
autonomous automaton; moreover,
for
every
q e X*,
8
t
,
a
,
P
(a,
pq) =
8
t
(a,
pq).
Simultaneously, A
t
,
a
,p preserves
the
property that
it is
without
any
Letichevsky
criteria.
Let B' =
(B',
X, ') be an
arbitrary connected state-subautomaton
of the
product
B
and
let bo =
(&
0)
i,
• • •, ) e B',
bo
tt
€ A
t
, t =
1,...,
n,
denote
a
state
for
which
B' is
connected.
B is
autonomous,
and
thus
B'
should
be
also autonomous.
Let p e X*
with
\p\
= m be
given
and for any t €
{1,...,
}, put p
t
=
<p
t
(bo,i,
...,b
0
,
n
,
p).
Now
we
shall show that
the
diagonal product
M. =
(B
f
,
X,
&M)
=
A\
<
b
0
^
pl
A
•
• •
&A
n
,bo,
n
,p
n
homomorphically represents
B'. Of
course,
for
every
r e X*, |r| < m,
St.bo.np.&o,!,
r) =
8
t
(b
0tt
,
(p
t
(b
Q
,i,
...,
fc
0
,n,
r')),
where
<p
t
(b
0t
i,...,
bo,
n
,
r') is a
prefix
of
p
t
of
length
|r|.
Thus,
for any r 6 X*, |r| < m,
<5x((fc
0
,i,
• • • •
*«>,«)•
r
) =
5/
((^o,i,
• •.,
Z?o,n),
^")-
Then
we
also have that
5x((
• • •,
£o,n),
) =
<$'((fco,i,
• • •
>
&o,»)>
P) is a
state
both
of
Aland
H'. But
then,
for
every
t e
{1,...,
n}, the
fth
component
of
^((^o.i.
• • •,
^o,«),
p)
generates
the
same autonomous state-subautomaton
in
A
t
,b
ol
,
Pt
and A
t
.
Hence,
by the
structure
of M and B', for
every
p, q € X*
with
\p\ = m, we can
also
get
8^(b0,1,
•••,
bo,
n
),
pr) =
8'((bQ
t
i,...,
b0 )
pr).
This completes
the
proof.
By
Propositions 4.32
and
4.22,
we can
derive
the
next statement.
Corollary 4.33.
Let B = A\ x • • • x
A
n
(X,
<p\,...,
<p
n
)
be a
product
of
automata
such that
each
of its
factors
is
without
any
Letichevsky
criteria and,
simultaneously,
the
product
B
is
an
autonomous automaton.
Then
B can be
represented
homomorphically
by a
diagonal
product
of
autonomous
automata such that each
of
its
factors
is a
single-factor
product
of
one
of
the
automata
A
t
,t
=
I,...
,n.
Lemma 4.34.
If
A = (A, X, 8) = A\ x • • • x
A
n
(X,
(p\,...,
<p
n
)
is a
product
of
automata
without
any
Letichevsky
criteria,
then
for
every
a G
Aandp
€ X*, \p\ = n^, the
automaton
Aa,
p
is
autonomous
and it can be
represented
homomorphically
by a
product
of
the
same
factors
Ai,
...,A
n
.
Proof.
It is
possible
that
for
some
distinct
prefixes
p' and p" of the
word
p
there
exists
at €
{!,...,«}
such that
the fth
components
of 5 (a, p') and 8 (a, p")
coincide. Assume
that
we
have this situation
for a
pair
of
appropriate distinct subwords
p', p" of p and put
(flj,...,fl;_
1
,fl;.«;+P---X)
=
*(fl,/o.
K
<_iX,<«,...,<)
=
<*(«>/>").
But
then,
by
Proposition
4.16,
this state component
a'
t
of A
t
generates
an
autonomous
state-subautomaton
in A
t
.
Thus
we
obtain
the
same product
A if we
assume that
the
val-
ues
of
(p
t
(a{,...,
a,_
l5
a'
t
,
a'
t+l
,
...,a'
n
,x)
md(p
t
(a'{,...,
a'
t
'_
lt
a'
t
,
a"
+1
,...,
a£, x) are un-
ambiguously defined
by the
state
a'
t
and
thus,
for
every
x', x" e X,
<p
t
(a(,...,
a^_
p
a'
t
,
a'
t+l
,
...,a'
n
,x')
=
(p
t
(a'{,...
,a"_
v
a'
t
,a"
+l
,...
,a^,jc").
On the
other hand,
it is
clear that
"A 5!
HA-
Thus, because
of |p| = n^, the
fth
component
of the
state
vector
5 (a, p)
gener-
ates
an
autonomous state-subautomaton
of A
t
.
Thus
we get the
same product automaton
A
if
we
suppose that
for
every state (aj,...,
a'
n
}
—
8(a,
pq),
q € X*, and x e X, the
value
of
<p
t
(a{,...,
a'
n
,
jc) is
unambiguously defined
by the
state component
a'
r
134
Chapter
4.
Without
Letichevsky's
Criterion
Having these assumptions,
we can
construct
a
product
A =
(A,X,8)
=
AI x • • • x
A
n
(X,
(p{,...,
(p'
n
)
of the
automata
A
t
=
(A
t
,
X
t
,8
t
)
in the
following way.
For
every
(a\,...,
a
n
) € A, x e X, t €
{I,...,
n],
But
then
the
state
a of
this product generates
the
automaton A
a
,
p
as a
state-subauto-
maton. Finally,
by
Lemma 4.31, A
a
,
P
should
be
autonomous,
as we
have stated.
D
Consider
an
automaton
A =
(A,X,8)
without
any
Letichevsky criteria
and let
0o
e A be fixed. For an
arbitrary pair
k, t of
positive integers,
put
PA,OO(X,
k,l)
= *
if
8(a.Q,
px\)
=
8(ao, px2) holds
for
every
p e X*, \p\ = k
—
1 and
x\,X2
€ X.
Moreover,
put
PA,OO(X,
k,
V)
= * if for
every
a =
8(ao,
p), p € X*, \p\ = k — 1,
property
(1) of
Lemma 4.24 holds, and, simultaneously,
t>tk,
where
-4
denotes
the
length
of the
words
q, q' € X*, \q\ —
\q'\ having maximal length such that
8(a,q)
=
8(a,q'); furthermore,
8(a,
s)
8(a,
s') for all
nonempty prefixes
s of q and s' of q'
with
\s\ =
\s'\. Otherwise
put
AA,«O(*>
*• *) =
*-
3
°
to
addition,
put
PA,OV(XI
• • • x
n
) =
pA,a
0
(x\,
1,
k)p
A<ao
(x
2
,
2,k-
1) • • •
PA,ao(xk,
k, 1) for
every
x\,...,
jc* € X.
Finally,
put
PA,a0(
) = A by
definition.
We
shall
use the
following
two
observations.
Proposition
4.35.
If
PA,
OO
(XI
• •
•*„)
= y\ - • •
y
n
-i
* (yi e
{*,-,*},/
=
1,....
n -
l)/<?r
-yome^i,...,
x
n
e X,
thenp
A<ao
(x\
•
-x
n
x)
= y{ • • •
y^**,
y,' e
{y,-,
*}, i =
1,...,
n-l
for
every
x e X.
Proposition
4.36.
Let A = (A, X, 8) be a
connected automaton without
any
Letichevsky
criteria
and let
OQ
be a
state
for
which
A is
connected.
For
every
p,q € X*,
PA,a0(P)
=
PA,a
0
(q)
implies 8(a
0
,
p) =
8(a
0
,
q).
Given
an
automaton
A = (A, X, 8)
without
any
Letichevsky criteria, assume that
A
is
connected
for
OQ
e A.
Define
the
automaton
Z>
=
(D,X,
8')
with
D = (PA
,a0(p}
I P €
X*,\P\<\A\],
Consider
a
positive integer
t e
{!,...,«},
a
state
a € X
t
, and a
nonempty word
p =
Zl
•
-'Zn
A
,Zl,
.
..Zn
A
& X
t
.
Let
pi,...,
p
u
be a
complete list
of all
words
of
length
of
HA
in X*.
Lemma 4.37.
The
diagonal product
D
A
a0ta1
A • • •
AAio,p
u
homomorphically
repre-
sents
A.
Proof.
By
Proposition 4.36,
for
every
p, q e X*,
PA,a0(P)
=
PA,a
0
(q)
implies 8'(ao,
p) =
8'(ao,
q).
Thus,
we can
unambiguously
define
the
mapping
i/r : D x
A
aQtpl
x • • • x
A
aQtpu
->
30
Thus
wealsoput/o^oQ^,
k, (.) = x if
there
area
=
<5(ao,
p), p € X*, \p\ — k
—
l,
such
that
we
have
property
(1) of
Lemma
4.24.
4.3. Networks
of
Automata Without
Any
Letichevsky
Criteria
1 35
A
such that
(1)
\fr(X,OQ,
...,oo)=«o;
(2)
for any p e X*
with
\p\ < n
A
,
1r((8'(
, p),
5
flo
,
pl
(ao,
p),...,
S
(a0,
p)))
=
<Wp,
(a0,
p),
where
p, is the first
word
in the
list
p\,...,p
u
such that
for the
prefix
of/?'
of p, of
length \p\,
0.4,00
(X) =
PA^pY
(3)
for any
pair
p,q e X*
with
\p\ = n
A
,
&((8'(X,
pq),
8^(00,
pq)...,
5oo,p
B
(«o,
/>#)))
=
5ao,ft(ao>
M)>
where
/?, is the first
word
in the
list
p\,...,
/?„
such
that
pA,a<>(pi)
=
PA,OO(P)-
Recall that
for all
words
r e X* of
length
n
A
,
8(ao,r) generates
an
autonomous
subautomaton
in A. By
this observation, using Proposition 4.36,
we
have that
^ is a
state-
homomorphism
of the
diagonal product
D
A
ao
,
pl
A • • •
A
ao
,
pu
onto
A.
By
Lemma 4.34
and
Proposition
4.32,
each
of the
automata
Aio.p,i
=
!,.••,«,
can
be
represented homomorphically
by a
diagonal product
of a
single-factor product
of the
factors
of A.
For
every
i =
1,...,
n
A
, x e X,
define
£?
I>JC
=
(fi,,
X,
<$,,*)
in the
following way.
If
PA,OO(X,
i,£)
= * for
every positive integer
t,
then
let 5, =
{0},
S,-
)JC
(0,
z) = 0,
z
e X.
If/o^
>ao
(jc,
i, ^) =
Jc
for
every
A:
e X and
positive integer
£,
then
let
J5,
=
{0,1, ...,/
—
1,
*, x}
with
Otherwise, denote
m, the
maximal positive integer
for
which
PA,a0
(x, i,
m,-)
= x, x e
X
and
define
B
(
-
=
{0,1,...,
i - 1, *} U
{(x,
t) \t =
1,...,
m,},
Lemma 4.38.
Let
x\,..,,
x
s
be an
arrangement
of
the
elements
of
the
input
set X. The
diagonal
product
B\
tXl
A • • •
B\,
XS
A • • •
AB
nA<Xl
A • • •
AB
nAtXs
homomorphically
represents
the
above
defined
automaton
D.
Proof.
Let D' =
(D',
X, 8")
denote
the
state-subautomaton
of
this diagonal product
BI,
XI
A
•
•
-Bi
>Xs
A • • •
Bn
A<X
i
A • • •
B
nA<Xs
generated
by the
state
(0,...,
0). It is
easy
to
prove that
^ :
B[
xl
x--.xBl
x
A
-»
Bwith^((5
Ul
(0,
p),...,S
Ui
(0,
p),..., ^.(O, p),..., S
n
^
s
(0,
/>)))
=
<5'(A,,
/?) is a
state homomorphism
of £>'
onto
T>.
Lemma 4.39. Given
an
integer
i > 0, an
automaton
A =
(A,X,
5)
without
any
Letichevsky
criteria,
states
OQ,
a € A,
vw/tfa
p,
<?,
<?'
e X*,
|/?|
> i — 1,
\pq\
=
\pq'\
> |A| — 1, let
136
Chapter
4.
Without Letichevsky's Criterion
5(a0,
P) = a and
8(a,
qr) ^
5(o,
q'r')for
every
r, r' 6 X*, \r\ =
\r'\.
Then
B
itX
,
x € X
can be
represented
homomorphically
by a
single factor product
of
A.
Proof.
By our
assumptions,
the
state
a e A of the
automaton
A = (A, X,
«5)
has
prop-
erty
(1) of
Lemma
4.24.
Then
we can
apply Lemma
4.27
provided that
\pu\
> i — 1.
In
more
detail,
we can
define
the
automata
B and C as in
Lemma
4.27.
Obviously, then
for
an
appropriate nonnegative integer
j >
\pu\
and for
every
u' e
X*,\u'\
= j,
there
exists
x e X
such that, whenever
i > 1, for
every
x
f
,
yi,..., y/_i
e X, x' ^ x, the
states
(S
B
(a
0
,
u'), 8
c
(a
0
, u')),
(8
B
(a
0
,
w'yO,
8
c
(a
0
,
u'yi)),...,
(8
B
(a
0
,
u'yi
• • •
y,--i),
8
c
(a
0
,
u'yi
• - •
y/_i)),
(8s(ao,
u'y\
- • •
yi-ix),
8c(a
Q
,
u'y\
• • •
y,_i*))
of the
diagonal product
B&.C
are
distinct. Similarly, whenever
/ = 1, for
every
x' e
X,x'
^ x, the
states
(5
B
(a0,
M'),
8
c
(a
0
, u')),
(5
B
(oo,
u'x), 8
c
(a
0
,
u'x)), (8
B
(a
Q
, u'x'), 8
c
(a
Q
, u'x'))
of the
diag-
onal product
#AC are
distinct.
In
addition, {(5(g(ao,
z),
8c(ao,
z))\z
=
z\xz2,
z\,
Z2
€
X*,
\zi\
= i + j - 1} and
{(5(
B
(a0,z),
5
c
(a0, z))|z=zi*'z
2
,*'
e
X,x'
/
x,z\,Z2
€
X*,
\z\\
= i + j — 1} are
disjoint sets. Clearly, then
the
mapping
ty
with
i{r((8
B
(aQ,
u'),
8c(ao,
M')))
= 0,
if((8
B
(a
0
,
u'v),
8
c
(a
Q
, u'v}}}
= m,v e
X*,\v\
= m, m =
1,...,
i -
1,
if((S
B
(a
0
,u'vxr),Sc(ao,u
f
vxr)'))
=
x,v,r
e
X*,\v\
= i - 1,
if((8
B
(ao,u'vx'r)
t
8c(ao,
u'vx'r)}}
= *, x' e X, x' x, v, r e X*, \v\ = i — 1, is a
state-homomorphism
of
an
appropriate state-subautomaton
of B AC
onto
BI,
X
.
Lemma
4.40.
Given
an
integer
i > 0 an
automaton
A= (A, X, 8)
without
any
Letichevsky
criteria,
Iet8(a,
q) =
5(a,
q')
for
every
a € A, q, q' € X*
having
\q\ =
\q'\
> \A\ -
I
for
which
there
are
ao
e A, p € X*, q", q'"
with
the
properties
\p\ = i
—
l,
\q"\
=
\q'"\
< \A\
—
I
and
8(ao,
p) = a,
5(a,
q") ^
8(a, q'").
Suppose
that \q"\(=
\q'"\)
is
maximal with this
property.
Then
BI
!X
,X
€ X can be
represented
homomorphically
by an
otQ-v\-power
of
A.
Proof.
By our
conditions,
the
automaton
A has
condition
(2) of
Lemma
4.24.
Then
we can
apply Lemma
4.29
assuming that
\pu\>i
— \.
(Then,
by our
assumptions, there exists
a
maximal positive integer
m,
with
PA,OO(
X
>
*>
m
<) =
x
-
Moreover,
m, =
\q"\
=
\q"'\
> 0.)
Clearly, then
the
mapping
$
with ^((5
B
(feo,z),5
c
(c
0
,z)))
=
|z|,z
€
X*,0
< |
z
| <
i,
^((&13(bo,
PZIXZ2~),8
C
(C
0
,
ZiXZ2)))
=
(X,\Z2\
+
l),Zl,Z2
€ X*,
|Zl|
= / - 1,0 <
\Z2\
<
nii,
is((8B(bo,zixz2),8
c
(co,zixz2)V
=
*,zi,Z2
e X*,
\z\\
=
i-l, |z
2
|
>
m,-,
^((8
B
(bQ,zix
f
Z2),8c(c
0l
zix'z2^
=
*,x',x'
e
X*,x
f
£x,zi,Z2£
X*,
\zi\
= i -
l,is
a
state-homomorphism
of an
appropriate state-subautomaton
of B
AC
onto B{
tX
.
For
every class
K, of
automata without
any
Letichevsky criteria,
put M
k
=
[I,...,
nB]
if
there exists
a B €
JC
such that
for
every
A € k, n& > n^.
Otherwise,
let Afc be the set
of
all
positive integers.
Lemma
4.41.
Consider
a
class
/C
of
automata without
any
Letichevsky
criteria.
Suppose
that
for
every
A =
(A',
X', 8') €
/C,
a' € A', yi, y
2
€ X', p', q, q' €
X'*,
fc > 0,
with
k
<
\p'l
\p'yiq\
=
\p'y2q'\
< \A\ - 1,
8'(a',
p'
yi
q)
£
&'(a
1
,
p'y
2
q'},
there
exist
A =
(A,X,8)
€/C,fl
€
A,xi,x
2
€
X,p,r,r'
€ X*
having
\p\
=k,\r\
=
\r'\
=
|o|(= |o'|)
5MC/I
f/raf
8(a, px\z)
/
5(a,
px2z'}for
all
prefixes
z ofr and z'
ofr'
with
\z\ =
\z'\.
Then
for
every
pair
i e
Af/c,
x 6 X,
Bi
tX
can be
represented
homomorphically
by a
single
factor
product
of
A
4.3. Networks
of
Automata Without
Any
Letichevsky Criteria
137
Proof.
By our
assumptions,
we can
apply Lemma 4.30. (Then,
by our
assumptions, there
exists
a
maximal positive integer
m,
such that
PA,a0(X,
i,m
f
)
= x.
Moreover,
m, = \q\ =
\q'\
> 0.)
Clearly, then
the
mapping
V
with
((8
B
(a,z),
8
c
(a,
z)))
=
|z|,z
e X*,
0
< |z| < i,
is((8t3(a,zixz2),8
c
(a,zixz
2
)))
= (x,
|z
2
|
+
l),zi,Z2
e X*,
|zi|
=
i-1,0
<
\Z2\
< mt,
if((8
B
(a,Zixz2),8c(a,Zixz2)))
=
*,Zi,Z2
€ X*,
|zi|
= i - 1,
|Z2|
>
»»,•,
^((SB(a.zi*'z2),Sc(fl,zi*'z2)))
=
*,x'
e
X,x'
^
x,zi,Z2
e X*,
|zi|
= i - 1, is a
state-homomorphism
of a
state-subautomaton
of B
AC
onto
.
Lemma 4.42.
Le?
1C
be a
class
of
automata without
any
Letichevsky criteria
and
assume
that
there exist integers
k, k' > 0
such that
\p\ ^ k
whenever
A = (A, X, 8) e /C, a €
A,
xi,X2
e X, p, r, r' € X*
having
|r| =
|r'|
= fc'
such that 8(a,
px\z)
=£
8(a, px2z')for
all
prefixes
zofr
and z'
ofr' with
\z\ =
\z'\.
Then
all of the
q
i
-products
of
factors
in
1C
preserve this
property.
Proof.
Consider
an
automaton
A = (A, X, 8) e /C. By
Lemma 4.24,
for
every
a € A we
have
one of the
following
two
possibilities:
(1)
There exist
q,q'
e X*, \q\ =
\q'\
> |A| - 1
such that 8(a,
qr)
8(a, q'r')
for
every
r,r'eX*,
|r| =
|r'|.
(2)
S(a,
?) = ( )
for
every?,?'
e X*, \q\ =
\q'\
> \A\ - 1.
By
our
conditions,
we
have
\p\
^kin
both
cases
whenever x\,X2
€ X, p, r, r' e X*
with
|r | =
|r'|
= k'
such that 8(a,
px\z}
i=-
8(a, px2z'}
for all
prefixes
z of r and z' of r'
with
|z| =
|z'|.
By the
above properties
(1) and
(2),
it is
clear
that
all
single-factor products
of
A
preserve this property.
On the
other hand,
it is
also clear that
a
diagonal product
of
automata
has the
conditions
of our
statement
if all of its
factors have
it. By
Proposition
2.57, this completes
the
proof.
Lemma 4.43.
Let
1C
be a
class
of
automata without
any
Letichevsky criteria
and
assume
that
there exist integers
k, t > 0
such
that
for
appropriate
p,r,r'eX*
with
\p\ = k, \r\ =
\r'\
= i we
have that there
are an
automaton
A = (A, X, 5) e /C,
state
a € A,
input
letters
x\,X2
€ X,
such that 8(a,
px\z)
^
8(a, px2z'}
for all
prefixes
z
of
r and z' of
r'
with
\z\ =
\z'\.
Then
for
every
integer
k'
with
k' < k
there
are
p,r,r'
e X*
with
\p\
=
k',\r\
=
\r'\
= t + k
—
k'
such that
an
appropriate
ctQ-v\-power
A = (A, X, 8) of
an
automaton
in
1C
also will have
a
state
a € A
having
the
above
property.
Proof.
Consider
an
automaton
A = (A, X, 5) 6
1C.
By
Lemma 4.24,
for
every
a € A we
have
one of the
following
two
possibilities:
(1)
There
exist?,
q' € X*, \q\ =
\q'\
> |A| - 1
such that 8(a,
qr) ^
8(a, q'r')
for
every
r,r'eX*,
|r| =
|r'|.
(2)
8(a,q)
=
8(a,q')
for
every?,?'
€ X*, \q\ =
\q'\
> |A| - 1.
Suppose that
(1)
holds
for
some
A = (A, X, 8) e
/C,
a e A,
with
a
long enough
q
(and
q')
such that there
are
p,r,r'
e
X*,xi,X2
e X
having
\p\ > k, \r\ =
|r'| =t+k-k',
px\r
is a
prefix
of ?, and
pxjr'
is a
prefix
of q' for
which 8(a,
px\z)
8(a, px2z')
for all
138
Chapter
4.
Without
Letichevsky's
Criterion
prefixes
z of r and z' of r'
with
|z| =
|z'|.
Then
the
automaton
A
with
its
state
a e A
also
has
the
properties
of our
statement.
Otherwise
we
have
to
assume that
(1)
does
not
hold
for any A = (A, X, 8) e /C, a e
A,
q, q' and p, r, r' e X*, x\,
X2
€ X
having
\p\ > k, \r\ =
\r'\
with
the
above properties.
In
this case
we
should have
an
automaton
A = (A, X, 8) e /C, a
state
a G A
such
that
(2)
holds; moreover, there
are p,
r,r'eX*,xi,X2€X
having
\p\ > k, \r\ =
\r'\
= t
for
which
8(a, px\z)
(a,
px2z')
for all
prefixes
z of r and z' of r'
with
|z| =
|z'|.
Then,
similar
to the
proof
of
Lemma 4.29,
we can
construct
a
diagonal product
of two
UQ-VI
-powers
of
A
such that
it has the
conditions
of our
statement.
Consider
yi
y^,,
yf
p|+1
,...,
y'
]pxiz]
€ X
such that,
in
order,
p = yi • • •
y\
p
\,
xi =
y\
p
\+i,
x
2
=
y'
lpl+1
,
z =
y\
p
\+2
• • •
y\
pxit
\,
z' =
y[
p|+2
• • •
y[
px
^.
Moreover, consider
words
p
m
, v
n
, v'
n
e X*,
where,
in
order,
p
m
is a
prefix
of
p of
length
m, 1 < m <
\p\,
r
n
is
a
prefix
of r of
length
n, and
r'
n
is a
prefix
of r' of
length
n, 1 < n <
\r\(=
|r'|).
In
addition,
let x' € X be an
arbitrary
fixed-input
letter.
By
our
assumptions, without
any
contradiction,
for
every nonnegative integer
i < \p\
we can
define
the
functions
tp\ : X -> X,
<PJ;
: A x X -> X,
<p{
: X -> X,
(p'
}
•
: A x X ->
X,
j =2,
...,\p\
—
i,
having
the
following properties:
Let
13
= (B, X, 8
B
) =
A\
pl
~
i+l
(X,
<p
lt
...,
<p\
p
\-
i+
i)
andC
= (C, X, 5
C
) =
A
lpl
i+l
(X,<p{,...,
<p'\
pl
-
i+
i)
with
b =
(8(a,
p\
p
\-d,
5(tf,
p\
p
\-i-i),...,
<5(tf,
pi),
a), c = b.
By
Proposition
4.16,
8(a,
/?')
i
{8(a,
p"), 5(a,
pjciz),
5(a,
px
2
z)
\ z € X*}
holds
for
every pair
of
distinct prefixes
p', p" of p. But
then,
of
course,
for
every
z, z' € X*
with
|z| < k'l <
Ip^i'*!,
we
have
5g(i>,
z) ^
&e(b, z')-
On the
other hand,
by
Lemma
4.28,
we
may
also assume
8(a, px\w)
^
8(a,
px2w
f
)
for all
prefixes
w of r and w/ of r'
with
|u;|
=
lit;').
Therefore,
(5
B
(^,
z),
<5
c
(c,
z))
(5
B
(
,
z'),
<5
c
(c,
z'))
if z and z' are
arbitrary words
with
|z| <
|z'|
<
\pxir\
31
orz =
zi^iZz
andz'
=
z^z^,
Izil
=
Iz'J
=
\p\,x
e X,x ^ x\,
0 < |^| =
|z'|,
where
12
is a
prefix
of r and
22
is
a
prefix
of
r'.
32
Then
we
obtain that
for
every
z, z' € X*
with
|z| <
\z'\
<
|pjcir|
we
have
(<$#(&,
z),
5c(c,z))
^
(S
B
(fc,z'),<$c(c,z'));
moreover
{ (*,
z),«c(c,z))|z
€ X*, |z| <
»},
{
B
31
Then5c(ft^)^5c(*,z').
32
Then3
B
(c,z)^
e
(c,z').
4.3. Networks
of
Automata Without
Any
Letichevsky
Criteria
139
and
are
pairwise disjoint
sets.
Then
we
have
our
statement
for
The
proof
is
complete.
Now
we are
ready
to
prove
the
next theorem.
Theorem 4.44.
Let K be a
class
of
automata
without
any
Letichevsky
criteria.
The
following
statements
are
equivalent:
(1)
Every
general product
of
factors
from
1C
can
also
be
represented
homomorphically
by
a q
l
-product
of
the
factors
from
1C.
(2) For
every
with
there
exist
having
such
that
for all
prefixes
z
of
r and
having
Proof.
First
we
assume that
we
have condition
(2) of our
statement
and let
be a
product
of
automata,
that
each
of
A
t
,t
= I,.
..,n,is
without
any
Letichevsky
criteria).
Next
we
prove that
M
can
be
represented homomorphically
by a
diagonal product
N of
automata such that each
of
its
factors
is a
single-factor product
of an
appropriate factor
of M. By
Proposition 4.22,
we
can
restrict ourselves
to
proving
our
statement
to the
connected state-subautomata
of M.
On
the
other hand,
by
Proposition 2.75,
M and
thus
all of its
connected state-subautomata
of
M
preserve
the
property that they
are
without
any
Letichevsky criteria.
Let
A = (A, X, 8) be a
connected state-subautomaton
of M
without
any
Letichevsky
criteria.
If A is
autonomous, then
we are
done
by
Corollary 4.33. Then
we may
assume
that
A is
nonautonomous
and
thus
n
A
> 0. Let us
denote again
by a
o
a
state
for
which
the
(nonautonomous) automaton
A is
connected; moreover,
let a
o
=
(a
o
,1,..., a
o
,
n
), a
o
,t
A
t
. t = 1 n.
Consider
a
complete
list
P
1
D,, of all
words
of
length
of n in
X*.Bv
Lemma 4.37,
homomorphically represents
A. By
Lemma
4.34
and
Proposition 4.32, each
of the
automata
,
can be
represented
homomorphically
by a
diagonal product
0f a
single-factor product
0f the
factors
0f A. It
remains
to
prove
by (1)
that
D can be
represented homomorphically
by a
q
l
product
of
factors
from
1C.
But it is a
direct consequence
of
Lemmas 4.38
and
4.41.
Now
we
assume that
(2)
does
not
hold. This implies that there
exist
A =
(A',
X', $')
with
such
that
for
every
having
for
every
prefix
z of r and z' of r'
with
|z| =
|z'|,
we
have
\p\
k. By
Lemma
4.42,
we
obtain that every q
l
-product
of
these automata
in K
preserves this property. But,
by
Lemma 4.43
it can be
shown that
the (
o
-V
1
-product
does
not
preserve this property. Thus
we
obtain this
fact
for the
general product, too. This ends
the
proof.
Next
we
prove
the
following proposition.
1
40
Chapter
4.
Without
Letichevsky's
Criterion
Proposition
4.45.
There
exists
an a
o
—
v
1
-power
M of an
automaton
A
without
any
Letichevsky
criteria such that
M
cannot
be
represented
homomorphically
by any q
l
-product
of
A.
Proof.
Let A = (A, X, 8)
with
A = {
o
,
a
1
,a
2
, a
3
,a
4
}, {x
1
, x
2
],
Moreover,
let B = (B, X, $')
with
A =
{b
0
,
b\, b
2
, b
3
, b
4
,
b
5
},
[x
1
,x
2
],
Define
the
functions
in the
following way:
In
addition, give
:
{(a
1
,a
o
)
,
(a
2,
a
1
), (a
3,
a
1
), (a
4,
a
2
), (a
4
, a
3
), (a
4
, a
4
)}
B as
follows:
Obviously,
is a
state-isomorphism
of a
state-subautomaton
of the
a
0
-VI
-power
Ax A
onto
B. On the
other hand,
bv an
elementarv comoutation.
we
obtain
for
every diagonal product
D = (D, Y, S
D
) of
arbitrary single-
factor
products
of A,
state
d D, and
input letters
y
1
, y
2
Y.
Therefore,
B
cannot
be
rep-
resented homomorphically
by any
q
l
-power
of A.
Thus
the
•power
A x A
also cannot
be
represented homomorphically
by any
q
l
-power
of A.
We
will also
use the
next statement.
Lemma 4.46.
If
A is an
automaton without
any
Letichevsky
criteria, then
every
single-factor
product
of
A can be
represented
homomorphically
by an
a
o
-v
1
-power
of
A.
Proof.
First
we
suppose that
A is
connected.
Let us
consider
a
single-factor product
A
of
the
automaton
A = (A, X, 8) and
construct
the
-power
M =
A
nA
(X