D?m?si P., Nehaniv C.L. Algebraic Theory of Automata Networks. An Introduction
Подождите немного. Документ загружается.
2.4. Automata Networks
and
Products
of
Automata
61
•PRODUCT
-PRODUCT
V]-PRODUCT
V
2
-PRODUCT
V
3
-PRODUCT
There
is a
close relationship between
the
ao-product
of
automata
and the
wreath
product
of
transformation semigroups.
If we
have
an
ao-product
as
above, then con-
sider
the
wreath product
of the
transformation semigroups
of the At,
(A
n
, S(A
n
))
* • • • i
(A\, S(.Ai)); viewing this
as an
automaton,
we see
that
the
ao-product embeds into
it
under
(a\,...,
a
n
)
M»
(a
n
,...,
a\} and x h>
(/„,...,
f\),
where
f\ e
S(A\)
is
defined
by
/i =
0$i)*i
using
xi =
(p\(x),
and, similarly
for i
>!,/}:
A,_i
x • • • x AI ->
S(Ai)
is
defined
by
/)(a
(
_i,...
,a\)
= (
)
Xi
, using
z
=
<pi(a\,...,
a,_i,
x).
Conversely, consider
the
wreath product
(A
n
x • • • x AI, W) of
transformation semigroups
Ai —
(A,, 5,-)
as an
automaton
with input transformations
(/„,...,
f\) e W;
then
the
ao-product
of the At
con-
sidered
as
automata with feedback
functions
,
(a\,...,
a,\-\
n
,...,
/i))
= //
(a,-_i,...,
fli) is
isomorphic
to the
wreath product.
Proposition
2.51. Given
a
nonnegative
integer
i, let
be an
ctQ-product
of
cti-products
Then
M. is
isomorphic
to an a,
-product
of
62
Chapter
2.
Directed
Graphs,
Automata,
and
Automata Networks
Let
T>
— (V, E) be a
digraph with
V =
[I,...,
n]
and,
for
every
v e V, let A
v
=
(A
v
,
X
v
, ) be an
automaton.
A
general product
A = AI x • • • x
A
n
(X,
pi,...,
n
)) is
a
T)-product
if
each feedback function
<
(v V) is
really independent
of its uth (u V)
state variable whenever
(u, v) E. If A is a
nonempty class
of
digraphs
and
T>
A,
then
it
is
also said that
A is a
^-product.
(In
what follows,
by a
class
A of
digraphs
we
always
mean that
A is a
nonempty class.) Thus,
if A is the
class
of all
digraphs having neither
cycles
nor
loop edges, then
the
-product
is
just
the
loop-free
product, which
is
further
equivalent
to the
cascade product
or, by
another name,
the
ao-product.
If A
consists
of the
cycles, then
we
obtain
the
concept
of
loop
product.
(Of
course,
if all
factors
are the
same,
then
we
speak about appropriate types
of
powers.)
If A is the
class
of all
digraphs having
no
edges, then
the
-product
is
called
a
parallel product
or a
quasi-direct
product,
or, in
short,
a q
-product.
In
other words,
we
define
the
underlying
graph
T>
= (V, E) (V =
{I,...
,n},
E
V
x V) of A
such that
(i, j) € E if and
only
if the
feedback
function
J
really depends
on
its
/th-state variable. Thus,
an
underlying graph
is a
digraph which
may
contain loop edges.
We
will
use the
following
two
facts
throughout this monograph.
2.4.
Automata Networks
and
Products
of
Automata
63
Proposition
2.52.
Given
a
digraph
D,
suppose
that
an
automaton
A can be
represented
homomorphically
(isomorphically)
by a
D-product
of
automata
A
t
,t
=
!,...,«.
Then
there
exists
a
D-product
of
automata
A
t
, t =
1,...,
n,
having
a
state-subautomaton
which
can
be
mapped
state-homomorphically
(state-isomorphically)
onto
A.
Proof.
Let =
(V''!'
),
V^:
B
A,ijf2
: XB X be a
homomorphism
(an
isomorphism)
of a
subautomaton
B = (B, X SB) of the X
-product
= A\ x • • • x
A
n
(X',
<p[,...,
(p'
n
)
onto
A = (A, X, ). For
every
x X, let be an
arbitrary
fixed
letter
in
XB
with
"*) = x.
Define
the Z
-product
M = A\ x • • • x
A
n
(X,
,...,
)
such
that
for
every
t
{1,...,«},
(a\,... ,a
n
)
AI x • • • x A
n
andX
e X,
(p(a\,
...,a
n
,x)
=
<
(ai,...,
a
n
, ). It is
clear that
M is
also
a
P-product.
It is
also obvious that
1 is a
state-homomorphism
(a
state isomorphism)
of the
state-subautomaton
of M
with
the
state
set
B
onto
A. The
proof
is
complete.
Proposition
2.53.
Given
a
digraph
D,
suppose
that
an
automaton
A can be
represented
homomorphically
(isomorphically)
by a
D-product
of
automata
A
t
, t =
1,...,
n.
Consider
automata
B
t
, t =
1,...,
n,
such
that
for
every
t =
1,...,
n, B
t
homomorphically
(isomor-
phically)
represents
A
t
.
Then
A can
also
be
represented
homomorphically
(isomorphically)
by
a
D-product
ofB
t
,
t =
!,...,«.
Proof.
For
every
t =
I,...
,n,
consider
a
homomorphism (isomorphism)
= ( ,!,
,2),
1
,1 :
t
-+ A
t
,2 '• • X
t
of a
subautomaton
of B
t
=
(B
t
, X'
t
,
)
onto
A
t
=
(A
t
,
X
t
, ).
Moreover,
let AI x • • • x A
n
( \, •. •,
n
, X) be a
D-product
of
automata
AI,
...,
A
n
which homomorphically (isomorphically) represents
A =
(A,X,8).
Then,
by
Proposition 2.52,
we can
also assume that
it has a
state-subautomaton
M
which
can
be
mapped homomorphically (isomorphically) onto
A by a
state-homomorphism (state-
isomorphism)
: M A.
Define
the
£>-product
B\ x • • • x
B
n
((
,...,
'
n
, X) in the
following
manner.
For
every
t =
,...,«,
consider
a fixed
element
d
t
of B'
t
and
define
the
mapping
:
B
t
A
t
such that
Moreover,
let p
t
denote
an
ordering
on
X'
t
.
In
addition,
define
(bi,...
,b
n
,x)
= x'
such
that
x' X'
t
is the
minimal input sign (with respect
to p
t
)
having
t
,2(x')
= x"
with
(
(ri(bi),...,T
n
(b
n
),x)
=x".
First
we
prove that
B\ x • • • x
B
n
((
{,...,
(
n
, X) is a
D-product. Consider
t
{1,...,«}
and let { ,
t),...,
(t
m
,
t)} = E n
{1,...,«}
x
{t},
where
E
denotes
the set
of
edges
of D.
Then
for
every
t
{1,...,
n},
(b\,...,
b
n
) 6 B\ x • • • x B
n
, x e X,
<Pt(
(bi),...,
T
n
(b
n
),
x) = x" is
unambiguously determined
by the
components
l
,...,
m
,x.
Therefore, these components unambiguously determine
the set [z € X'
t
\
1/^,2(z)
=
x"}. Then
'
t
(b\,...
,b
n
,x)
= x' is
also unambiguously determined
(by the
components
b
tl
,
...,b
tm
,
x)
because
it is the
minimal element
of [z X'
t
\
1/^,2(2)
= x'}
(with respect
to
p
t
). Therefore, indeed,
B\ x • • • x
((p{,...,
r
n
, X) is a
D-product.
Now
we
prove that this D-product homomorphically (isomorphically) represents
A.
Let M' =
{(hi,...,
b
n
) B{ x ... x B'
n
\
(^i,i(&i),
• - •, O) M};
moreover,
64
Chapter
2.
Directed
Graphs,
Automata,
and
Automata Networks
let
defined
bv
For
every
and
ive
have
such
that.
is the
minimal input sign (with respect
to p
t
)
having
with
This means that
Therefore,
is a
state-homomorphism (state-isomorphism)
of a
state-subautomaton
of the
D-product
onto
A. Ihe
proot
is
complete.
We
have
the
following direct consequence
of the
above statement.
Proposition
2.54.
Consider
a
class
K. of
automata
and two
classes
A, A of
digraphs
having
the
property
that
every
-product
of
.-products
of
automata from
1C
is
also
a
A-product
of
automata from
K.
Suppose
that
an
automaton
A can be
represented
homo-
morphically
(isomorphically)
by a
A-product
of
automata
Ai,... ,A
n
,
and
assume that
for
every
t =
1,...,
n, A
t
can be
represented
homomorphically
(isomorphically)
by a A-
product
ofautomata
from
K.
Then
A can be
represented
homomorphically
(isomorphically)
by
a
A-product
of
automata
from
K..
Here
and
throughout this monograph,
if we are
dealing with
a
class
K.
of
automata,
we
always assume that
k is
nonvoid.
A
class
of
automata
is
called complete with
respect
to
homomorphic
(isomorphic)
simulations
under
the
given
type
0
of
products
if
every
automaton
can be
simulated homomorphically (isomorphically)
by a
product
of
automata
inK.
K
is
called
finite
if it has a finite
number
of
elements. Furthermore,
it is
said that
/C
is
minimal
if for
every
A K, k \ A is not a
complete
class
of
automata with respect
to
homomorphic (isomorphic) simulations under
the
0-product.
The
complete
(finite
complete, minimal complete) classes
of
automata with respect
to
homomorphic (isomorphic) simulations
by
nonempty
words
are
analogously defined.
The
next statement
is
clear.
Proposition
2.55.
Given
a
digraph
D, let M = A\ x • • • x
A
n
(X,
i,...,
<
) be a -
product
of
automata
A\,...,
A
n
such that
M.
homomorphically
(isomorphically)
simulates
an
automaton
A by
some
mappings
: B A, 12 : Y • X*.
Then
there
exists
a
D-product
M' = AI x • • • x
A
n
(X',
(,...,
<p'
n
)
with
the
same factors such that
Ad'
homomorphically
(isomorphically)
simulates
A by i\ : B
—>•
A, T
2
: Y -» X'*
having
the
following
properties:
\T2(y)\
=
^(y)!,}?
e Y;
moreover,
for
every
positive integer
k, I
and
ji, y2 € F, the kth
letter
ofr^yi)
and the tth
letter
of 2)
coincide
only
ifk = t
andy\
=
Y2-
Given
a
digraph
D =
(V,E),
letDl
= (V, E') be a
digraph with
E' =
EU{(i,
i) \i €
V}.
Similarly,
if is a
(nonempty)
class
of
digraphs, then
we put = {D
l
\ D A).
Thus,
for
every digraph
D, a
D
£
-product
of
automata
is a
general product having
an
underlying
graph
D
l
.
Similarly,
if M is a
D
l
product
of
automata
and D A
holds
for a
class
of
2.4. Automata Networks
and
Products
of
Automata
65
digraphs,
then
M is
also
said
to be
-product.
In
this
sense
we
will speak about
-
product, -product, product, etc.
The
following statement
is
obvious.
Proposition
2.56. Given
a
digraph
D, an
automaton
is a D
l
-product
of
automata
A
t
, t
=
1,...,
n, if and
only
if it is a
TJ-product
of
products
A
t
(X
t
,
<p
t
)
of
automata
A
t
, t
=
1,...,
m,
each having
a
single
factor.
Direct
consequences
of
Proposition
2.56 include
the
following three statements.
Proposition
2.57.
Every q*-product
of
automata
A\,...,
A
n
coincides with
a
diagonal
product
of
automata
B\,...,
B
n
,
where
B
f
is a
single-factor
product
of
Ai for
every
i =
!,...,«.
Moreover,
every q
l
-product
of
automata
Ai,i
=
1,...,
n,
coincides with
a
quasi-
direct
product
of
automata
BI
which
are
each
single-factor
products ofAi.
d
Proposition
2.58. Every quasi-direct product
of
automata
A\,...,An
coincides with
a
diagonal
product
of
automata
B\,...,
B
n
,
where
Bi is a
loop-free
product
of
a
single factor
Ai
for
every
i =
1,...
,n.
Proposition
2.59.
Every a.\-product
of
automata
AI,
...,
A
n
coincides with
an
UQ-
product
of
automata
B\,...,
B
n
,
where
BI is a
product
of a
single factor
Ai for
every
i
=
l,...,n.
The
next
six
statements
are
also
obvious.
Proposition
2.60.
The
ctQ-product
coincides with
the
a\-pwduct.
In
addition,
ifi > 0,
then
the
af-product
coincides with
the a,
-product.
Proposition
2.61. Every q
l
-product
is a
v\-product. Furthermore, every
vf-product
is a
vi+i-product.
Proposition
2.62. Given
a
cycle digraph
T>
with
V =
({1,...,
m},
{(1,
m),
(2,1),
(3, 2),
...,
(m, m
—
1)}),
let M be a
T^-product
of
automata. Then
M
also
is an
a.i-product
of
its
factors.
Proposition
2.63. Suppose that
the
automaton
M. is an
oiQ-product
of
factors
M.\ and
M.2,
where
MI is an a,
-product
ofAi,...,A
m
(having
m
factors
for a
given positive integer
m);
moreover,
M.I is an
aj-Vk-product
(aj-v^-product)
of
Am+i,...,
A
n
.
Then
M. is an
oimsx.(i,jr
v
m+k-product
(am^ajyv^-product)
ofA\
,...,A
n
Proposition
2.64. Suppose that
an
automaton
A can be
represented homomorphically
by
a
general product ofnilpotent automata. Then
A is a
nilpotent automaton.
Proposition
2.65. Given
a
monotone automaton
A
suppose that
B is a
single factor general
product
of
A
Then
B is a
monotone automaton.
66
Chapter
2.
Directed Graphs, Automata,
and
Automata Networks
Next
we
prove
the
following.
Proposition
2.66.
Let
be
a
product
of
automata having
an
underlying
graph
=
({1,
...,»},£),
vertices
with
such
that
(
suppose
that
for any
pair
implies
Then
there
exists
a
product
having
the un-
derlying
graph
with nodes
and
edges
such
that
for any
whenever
Proof.
By the
condition
on
edges,
do
not
depend
on
their
(i +
l)th,...,
nth-state
components.
MX
any
arbitrary
We
construct
the
following feedback
functions:
where
It
is
easy
to
check that
the
product
A'
having
the
above feedback
function
components
satisfies
the
required conditions.
Corollary 2.67.
Every
cascade
of
automata
can be
isomorphically
represented
by a
cascade
of
(copies
of the
same) automata such that
for
each
i, at
most
one
feedback
function
<PJ
really
depends
on the
state
of
At.
Also,
the
analogous statement
holds
for the
a
\-product.
Completeness problems
are
investigated intensively
for
several families
of
products
of
automata.
A
class
1C
of
automata
is
called complete with
respect
to
homomorphic
(isomorphic)
representations/simulations
under
the
given
type
0
of
products
if
every automaton
can be
represented/simulated homomorphically (isomorphically)
by a
0-product
of
automata
in
1C.
We
also
say
1C
is
homomorphically
(isomorphically)
complete under
the
©-product
if
every
finite
automaton
can be
homomorphically (isomorphically) represented
by a
0-product
of
automata
from
1C.
Homomorphic (isomorphic) completeness under
any of
various other
products
is
defined
analogously.
1C
is
called
finite if it has a finite
number
of
elements. Furthermore,
it is
said that
1C
is
minimal
if
for
every
A e
1C,
1C
\ A is not a
complete class
of
automata with respect
to
homomorphic (isomorphic) representations under
the
©-product.
2.4. Automata Networks
and
Products
of
Automata
67
Theorem
2.68 (Gluskov
decomposition
theorem).
A
class
1C
of
automata
is
complete
with
respect
to
isomorphic
representations
under
the
general product
if
and
only
if
there
exists
an
automaton
A =
(A,X,8)
in K.
which
has
input
letters
x\,
X2,
x^,
X4
€ X and
distinct
states ao,a
A
such that
<S(0o>*i)
= oo (
,X2)
=
a,8(a,X3)
= a, and
8(a,X4)
=
hold.
GLU§KOV CRITERION
Proof.
For the
proof
of
necessity,
let
be
a
product
of
automata
such
that
a
subautomaton
of B has an
iso-
morphism
onto
A. For
appropriate states
ana in-
put
letters
let
Because
of
there exists
with
Let
and
Then
.
Thus
t
has the
conditions
01
necessity.
Conversely, prove that
an
arbitrary automaton
can
be
represented
isomorohicalry
bv a
power
or A.
Using
the
transitive property
of
isomorphic representation, without loss
of
generality
we
mav
assume that
Define
the
functions
such
that
for
every
implies
whenever
Clearly, then
the
power
isomorphically
represents
M,
where
the
appropriate isomorphism
is
having
and
The
proof
is
complete.
Note that
in the
proof
of
sufficiency
of the
above theorem,
the
automaton
M. can
also
be
represented
by a
power
of A
having
k >
Iog
2
n
factors.
(We
leave
to the
reader
the
proof
of
this statement.)
For
homomorphic representations
by
automata networks,
the
minimal computational
elements required
to
achieve
an
arbitrary
finite
state computation
are
characterized
in the
Letichevsky decomposition theorem
by a
simple criterion. Necessity
of the
criterion will
be
shown
in
Proposition 2.71. Although giving
a
proof
of
sufficiency
is not
difficult,
we
delay this until
the end of
Chapter
5.
There
two
proofs
of
sufficiency
are
derived
from
much
stronger independently proved results (e.g., Theorem 5.26).
Theorem
2.69 (Letichevsky
decomposition
theorem).
A
class
K,
of
automata
is
complete
with
respect
to
homomorphic
representations
under
the
general
product
if
and
only
if
there
68
Chapter
2.
Directed Graphs, Automata,
and
Automata Networks
exists
an
automaton
A= (A, X, 8)
which
has a
state
a € A, two
input letters
x,y X,
and
two
input words
p, q € X ,
under which
It
is
said that
an
automaton
A
satisfies
Letichevsky's criterion
if it has the
above
property
(*).
If A = (A, X, 8)
does
not
satisfy
Letichevsky's criterion
but we
have
LETICHEVSKY
CRITERION
8(ao,
x)
5(0o.
y), and (« *P) =
«for
some
o G A, jc, y X, and /? X*,
then
A
satisfies
the
semi-Letichevsky criterion. Otherwise
we say
that
A
does
not
satisfy
any
Letichevsky
criteria
or is
without Letichevsky criteria.
Proposition
2.70.
Let
there
be
given
an
automaton
A = (A, X, 5), a
state
O
A,
four input
words
u, v, p,q € X*
with
\p\ = \q\
under which (ao,
u) ^
8(
ao,
v),
and8(ao,
up) =
8(ao,
vq) = a$.
Then
A
satisfies
Letichevsky's criterion.
Proof.
We
shall
use the
following simple fact. Assume that there
are w\,
W2,
w(, w'
2
e
X*, x,y e X
w\xw2,
w(yw'
2
€
{up,
vq}
such that 8(ao,
w\) =
8(ao,
w(),
8(ao,
w\x)
^
8(ao,
w(y). Then
we
obtain Letichevsky's
criterion
by
setting
ao, u, v, p, q to
8(ao,
w\)(=
8(ao,
w()),
x, y,
W2U)\,
w
2
wi,
respectively. Therefore,
it
remains
to
study
the
case when
for
every
w\,
W2,
w{, w'
2
e X*, x, y e X
with
w\xw2,
w[yw'
2
€
{up,
vq}
and5(oo,
^i) =
8(ao,
w'i),
it
holds that 8(ao,
w\x)
=
8(ao, w(y}.
In
this case, there
are
x\,..
.x
n
€ X
having
u = xi • • •
x,,,
p =
x
i+
i
•••X
H
(XI---
x
n
y,
v = xi • • •
x
}
,,
q =
x
j+i
• • •
x
n
(xi
• • •
x
n
)
1
for
appropriate
s, t 0. But
(ao,
) (a ,v)
implies
i j.
Hence
\p\ ^
\q\,
a
contradiction.
D
If
a
class
1C
of
automata contains
an
automaton satisfying Letichevsky's criterion,
then
we
also
say
that
/C
satisfies
Letichevsky's criterion. Otherwise,
we say
that
/C
does
not
satisfy
it. If K
does
not
satisfy Letichevsky's
criterion
but
there
exists
A
fC
such
that
A
satisfies
the
semi-Letichevsky criterion, then
it is
also said that
1C
satisfies
the
semi-
Letichevsky
criterion. Otherwise,
we
also
say
that
1C
does
not
satisfy
Letichevsky criteria
or 15
without
any
Letichevsky criteria.
As
already mentioned, necessity
of the
Letichevsky
criterion
in
proving
the
Letichevsky
decomposition theorem follows
by the
next statement.
Proposition
2.71.
Suppose that
a
product
of
automata
satisfies
Letichevsky's criterion.
Then
it has a
factor with this property.
2.4. Automata Networks
and
Products
of
Automata
69
SEMI-LETICHEVSKY CRITERION
WITHOUT LETICHEVSKY CRITERIA
Proof.
Let
)
be a
product
of
automata
Suppose
that
A
satisfies
Letichevsky's
criterion.
Then
there
are a
state
,
input letters input words
such
that
and, simultaneously,
.
But
then there
are
with
and
such that and,
simultaneously,
But
then
A
t
has
Letichevsky
s
criterion.
70
Chapter
2.
Directed Graphs, Automata,
and
Automata Networks
Proposition
2.72.
Suppose
that
a
product
of
automata
satisfies
the
semi-Letichevsky
cri-
terion.
Then
it has
either
a
factor with
Letichev
sky's
criterion
or a
factor with
the
semi-
Letichevsky
criterion.
Proof.
Let A = A
1
x • • •
xA
n
(X,
,...,
(p
n
)
be a
product
of
automata
A
t
—
(A
t
,
X
t
,
t
), t
=
1,...,n.
Suppose that
A
satisfies
the
semi-Letichevsky criterion. Then there
are a
state
(a
1
,...,
a
n
e A
1
x • • • x A
n
,
input
letters
x, y e X,
input words
p, q e X*
such that
(
1
(a
1
,
1
(a
1
,
...,a
n
,*)),...
,
n
(a
n
,
p
n
(a
1
,
...,a
n
,
x)))
(a
1
,
(a
1
,
...,a
n
,y)),...,
(an,
n(a
1
,...,a
n
,y))),
and,
simultaneously,
(
1
(a
1
,
1
(a
1
,...,
a
n
,
xp))
,...,
n
(a
n
,
n
(
a
1
,...
,a
n
,
xp)))
=
(a
1
,...,
a
n
).
But
then there
are t e
{1,...,n},
x
t
=
<p
t
(a
1
,
•• •,
a
n
,x),y
t
=
t
(a
1
,...,a
n
,y),p
t
=
t
(a
1
,..
.,a'
n
,
p),
with
(a
1
,...
,a'
n
)
=
1
(a
1
,
p
1
(a
1
,...,a
n
,x)),...,
n
(a
n
,
n
(a
1
,...,a
n
,x)))
and
(a
1
",...,
a =
1
(a
1
,
1
(a
I
,
...,
a
n
,
y)),
• • •,
(a
n
,
(a
1
,
• • •, a
n
,
y)))
such that
8
t
(a
t
,
x
t
)
t
(a
t
, y
t
), and,
simultane-
ously,
8
t
(a
t
,x
t
p
t
)
= a
t
. It
does
not
matter whether there exists
a q
t
=
(p
t
(a'{,...,
a
n>
9)
w
i
m
(
a
t,
ytqt)
= a
t
because then
A
t
has
either Letichevsky's criterion
or the
semi-Letichevsky criterion.
The
next
two
observations show that
a
statement analogous
to
Proposition
2.71
does
not
hold
for the
semi-Letichevsky criterion.
Proposition
2.73.
There
exists
an
automaton having Letichevsky criterion such that
it has
a
single-factor
product
satisfying
the
semi-Letichevsky
criterion.
Proof.
Let A =
({0,1,
2},
{x
0
,
x
1
,
x
2
],
8) be
defined
by
5(0,
x
i
) = i, (1, x
i
) = 0,
5(2,
x
i
)
= 2, i = 0, 1, 2. Let
.A({x,
y), p) be
given with
p(i,
x) = x
1
,
p(i,
y) = x
2
, i = 0, 1, 2.
Then
(0, (0, x)) = 0, (0,
p(0,
y)) = 2,
5(2, p(2,
x)) =
5(2,(2,y))
= 2, and
5(1,
(1, x)) =
5(1,
(l,
y))
= 0. It is
easy
to
check
that
A
satisfies
Letichevsky's
cri-
terion,
but the
product
A({x,
y},
<p)
does
not
satisfy
it.
However,
A({x,
y},
<p)
satisfies
the
semi-Letichevsky criterion.
Proposition
2.74.
There
exists
an
automaton having Letichevsky criterion such that
it has
a
single-factor
product which
is
without
any
Letichevsky
criteria.
Proof.
Let us
consider again
the
automaton
A =
({0,
1, 2},
{X
0
,
x
1
,
X
2
},
8}
with
5(0, x
i
,)
=
i,
(1,x
i
,-)
=
0,5(2,
x
i
) = 2,i =
0,1,2.
Define
A({x,
y],
)
with
p(i,x)
=
(i, y) = x
2
, i =
0,1,
2.
Then
for
every
i e {0, 1, 2} and p
<=
[x, y}*
with
\p\ > 2,
we
obtain
(i,
<p(i,
p} — 2.
Thus
the
product
A([x,
y},
<p)
does
not
satisfy Letichevsky's
criteria.
Proposition
2.75.
Given
a
product
of
automata,
it is
without
Letichevsky
criteria
if
all its
factors
have this
property.
Proof.
Consider
a
product
of
automata such that
all of its
factors
are
without Letichevsky
criteria.
If
this product satisfies Letichevsky's criterion, then,
by
Proposition
2.71,
one of its
factors
has
this property, which
is a
contradiction.
If
this
considered
product
has the
semi-
Letichevsky criterion, then,
by
Proposition
2.72,
one of its
factors
has
either Letichevsky's