D?m?si P., Nehaniv C.L. Algebraic Theory of Automata Networks. An Introduction
Подождите немного. Документ загружается.
4.2. Without
Any
Letichevsky Criteria
121
Proposition
4.13.
There
exists
an
automaton
A
without
Letichevsky
criteria
and a
class
1C
of
automata
having
the
semi-Letichevsky
criterion such that
A
cannot
be
represented
by an
cto-product
of
factors
from K..
Proof,
Let /C be a
singleton class having
the
automaton
B =
({1,
2, *},
{*i, x
2
],
<$)
with
8(1,
xi) = 2,
6(2,
x
2
) = 1,
6(1,
x
2
) =
8(2, jci)
=
6(*,
*i) =
6(*,
*
2
) = *.
Moreover,
let
A =
({0o,
«i,
a
2
}{y1,
y
2
},
6') be
defined
by
6
/
(o
0
,
yi) = «i,
S'(OQ,
y
2
) = a
2
,
8'(ai,
vi) =
<$'(0i,
y
2
} = a\,
S'(a
2
,
yi) =
S'(a
2
,
y
2
) = a
2
.
Consider
an
arbitrary ao-power B
n
(X,
<pi,
...,
<pn)
of B and
prove that
for
every state
(b\,...,
b
n
) of B
there
exists
a p e X*
such
that
(8(bi,
<pi(bi,
...,b
n
,
p)),...,
(8(b
lt
<p
n
(bi,
...,b
n
,
p))))
=
(*,...,
*).
Indeed,
if the first two
letters
of p are the
same (assuming
\p\ 2),
then 6(b\,
(p\
(b\,
...,£„,
p)) = *. And
then,
if the
third
and
fourth letters
of p are the
same (assuming
\P\
2: 4),
then
8(b
2
,<p2.(bi,
...,£„,
p)) = *.
Repeating this procedure,
we
obtain
(8(bi,
<pi(bi,
...,b
n
,
p)),...,
(8(b
n
,
<p
n
(bi,
...,&„,
p))))
=
(*,...,*)
provided
p = z
2n
for
some
z e X.
Suppose that, contrary
to our
assumptions, there
exists
a
subautomaton
B'
=
(B', X'5")
of
this ao-power such that
B' can be
mapped homomorphically onto
A by a
homomorphism
i/r
=
(fa,
fa).Let z1, Z
2
e X' be
given such that
(z1)
= yi and
(z2)
=
y
2
.
Moreover,
let fa(b) = a
0
for
some
b e B'.
Then
6"(fc,
zf
1
)
=
8"(b,
z ) =
(*,...,*)
andai
=
8'(fa(b),
^(zf
1
))
7^
8'(fa(b),
^2(^2"))
= fl
2, a
contradiction. Therefore, none
of
the
«o-powers
of 5 can
represent
.A
homomorphically.
This
ends
the
proof.
Problem 4.14.
/5 ft
decidable
for
every
positive
integer
k and
every
finite
class
K, of
automata
having
the
semi-Letichevsky
criterion whether
or not a finite
automaton
can be
represented
homomorphically
by a
^-product
of
factors
in
1C?
By
Corollary 4.10
we can
derive
the
following well-known statement.
Corollary 4.15. Given
a
class
/C
of
automata
having
the
semi-Letichevsky
criterion,
let
A be an
automaton which
can be
represented
homomorphically
by a
product
of
factors
from
/C.
Then
A can
also
be
represented
homomorphically
by an
ct\-product
of
factors
from
1C.
4.2
Without
Any
Letichevsky
Criteria
Now
we
study automata satisfying neither Letichevsky's criterion
nor the
semi-Letichevsky
criterion.
The
following statement
is
obvious.
Proposition
4.16.
A = (A, X, 6) is an
automaton without
any
Letichevsky
criteria
if
and
only
if
for
every
state
OQ
e A,
input
letters
x,y € X, and an
input
word
p e X*
having
5(«o,
xp) =
OQ,
it
holds
that
S(OQ,
x) =
6(#o,
)0-
Obviously,
if A = (A, X, 5) has the
above properties, then there exists
a
nonnegative
integer
n
such that
for
every
p e X*
with
|p| > n,
each 8(a,
p) (a e A)
generates
an
autonomous state-subautomaton
of A
Denote
by
n^(<
n) the
minimal nonnegative integer
having
this property.
122
Chapter
4.
Without
Letichevsky's
Criterion
Proposition
4.17.
n
A
<
max(|A|
- 2, 0).
Proof.
Take
out of
consideration
the
trivial cases. Thus
we may
assume
|A| > 2.
Con-
sider
a € A,
xi,...,
x
m+2
€ X,
having 8(a,
xi • • •
x
m
x
m+
i)
^
8(a,xi---
x
m
x
m+2
).
If
a,
8(a, *i), 8(a,
Xix
2
),...,
8(a,
x\ • • •
x
m
), 8(a,
xi • • •
x
m
x
m+
i),
8(a,
*i • • •
x
m
x
m+2
)
are
not
distinct
states,
then
A
satisfies
either
Letichevsky's
criterion
or the
semi-Letichevsky
criterion,
a
contradiction.
Hence,
m < \A\
—
3.
Thus
n^ < \A\
—
2.
We
also
note
the
next direct consequence
of
Proposition
4.16.
Proposition
4.18.
If
A is a
strongly connected automaton without
any
Letichevsky criteria,
then
A is
autonomous.
By
this observation,
we
immediately
get the
following.
Proposition
4.19. Suppose that
A= (A, X, 8) is a
strongly connected automaton without
any
Letichevsky criteria.
There
exists
a k > 0
such that
for
every
a, b € A, a = b,
if
and
only
if
there exists
a
pair
p,q e X*
with
\p\ =
|#|(modA:)
19
and8(a,
p) =
8(b,
q).
Lemma
4.20. Given
an
automaton
A= (A, X, 8)
without
any
Letichevsky criteria,
a e A
is
a
state
of a
strongly connected state-subautomaton
of A
if
and
only
if
there exists
a
nonempty
word
p e X*
with 8(a,
p) = a.
Proof.
Let a e A be a
state
of a
strongly connected state-subautomaton
of A. By
definition,
for
every nonempty word
q e X*,
there
exists
a
word
r e
X*wtih8(a,qr)
= a.
Conversely,
suppose that 8(a,
p) = a for
some
a e A and p € X*, p .
Then
for all
prefixes
p'
of
p and
input letters
x, y € X,
8(a, p'x)
=
8(a, p'y). Therefore,
for
every
q e X*,
8(a,
q) =
5(a,
r),
where
r is a
prefix
of p
with
\q\ =
|r|(mod
\p\).
But
then
a
generates
a
strongly connected state-subautomaton
of A.
We
shall
use the
following consequence
of the
above statement.
Proposition
4.21.
Let A = (A, X, 8) be an
automaton without
any
Letichevsky cri-
teria. Moreover, suppose that
a & A is not a
state
of any
strongly connected state-
subautomaton of'A.
If'8
(b, p) = a
for
some
b e A
and
nonempty
p € X*,
then8(a,
q) ^ b,
q
e X*.
Conversely,
if
8(a,r)
= c for
some
c e A and
nonempty
r e X*,
then
8(c,q)^a,qeX*.
d
Next
we
prove
the
following
proposition.
Proposition
4.22. Given
a
class
1C
of
automata without
any
Letichevsky criteria,
let A be
an
automaton which
can be
represented homomorphically
by a
general product
of
factors
from
JC.
There
exists
an
automaton
A e /C, a
q-power
M
of
A
with
a
single factor such
that
M. is an
autonomous automaton; moreover,
A can be
represented homomorphically
by
a
diagonal product
of
its
connected state-subautomata
and M..
19
Recall
that
a = fc(modn)
means
n\a
—
b.
Moreover,
a
b(modn) means
n/a
—
b.
4.2.
Without
Any
Letichevsky Criteria
123
Proof.
Consider
the
automaton
A' —
(A',
X',
<$')•
We
distinguish three
cases.
Case
1.
There exists
an A = (A, X, 5) e
K,
having
a
nontrivial cycle.
In
other words,
there
are
distinct states
a\,...,
a
m
e A, in > 1, and
(not necessarily distinct) input letters
xi,...,x
m
e X
such that
5(a,-,
jc,-)
=
a,
+
i(
m0
dm)-
By
Proposition 4.16, this implies that
for
every
jc
e X,
8(a
t
,
x) =
a,
+
i(mod
m
).
Consider
a fixed jc e X and let M =
A(X,
<p)
be
given
such
that
(p(a,
x') = x for
every
a e A and x' e X.
Then
M. is an
autonomous automaton
which
is a
<?
-power
of A
with
a
single factor such that
for
every distinct
&,€e{l,...,m},
8(dk,
<p(dk,
p)) 7^
8(ai,
<p(at,
p)),p
e X*.
Using Proposition 2.28, this ends
the
proof
of
our
case.
Case
2.
There exists
an A — (A, X, 5) e /C
having
two
distinct trivial cycles. This
means that there
are
distinct states
a, b € A and
(not necessarily distinct) input letters
x\,X2
€ X
having 5(a,
*i) = a and
S(£,
x
2
) = b. But
then, again applying Proposition
4.16,
we
obtain
for
every
x e X,
8(a,
x) = a and
8(b,
Jt) = b.
Thus, similar
to
above,
we
can
define
the q
-power
M of A
with
a
single factor such that
8 (a,
(p(a,
p)) /
8(b,
(p(b,
/?)),
p € X*.
Then
we can use
Proposition 2.28 again, which completes
the
proof
of
this case.
Case
3.
Neither
of the two
cases above apply. Using Proposition 2.23, this means that
all
elements
of
K,
are
nilpotent automata.
But
then, using
Proposition
2.64,
A' is a
nilpotent
automaton
whenever
it can be
represented homomorphically
by a
general product
of
factors
in
/C.
Therefore,
A is a
directable automaton. Thus, applying Proposition 2.27,
it can be
represented homomorphically
by a
diagonal product
M' of its
connected state-subautomata.
Then
it is
obvious that
M'
AA4
also homomorphically represents
A
whenever
M. and M.'
have
the
same input
set and At is an
arbitrary autonomous
q
-power
of an
automaton
in
JC
with
a
single factor. (Obviously,
if X'
denotes
the
input
set of M' and A = (A, X, 5) is an
arbitrary
element
of
/C
with
a fixed
input letter
x e X,
and, moreover,
M =
A(X,
<p)
is a
^-product with
<p(a,
x') = x, a e A, x' e X',
then
M has
this property.) This implies
the
validity
of our
statement
in
this
case.
D
Lemma
4.23.
Let A = (A, X, 8) be an
automaton without
any
Letichevsky
criteria.
If
there
are a € A, q, q' e X*, \q\ —
\q'\
> \A\ — 1,
8(a,
q) ^
8(a,
q'\
then
for
every
pair
of
words
r, r' e X*, \r\ =
\r'\,
we
have
8(a,
qr) ^
8(a, q'r').
Proof.
Suppose that
our
statement does
not
hold, i.e., there
are a e A, q, q', r, r' e X*, \q\ =
\q'\
> \A\ - 1, |r| =
|r'| having 8(a,
q)
^=
8(a,
q') and
8(a,
qr) =
8(a, q'r'). Then,
of
course,
|r| =
|r'|
> 0. We
distinguish
the
following three cases.
Case
1.
There
are
qi,n,
q
2
,r
2
,q{,
r[,q'
2
,r'
2
with
q =
q\r\
=
q
2
r
2
,q'
=
q{r(
=
q
2
r
2
,
\qi\
<
\q
2
\, \q[\
<
\q'
2
\
such that 8(a,
q{) =
8(a,
<?
2
),
8(a,
q{) =
8(a, ^).
20
But
then,
by
Proposition 4.16,
8(a,q\w)
=
8(a,qiw')
and
8(a,q{w)
=
8(a,q(w')
for
every
w, w'
eX*, |u;|
=
|iy'|.
Thus, because
of
&(a,q\)
=
8(a,q
2
)
and5(a,
q()
=
8(a,q
2
),
we
obtain that
for
every
w, w' € X*
there
are z, z' e X*
with 8(a, q\wz]
=
8(a,
q\)
and
8(a,
q
w'z')
=
8(a, q{). Thus
q\r\—q,
q'^ =q'
imply that 8(a, qrz}
=
8(a,
q\) and
8(a,
q'r'z')
=
8(a,
q{)
hold
for
some
z, z' e X*.
This
means that
8(a,qrzri)
=
S(a,#)and
8(a,
q'r'z'rQ
=
8(a, q').
Putb
=
8(a, qr)(= 8(a, q'r')),
c =
8(a,
q), c' =
8(a, q'). Then
8(b,
zr
1
)
= c c' =
8(b, z'r{)
and
8(c,
r) =
8(c',
r') = b.
Therefore,
by
Proposition 2.70,
A
satisfies Letichevsky's criterion,
a
contradiction.
20
This
holds automatically
if \q\ =
\q'\
>
\A\.
124
Chapter
4.
Without
Letichevsky's
Criterion
Case2. Therearegi,
r\, qi,
TI
with*?
=
q\r\
=
qiri,
\q\\
<
\q2\, suchthat5(a,
q\) =
8(a, q2),but5(a,
q() ^
8(a,
q'
2
)
holds
for all
distinct
prefixes
, of
-Theseassumptions
imply
(\q\
=)
\q'\
< \A\ — 1. On the
other hand,
\q\ =
\q'\
> \A\ — 1 is
supposed. Hence,
we
necessarily have
\q\ =
\q'\
= \A\ — 1.
Thus
we get
8(a,
q() ^
8(a,
q
2
) for all
distinct
prefixes
q{, q'
2
ofq',
where \q'\
= |A|
—
1.
This implies that
for
every
d e A
there exists
a
prefix
q[
ofq' with 8(a,
q() = d.
Then
for
every
d e A
there exists
an
r(
e X*
having 8(d,
r ) =
8(a, q').
On the
other
hand,
we may
assume 8(a,
qrzr\)
=
8(a,
q) as in the
previous case.
Now
we
suppose
8(a,qr)
=
8(a,q'r
f
)
as
before. Substituting
d for
8(a,q)
(=
8(a,
qrzri)),
there exists
an
r[
6 X*
holding 8(a, qr()
=
8(a, q').
Put b =
8(a, qr)x
(=
8(a,q'r'),c
=
8(a,q),c'
=
8(a,q').
Hence 8(b,
zn) =
c,8(b,
zrir{)
= c' and
8(c,
r) —
8(c',
r') = b
(with
c
c'}. Therefore,
by
Proposition 2.70
we
obtain again
that
A
satisfies Letichevsky's criterion contrary
to our
assumptions.
Case
3. Let
8(a,
q\) /
8(a,
q2)
and
8(a,
q{)
^
8(a,
q^)
for
all
distinct prefixes
q\, qi
of
q and
q{,q'
2
of q',
respectively. Then|^|
=
\q'\
< \
A|-l. Recall that
\q\ =
\q'\
>
\A\-l
is
also assumed. Thus
\q\ =
\q'\
= \A\ — 1,
which implies that
for
every
d € A
there
are
ri,r{
€ X*
satisfying 8(d,
n) =
8(a,q)
and
8(d,r{)
=
8(a,q
f
).
Therefore, assuming
8(a,
qr) =
8(a, q'r')
for
some
r, r' 6 X*, and
substituting
d for
8(a, qr)(= 8(a, q'r')),
we
obtain 8(a, qrn)
=
8(a,
q},
8(a, qrr{}
=
5(a,
q'}
(with 5(a,
qr) =
8(a, q'r')).
Put c =
8(a,
q), c' =
8(a, q'). Then 8(d,
n) = c,
8(d,
r() = c',
8(c,
r) =
8(c',
r') = d
(with
c £
c').
By
Proposition 2.70, this implies that
A
satisfies Letichevsky's criterion,
a
contradiction
again.
Lemma 4.24.
Let A = (A, X, 8) be an
automaton without
any
Letichevsky
criteria.
For
every
state
a € Awe
have
one
of
the
following
two
possibilities:
(1)
There
existq,
q' € X*, \q\ =
\q'\
> |A| - 1,
suchthat8(a,
qr) ^
8(a, q'r')
for
every
r,r' £X*,
|r| =
|r'|.
(2)
8(a,q)
=
8(a,q')
for
every
q,q
f
€ X*, \q\ =
\q'\
> |A| - 1.
Proof.
Suppose that
(1)
does
not
hold. Then
for
every
q, q' e X*, \q\ =
\q'\
> |A|
—1,
there
exist
r, r' e X*, \r\ =
\r'\, having 8(a,
qr) =
8(a, q'r'). Using Lemma 4.23, 8(a,
qr) =
8(a, q'r'),
\r\ =
|r'|,
and \q\ =
\q'\
> \A\ - 1
implies 8(a,
q) =
8(a, q'). Thus
(2)
holds
whenever
(1)
does
not
hold.
The
following statement
is
obvious.
Lemma 4.25. Given
a
digraph
V = (V, E), let v € V, pi, P2,
p'
2
,
Pi, P4 e V*
such that
PIP2P3VP4V
and
pip'
2
p3vp4v
are
walks
and
vp4V
is a
cycle.
\p2\
=
\p'
2
\(mod\p4V\)ifand
only
if
there
are
positive
integers
k, I
having \p\pip'3v(p4v)
k
\
=
Ipip^Psv^tv)*].
Lemma 4.26.
Let A =
(A,X,8)
be an
automaton without
any
Letichevsky
criteria.
Consider
a
state
a € A and
suppose
that
there
are
q,q'
€ X*, \q\ =
\q'\
|A| — 1,
8(a,q)
8(a,q').
Then
there
are
q,q'
(with
\q\ =
\q'\
\A\ - I)
such that
for an
appropriate
triplet
u,v,v'
€ X*, q = uv and q' =
uv',
for
which
we
have
the
following
4.2.
Without
Any
Letichevsky Criteria
125
properties:
(1) For
every
prefixes
z ofv and z'
ofv' with
\z\ =
\z'\
> 0,
8(a,
uz)
i=-
8(a, uz').
(2)
For
every
prefixes
wx ofz and
w'x' ofz' with
ww' A and x, x' € X,
S(a,
uw) =
8(a, uw')
implies
x = x'.
(3)
For
every
words
r, r' e X*
with
\r\ =
\r'\, 8(a, uvr)
^
8(a, uv'r').
Proof.
Consider
a e A and
suppose that
our
conditions hold; i.e., there
are q, q' e X*
having
\q\
=
\
q
'\
>
\A\-l,
8(a,q)
^
8
(a,
q').
In
this case,
by
Lemma 4.24,8
(a,
qr)
8(a,q'r')
holds
for
every
r, r' e X*
with
|r| =
|r'|
> 0.
Thus,
it is
enough
to
prove that
we
have
properties
(1) and
(2).
Then Proposition 4.17 implies that
8(a,q)
and
8(a,q') generate autonomous
state-subautomata
of A. We
will distinguish
the
following cases (omitting some
of the
analogous
ones).
Case
1.
There
are u, u', v, v', e X*
such that
q = uv, q' =
u'v', 8(a,
u) =
8(a,
u')
and for
every nonempty
prefixes
r of v and r' of v', 8 (a,
u)(=
8 (a,
u'))
(a , ') 8 (a, u')
(=
8(a,
u)) 96
8(a, ur),
and
8(a,
ur) ^
8(a, u'r').
21
Let, say,
\u\ >
\u'\
and let v" be a
prefix
of v'
with \v"\
=
\v\. Submit
q'
with
uv" and
then
we
will have
our
requirements.
Case
2.
There exists
a
prefix
u of q
having
<5(a,
u) =
<5(a,
q').
We
shall
use the
fact
that,
in
this case,
v ^ X for v e X*
with
q = uv
because
of
8(a,
q) ^
8(a, q').
Let
t2 e X* be a
nonempty word with minimal length having 8(a, q't\t2)
=
8(a, q't\)
for
some word
t\ e X* and
assume that
?2 is
minimal
in the
sense that
for
every nonempty
p
€ X*,
8(a,
q't\p)
=
8(a, q't\) implies \t2\
<
\p\-
22
Then, using that 8(a,
q
f
)
generates
an
autonomous state-subautomaton
of A, we
have
q = uv,
where
u is a
nonempty
prefix
of
t\t\
for a
suitable
k > 0.
To
prove that
in
this case
\u\ =
j^r'Kmod
|?2l)
is
impossible, assume
the
contrary.
Recall
again that 8(a,q')
generates
an
autonomous state-subautomaton
of A. But
then,
applying Lemma 4.25, there
are
words
r, r' e X*, \r\ =
\r'\, having 8(a,
qr) =
8(a, q'r').
By
Lemma 4.23, then
|q| =
|q'|<|A|
—
1,
contrary
to our
assumptions. Thus
we
have
the
following
cases.
Case
2.1. Suppose
\u\ |
|(mod |r
2
|) such that
for all
prefixes
u\ of u and
u
(
of
q'
with uiu(
i=.
A,
8(a,
u\) =
8(a,
u()
implies
u\ — u and u\ = q'.
Then
we
obtain
our
requirement again (having
q = uv,
where
v is a
nonempty
prefix
of
t\t\
for a
suitable
k>0).
Case
2.2. Assume
\u\ ^ |
|(mod
lt
2
l)
and, simultaneously, let,
for
some
prefixes
u\
of
u and u\ of q',
8(a,
MI)
=
8(a,
u\)
such that
u =
u\v\,
q' =
u\v(\ furthermore, neither
m = u\ = X nor v\ = v( = .
23
If vi =
X
and v( X,
then 8(a,
u\} =
8(a, u'^)
^
8(a,
u'
1
v'
l
v)(=
8(a,uv)).
Recall that
u is a
nonempty
suffix
of q. But
then
A has
either
Letichevsky's criterion
or the
semi-Letichevsky criterion,
a
contradiction. Similarly,
it
also
leads
to a
contradiction
if we
assume
v\ ^
A
and v1 .
Thus
X
^
[vi,
v(} can be
assumed
and
we may
also
assume
k$.{u\,u\]
analogously.
21
H
= u' =
X
is
possible.
22
The
finiteness of the
state
set of A
implies
the
existence
of t\ and t2-
23
If
MI
= u j =
A.
or v\ = i/j =
A.,
then
we may get
either
the
previous
case
or
this
case
considering
appropriate
MI,U],
vi, Vj
withuiu'j
^A-anduii/j
7^ A..
126
Chapter
4.
Without
Letichevsky's
Criterion
By
\i<\
|0'|(mod|r
2
|),
either
|
Ul
|
&
K|(mod|f
2
|)
or
|vi|
&
K|(mod|f
2
|).
Case
2.2.1.
Suppose
\u\\
^
|ui|(mod |f
2
|)
and
let, say, |ui|
<
\v{\.
Take
a
prefix
v
f
of
t\t
2
for a
suitable
k > 0
with
= \q\ and let us
consider
u\v\v'
instead
of q'.
Case
2.2.2. Suppose
|ui|
=
|u'p!(mod|f
2
|).
Then
|ui|
|i/p!(mod|f
2
|).
Let, say,
l"i I <
|M'I
I-
Take
a
prefix
v' of
fif|
for a
suitable
k > 0
with
(MI^I/!
= \q\ and
submit
q'
with
«i
i>i
i/.
In
both Case
2.2.1
and
Case 2.2.2,
we
have words
24
it;,
w\, W2, u/p w'
2
e X*, A. ^
{w\,w'
l
},
\w\\
=£
lu/jKmodl
l), w'
2
is a
prefix
of wi
(or,
in the
opposite case,
W2
is a
prefix
of
w'
2
),
q =
ww\W2,q'
=
ww^w^, such that S(a,
ww\)
=
8(a,
ww'j),
and
8(a,
ww\)
(=
S(a, ww\}) generates
an
autonomous state-subautomaton
of A.
Then
let iu, w\,
W2,
w ,
w'
2
X* be
arbitrary strings with these properties
for
which min(|w1
|,
\w(
|) is
minimal.
Suppose that
for
every nonempty proper
prefixes
z\ of w\ and z\ of w( we
have
8(a,
w) £
[8(a,
wz\),
8(a, wz\)}
and
8(a,
wz\)
•£
8(a,
wz[). Moreover, recall that
8(a,
w) ^
8(a,
ww\)(=
8(a, ww{)) because 8(a,
ww\)(=
8(a, ww()) generates
an
autonomous
state-subautomaton
of A. By
these conditions,
we are
done, since
we
have
our
properties
for q =
ww\W2,
q' =
ww'^w^.
Now we
assume
\w\ \ \w(
|(mod j^l) such that
for
some prefixes
z\ of w\ and z\ of
w{,
8(a,
z\) =
8(a,
z(
)
such that
w\ =
ziZ2,
w{ =
z\z'
2
\ furthermore, neither
z\ = z\ =
A.
nor Z2 = z'
2
—
..
25
We can
prove
A
{z\,
z(, Z2,
z'
2
]
in a way
similar
to the
proof
of
X
i
{u1,
u'p
vi,v{}
in
Case
2.2.
Then either
|zi|
|zil(mod
|r
2
|)
or
|z
2
|
|z
2
|(mod
|t
2
|).
It
remains
to
prove that these cases
are
impossible.
If
|z
1
|
|zil(mod|f2l)
and, say,
\Z2\
>
\Z
2
\,
then considering
the
prefix
w'
2
of
w'
2
having
\Z2W
2
\
=
\z
2
w
2
\,
we can
submit
w, w\, W2, w{, w'
2
with
w, z
1
,
z2w2,
z{,
Z2W
2
,
contrary
to the the
minimality
of
min(|
w\ \, \
w{
\).
If
Izil
=
kil(mod
|r
2
|)
with
|z
2
|
|z
2
|(mod
|t
2
|) and, say, |z1|
>
|z'|,
then consid-
ering
the
prefix
w'
2
of w'
2
having \z\w'
2
\
= | | , we can
submit
w, w\, w(, W2, w'
2
with
, Z2,
w>2,
u>2,
contradicting
the
minimality
of
min(|w\|,
\w( |).
The
proof
is
complete.
We
shall
use the
following definition.
Let A = (A, X, 5) be an
automaton.
For
every
pair
a, b € A,
consider
a fixed
x
a
,b
e X
with
5(a, x
a,b
)
= b if it
exists
and put
p
a
(x)
=
x
a,b
if
8(a,
x) = b.
Moreover,
put p
a
( ) = . and
p
a
(x\
• •
•x
n
)
=
p
a
(x\)pB(
a
,
Xl
)(x2}
• - •
Ps(a,x
r
-x
n
-i)(
x
n)-
Clearly, then
(a, w) =
8(a, p
a
(w)) holds
for
every
w X*.
Lemma
4.27.
Let A= (A, X, 8) be an
automaton without
any
Letichevsky
criteria.
Con-
sider
a, a, A, p e X*
with
S(a0,
p) = a.
If
there
are
q,q'
e X*,
\pq\
=
\pq'\
>
|A| — 1, (a, q)
8(a, q'), then
there
are an
input
letter
x e X, a
word
u € X*, and
single-factor
products
B = (A, X,
SB),
C = (A, X, 8c)
of
A
such
that
for
every
z, z' e X*
with
\z\ <
|z'|
<
\pu\
+ 1 we
obtain
(
(a0,
z),
8
c
(ao,
z)) (
(00,
z'),
8c(a
Q
, z')); more-
over,
{(8
B
(ao,z),8
c
(ao, z))\z
X*,\z\
<
\pu\},{(8
B
(ao,z),8c(ao,z))\z
=
Zixz2,z\,
Z
2
€ X*,
|zi|
=
\pu\]
and
{(8
B
(ao,
z),
8
c
(a
0
,
z))\z
=
Zix'z
2
,
x'
eX,x'
x,
zi,z
2
e
X*,
\Z1\
=
\pu\\ arepairwise
disjoint
sets.
24
In
Case 2.2.1,
of
course,
w = l,.
25
If
zi = zi =
A.
or
Z2
= z — .
then
we may get
either
the
previously discussed case
or
this case considering
appropriate
z\, z
,Z2,z'
2
with z\z\
. and
z2z2
••
4.2.
Without
Any
Letichevsky
Criteria
127
Proof.
Let A = (A, X, 5) be an
automaton without
any
Letichevsky
criteria.
Consider
a,OQ
e A, p € X*
with
<5(a
0
,
p) = a. If
there
are
q,q'
€ X*,
|p#|
=
\pq'\
> \A\ -
1,
S(a,
q) ^
8(a, q'), then
we may
assume
q = uv and
<?'
= uv' for
some
M,
v, u' e X*
such that
(1
)-(3)
of
Lemma 4.26 hold.
Put
u =
x\z,
v' =
x
2
z' with x\,X2
e
X,z,z'
e X*, |z| =
|z'|. Thus
for
every
prefix
wx of z and
u/*'
of z'
with
ww' ^
A
and x, x' e X, jc = x'
whenever 8(a, ux\w)
=
8
(a,
ux2w'~).
Therefore, without
any
contradiction,
we can
define
the
functions
<p
: A x X ->
A, ' : AxX -> A
having
the
following properties.
Let*',
y' e X be
arbitrary
fixed-input
letters
and for
every
b e A, y X, let
By
Proposition 4.16,
for
every
prefix
p' of
/?M,
8
(ao,
p') £
[8(ao,
pux\r),
8(ao, pux2r)
| r e
X*}.
(We
note that
S(a0,
p')
8(ao,
p")
also
holds
for
every pair
of
distinct
prefixes
p', p" of
pu.)
On the
other hand,
by our
assumptions
and
Lemma 4.23,
for
every
r, r' e
X*, \r\ =
\r'\,
it
holds that S(ao,
pux\zr}
S(a0,
pux2z'r'). Therefore, S(a0,
pux\zr')
^
8(ao,
pux
2
z'r').
But
then (8(a
0
,
pux\zr),
8(ao,
pux\zr))
(8(ao,
pux\zr'),
8(ao, pux2Z
f
r'))
is
valid
for
every
r, r' e X*. In
addition,
by
property
(1) of
Lemma 4.26,
for
every prefix
w of z and it/ of z'
with |u;|
=
|u/|,
(
(ao>
pux\w),
S( ,
pux\wj)
(S(OQ,
puxiw),
8(ao,
pux2U>')).
Therefore
the
single-factor products
B =
A(X,
(p)
and
C
=
A(X,
<p')
satisfy
the
conditions
of our
Lemma 4.27.
Lemma 4.28.
Let A= (A, X, 5) be an
automaton without
any
Letichevsky
criteria. Con-
sider
a, a0 A, p € X*
with 8(ao,
p) = a and
suppose
that 8(a,r)
= 5 (a, r')
holds
for
every
r, r' € X*,
\pr\
=
\pr'\
> |A|
—
1.
Assume that 8(a,
q)
8(a,
q')
holds
for
some
q, q' e X*,
\pq\
=
\pq'\
< |A|
—
1 and let q, q' be
words
of
maximal
length having this
property.
Then
there
are q = uv, q' = uv'
(having
\q\ =
\q'\
< |A|
—
1)
such that
we
have
the
following
properties:
(1)
For
all
prefixes
r ofv
andr'
ofv' with
\r\ =
\r'\
> 0, we
have 8(a,
ur) ^
8(a, Mr').
(2)
For all
prefixes
wx
of
v and
w'x'
of
v'
with
ww' ^
X
and
x,x'
€ X,
8(a,
uw) =
8(a,
MW/)
implies
x = x'.
(3) For all
distinct
prefixes
p\, P2
of
pq,
8(a0,
p\)
8(ao,
P2)-
(4)
For
all
words
r, r'
with
\r\ =
|r'|
>
\q\(= \q'\), 8(a,
r) =
8(a, r').
Proof.
Consider
a e A and
suppose that
our
conditions hold.
Suppose that
for
every
prefix
u of q and u' of q', 8 (a, u) =
8(a, «')impliesw
= u' =
A..
Obviously then
(1) and (2)
hold.
128
Chapter
4.
Without
Letichevsky's
Criterion
Now
let q = uv, q' =
u'v'
such that
MM'
^
X
and<5(a,
M)
=
8(a, u').
Suppose that
\u\
and
|M'|
are
minimal
in the
sense
that
for
every prefixes
u" of
M
and u'" of u'
with u"u"'
^ X
and
8(a,
u") =
8(a, u'"),
we
have
{u",
u'"}
-
{M,
u'}.
Assume that,
say,
M = A..
This implies
8(a,
u') = a
with
u' /: X. But
then,
by
Proposition 4.16,
a
generates
an
autonomous state-subautomaton
of A.
Therefore,
8(a,q)
=
8(a,q'),
a
contradiction.
Now
let X £ {u,
u'}.
Clearly,
v = v' = X is
impossible because
8(a,
q) ^
8(a, q'}.
Let,
say,
v = X.
Then,
by the
minimality
of
M
and u', we
have
(1) and (2)
again.
Next
we
assume
X ^
{M,
M',
u,
t/}.
If
|M|
=
|M'|,
then
we can
consider,
say,
uv'
instead
of
u'v'.
Therefore,
\u\ ^
\u'\
can
be
supposed.
Assume that,
say,
|M| >
\u'\.
Then submit
v
with
v",
where
v" is a
subword
of v'
with
\v"\
=
\v\.
Because
of the
minimality
of \u\ and
\u'\
for
every subword
w of
M
and w'
of
M'
with
|iy|, \w'\
> 0, we
obtain that
8(a,
iu) =
8(a,
w')
implies
w = u and w' = u'.
Submitting
q, q', u, u', v, v'
with
uv",
q', u, u', v", v' we get (1) and
(2).
Now
we
prove
(3),
omitting some analogous
cases.
If
there
are no
distinct prefixes
p(, p'
2
€ X* of pq'
with
8(dQ,
p() =
8(aQ,
p'
2
), then change
pq for pq' and pq' for pq.
Therefore,
in
this case,
we are
ready. Otherwise,
we may
suppose (ao,
p =
8(ao, p'
2
)
for
some distinct prefixes
p{, p'
2
e X* of
pq'. Let, say,
p( =
p'
2
r'
for
some nonempty
r' e X.
By
Proposition
4.16
and
8(ao, p'
2
)
=
8(ao, p'
2
r'), this implies that
8(ciQ,
p'
2
) generates
an
autonomous state-subautomaton
B of A.
Moreover,
8(GO,
P'\)
=
8(ay,
p'
2
r')
=
S(CIQ,
p'
2
),
r'
7^ X
implies that this autonomous state-subautomaton
is
strongly connected. Recall that
bythemaximalityof \q\(= \q'\), 8(ao,
pqx)
—
S(«o, pq'x') holds
for
every
x, x' €
X.Thus,
8(ao,
pqx)
is
also
a
state
of the
state-subautomaton
B of A.
Then
<$(a
0
,
pq) ^
8(a
0
, pq')
and
8(ao,
pqx)
=
8(ao, pq'x') imply that
8(ciQ,
pq) is not a
state
of B.
Indeed,
if
8(ao,
pq)
and
8(ao,
pqx)
are
states
of B
with 8(ao,
pq) ^
8(ao,
pq') (and \pq\
=
\pq'\), then
B
cannot
be
autonomous,
i.e.,
by
Proposition 4.18,
it is not
strongly connected,
a
contradiction.
Therefore,
for
every
prefix
p\ of pq,
S(CIQ,
p\) is not a
state
of B.
Suppose that, contrary
to our
assumptions,
S(OQ,
p\) — S( , p2)
holds
for
distinct
prefixes
p\ and p2 of pq and
put, say,
p\ =
pir\
(where
r1 X is
assumed).
In
other
words,
<5(flo,
P2r\)
=
8(ao,
p2)
holds such that
8
(a
0
,
pi) is not a
state
of B. But 8
(a
0
, pqx)
=
S(0o,
Pq'x'),
x, x' € X,
implies
that
there
exists
an r
2
€ X*
such that 8(ao, p^ri)
isastateof
B.
Clearly, then
A
satisfies either Letichevsky's criterion
or the
semi-Letichevsky criterion,
a
contradiction.
Finally,
(4) is a
direct consequence
of the
maximality
of
|#|(=
\q'\). This completes
the
proof.
Lemma
4.29.
Let A = (A, X, 8) be an
automaton without
any
Letichevsky
criteria.
Con-
sider
a
pair
a,ao
e A
of
states
and a
word
p e X*
with 8(ao,
p) = a and
suppose
that
8(a,
r) =
8(a,r')
holds
for
every
r, r' e
X*,\pr\
=
\pr'\
> \A\ - I.
Assume
that8(a,q)
/
8(a,q') holds
for
some
q, q' e
X*,\pq\
=
\pq'\
< \A\ - 1
and
let
q,q'
be
words
of
maximal length having this
property.
Then
there
exist
an
input
let-
ter
x,
words
u, v, v', w € X*, q =
uv,q'
=
uv',
v = xw
such that
for
every
non-
negative
integer
i <
\pu\,
there
are
<XQ
—
v\-powers
B = (B, X,
SB),
C = (C, X, 8c)
of
A
having states
bo e
B,CQ
€ C
such that
for
every
z, z' € X*
with
0 < |z| <
k'l
<
\P4\
~i we
have (8B(bo,z),8c(co,z))
^
(8B(bo,z'),8c(co,z')),
and,
moreover
4.2. Without
Any
Letichevsky Criteria
129
{(&B(bo,
z),
&C(CQ,
z))|z
€ X*, |z| < i},
{(S
B
(fco,
z),
<$c(c
0
,
z))|z
=
Zi*z
2
,
|zi|
= i,
|z
2
|
<
lM|-l}fllW/{(
B(b0,z),«c(Co,z))|z
€
X*,Z=ZlJC
;
Z2,|Zl|
= I, *' €
X,x' ^X,\Z
2
\
<
\pq\
—i}
arepairwise
disjoint
sets.
Proof.
Assume that
our
conditions hold.
Then there
are
q,q
f
,
u, v, v' e
X*with#
= uv, q' = uv'
(having
\q\ =
\q'\
< \A\
—
1)
such that
we
have properties
(l)-(4)
of
Lemma 4.28.
Consider
yi,...,
y\
pq
\,
y(
pu
|
+1
,...,
y'\
pq
\
e X
such that,
in
order,
p =
y
l
->
y\
p
\,
u =
y\
P
\+i
• - •
y\
P
u\,
v =
V|
pu
|
+
i
• - •
y
[pq
\,
v' =
y'
lpu
\
+l
• • •
y[
pqV
Moreover, consider words
p
k
, v
t
,
v'
t
e X*,
where,
in
order,
pk is a
prefix
of pu of
length
k, 0 < k <
\pu\,
v
t
is a
prefix
of v
of
length
£, and
vf
t
is a
prefix
of v' of
length
t, 0 < t <
\v\(=
\v'\).
Finally,
let y' e X be
an
arbitrary
fixed-input
letter.
By our
assumptions, without
any
contradiction,
we can
define
the
functions
<p\
: X ->
X,
<pj
: A x X -» X,
(f>\
: X -+ X,
<p'j
: A x X ->• X, j =
2,...,
\pu\
- i + 1,
having
the
following
properties.
For
every
d € A, y e Y,
Let
Moreover,
put
and
put
By
Proposition
4.16,
S(a
0
,
p')
{8(a0,
p"),
S(a
0
, puy\
pu
\+ir), S(a
0
, puy'
lpu]+l
r)
|
r
e X*}
holds
for
every pair
of
distinct prefixes
p', p" of pu. But
then,
of
course,
for
every
z, z' € X*
with
|z| <
\z'\
<
\pq\
— i, we
have
SC(CQ,
z) ^
&C(CQ,
z').
On the
other
hand,
by
Lemma 4.28,
we may
also assume
(a0, pur)
(a0, pur')
for all
prefixes
r
of
v and r' of v'
with
|r| =
\r'\
> 0.
Thus
SB&Q,
riy\
pu
\+ir2)
^
&B(bo,
r'^'r^),
x' e
X,x'
£
y|
p
«|
+
i,ri,r(,r
2
,
€
X*,
|n| =
|r{|
=
\pu\
- i,
\r
2
\
=
\r
2
\
<
\v\.
Therefore,
(&B(bo,
z),
5
c
(c
0
,
z)) 7^
(f>B(bo,
z'),
5
c
(c
0
,
z'))
if z and z' are
arbitrary words with
|z| <
130
Chapter
4.
Without
Letichevsky's
Criterion
Iz'l
<
\pqI
~i
26
or z =
riy\
pu
\
+
ir
2
,z
f
=
r[x'r^ wherex'
e
X,*'
Ji^i+i,
n, r[, r
2
, r^ €
27
Then
we
obtain that
for
every
z, z' e X*
with
\z\ <
\z'\
<
\pq\
we
have
(8&(bQ,
z),
8c(co,
z)) ^
(8
B
(bo, z'),
8
c
(c
0
,
z')),and,moreover, {(8
B
(b
0
,
z),
8
c
(c
0
,
z))|z
€ X*, \z\ < i},
{(<$B(fco,z),<$c(co,z))|z
=
Ziy|
p
«|+iZ2,
Izil
=
\pu\
-i,
\Z
2
\
< \q\ -
\u\]
and
{(8
B
(bo,
z),
8
c
(co,z))\z
€
X*,z
=
z\x'z2,
Izil
=
\pu\
-i,
\Z2\
< \q\ -
\u\,x'
e
X,x
f
^
V|
pK
|+i}are
pairwise disjoint
sets.
28
Thus
we
have
our
statement, assuming
x =
y\
pu
\+i-
D
Lemma
4.30.
Let A = (A, X, 5) be an
automaton without
any
Letichevsky criteria.
Suppose
that there
exist
a 6
A,xi,x
2
e X,
p,r,r'
6 X*
having
\r\ =
\r'\
such that
8(a,
px\z)
/
8(apx
2
z')for
every
nonempty
prefixes
z
ofr
andz' ofr' with
\z\ =
\z'\.
There
are
a
state
a' e A, an
input
letter
x € X, and
single-factor
products
B = (A, X,
8&),
C =
(A,X,8c)
of A
such that
for
every
z, z' e X*
with
\z\ <
\z'\
< \p\ + I we
have
(8
B
(a',z),8
c
(a
f
,z-))
£
(8
B
(a
f
,
z'),
8
c
(a
r
,
z'));
moreover,
{(8
B
(a',z),8
c
(a',z))\z
€ X*,
|z|
<
|p|},
{(*
B
(fl',z),«c(fl'
f
z))|z
=
Zi*z
2
,Zi,z
2
€
X*,\zi\
=
\pl\z
2
\
<
\r\]
and
{(&B(a
f
,
z),
8
c
(a',
z))|z
=
Zi^z
2
,
x' e X, x' £ x, zi, Z
2
6 X*,
|zi|
=
\p\, |z
2
|
<
|r'|}
are
pairwise
disjoint
sets.
Proof.
If
there
are
words
s,s'
e X,
\px\rs\
=
\px2r's'\
> \A\ — 1
with 8(a,
px\rs}
^
8(a,
pxir's'},
then
we
have
our
statement applying Lemma 4.27.
Thus
let
8(a,
px\rs)
=
8(a, px2r's'}
for all
words
s, s' X*,
\px\rs\
=
\pxir's'\
>
\A\-l.
Assume that, say, 8(a,
px\r}
is a
state
of a
strongly connected state-subautomaton
of
A. We
will prove that
in
this case,
8 (a,
px
2
r
r
)
is not a
state
of any
strongly connected state-
subautomaton
of A.
Indeed,
if 8 (a,
px
2
r')
is
also
a
state
of an
appropriate strongly connected
state-subautomaton
of A,
then
8 (a,
px\r}
and 5 (a,
px
2
r')
are
states
of
the
same strongly con-
nected state-subautomaton
of A
since 8(a,
px\rs)
=
8(a,
px
2
r's'),
s, s' e X*,
\px\rs\
=
\px
2
r's'\
| A|
—
1. But
then,
by
Proposition 4.19, 8(a,
px\r}
=
8(a,
px
2
r'),
a
contradic-
tion.
Therefore,
we may
suppose that, say,
5 (a, px\ r) is not a
state
of any
strongly connected
state-subautomaton
of A.
Now
we
consider (not necessarily nonempty) words
u,u',v,v'
with
r = uv, r' =
u'v', 8(a,
u) =
8(a,
u') and
suppose that
u and u' are
minimal
in the
sense that
for
every
prefix
u" of u and u'"
ofu', 8(a,
px\u"}
—
8(a, px
2
u'")
and
u"u'"
•£
X
implies
u" = u and
u'"
= u'.
Observe that
by our
conditions,
\u\ =
\u'\
is
impossible,
i.e.,
\u\ ^
\u'\.
Let v" be a
prefix
of v
with \v"\
=
\v'\
if |u| >
\v'\
and let v" = vz be for an
arbitrary word
z e X*
with
|uz|
=
|v'|if
|v| <
|i/|.
Now
we
prove that 8(a,
p\) ^
8(a,
p
2
} for all
nonempty prefixes
p\ of
px\uv
and
p
2
of
px
2
u'v"
with
\pi\
=
\p
2
\
>
\p\.
If v" = v',
then this statement
is
true because
of
the
conditions
of our
lemma. Thus
we may
assume
v" ^ v' and
max(|w|,
|w'|)
> 0. If
\P!\
=
\p
2
\
<
mm(\pxiu\,
\px
2
u'\),
then
we
have 8(a,
p\) ^
8(a,
p
2
) by our
conditions.
26
ThenSc(bo,z)^Sc(b
0
,z').
27
Then^(c
0
,z)^6
B
(co,z').
28
Clearly,
i = 0 is
possible
and
then
{(5s(i
0
,
z),
S
C
(CQ,
z))|z
e X*, |z| < i} = 0.