COMPLETENESS OF

CONDITIONS

WEAKLY A.

INITIAL Ao

MOORE

OF

SYSTEMS

AUTOMATA

Donis

UDC

519.95

In the theory of synthesis of automata, a special role is played by complete systems; in such a system, any automaton of a given class can be realized with the aid of assigned operations from automata belonging to the system. Therefore it is necessary to find (or to show that this is not feasible) an algorithm that ascertains the completeness of any finite system of automata. Among others, this problem is solved in [1-4] and [6-9], where a class of abstract automata is considered that can carry out the operations of direct product and feedback via logical units used in Moore automata. The most important results inthis respect are the conditions of homomorphic completeness of systems of noninitial Moore automata obtained by Letichevskii [7]. In the above-mentioned papers, a noninitial automaton is an automaton that can be set at the initial instant in any state; this is essential for obtaining the completeness conditions. On the other hand, a model that is m o r e appropriate for the majority of actual d i s c r e t e automata is a weakly initial automaton that can be set at the initial instant in any state belonging to a set of initial states, Initial and noninitial automata a r e p a r t i e u l a r c a s e s of this model. The completeness c r i t e r i o n of [7] is not sufficient for s y s t e m s of weakly initial automata. T h e r e f o r e it is n e c e s s a r y to find a completeness c r i t e r i o n for the general c a s e just mentioned. This is p r e c i s e l y the aim of this paper. In it we shall find effective n e c e s s a r y and sufficient conditions of i s o m o r p h i c and h o m o m o r p h i c completeness of s y s t e m s of weakly initial Moore automata. The conditions of i s o m o r p h i c completeness a r e s i m i l a r to the c o r r e s p o n d i n g conditions of Glushkov [2]. On the other hand the conditions of homomorphic completeness are much m o r e complicated than the conditions f o r m u l a t e d in [7]. In p a r t i c u l a r , it turns out that t h e r e exist complete s y s t e m s of a r b i t r a r y finite power, which is a r e s u l t analogous to T h e o r e m 6 of [5]. it was n e v e r t h e l e s s p o s sible to obtain these conditions in fairly simple f o r m and to a s c e r t a i n to s o m e extent t h e i r meaning. The c o m p l e t e n e s s conditions of [1-3] and [6-9] can be obtained f r o m our conditions as completeness conditions of p a r t i c u l a r s y s t e m s . The author e x p r e s s e s his gratitude to M. A. Spivak and A. A. Letichevskii for their interest~ 1o C o n d i t i o n s

of Isomorphic

Completeness

In this section we p r e s e n t an exact formulation of the completeness p r o b l e m and of the i s o m o r p h i c completeness theorem, and we establish the relationships between different types of c o m p l e t e n e s s . An automaton is defined as a s y s t e m (S, X, Y, 5, X, I), where S, X, and Y are nonempty finite sets of "states" and of "input signals" and "out-put signals," I is a nonempty set of "initial state," I C S , and 5 : S • X - - S and )t : S• X - - Y a r e "transition" and "output" functions. An automaton is said to be initial if I is a oneelement set, and noninitial if I= S. If the transition function does not depend on the input signal, the automaton will be called a Moore automaton, and its t r a n s i t i o n function will be called a " m a r k e r " function and denoted by # (# : S -* Y). The concepts not defined h e r e can be found in [10]. Let A and B be automata, A relation (unique relation, o n e - t o - o n e relation) ~ c SA• SB will be called a relation of equivalent (homomorphic, isomorphic) extension of an automaton B by an automaton A if XA = XB, YA = YB, and Pr2s = SB,

Translated Ii, 1971o

from Kibernetika,

No. 3, pp. 36-53, May-June,

(1.1)

1972.

Original article submitted

November

9 1974 Consultants Bureau, a division of Plenum Publishing Corporation, 227 g'est 17th Street, New York, N. Y. fOOl1. No part of this publication may be reproduced, stored in a retrieval system, or transmitted, in any form or by any means, electronic, mechanical, photocopying, microfilming, recording or otherwise, without written permission of the publisher. A copy of this article is available from the publisher for $15.00.

387

1t~ C ~ (IA),

(1o2)

(S~,S~)E ~ ---"(6A (S~,X), 58 (S2,X)) Ee, (SI, S2) ~t~ --~ ~A (SI' X) = ~,B (S2,X) ((Sp S2) ~..--->-~I,A(Sl) = ~LI. B ($2)),

(1.3) (1o4)

and w e s h a l l s a y t h a t t h e a u t o m a t o n A e q u i v a l e n t l y ( h o m o m o r p h i c a l l y , i s o m o r p h i c a l l y ) r e a l i z e s t h e a u t o m a t o n B. L e t X ~ b e t h e s e t o f a l l w o r d s in t h e a l p h a b e t X A i n c l u d i n g t h e e m p t y w o r d e, and l e t A b e an a u t o m aton. By 5A(S , p), w h e r e s 6 S A and p EX*A, w e s h a l l d e n o t e t h e s t a t e into w h i c h t h e a u t o m a t o n A g o e s o v e r f r o m the s t a t e s u n d e r t h e a c t i o n of an i n p u t w o r d p; h e r e hA(S, e) = s. By i n d u c t i o n on t h e length of t h e w o r d p w e c a n t h e n s h o w t h a t t h e c o n d i t i o n (1.3) i s t a n t a m o u n t to t h e f o l l o w i n g : (s,,s9

s--~(bA(s,P),

~(s2, p))E~

(1~

L e t us go o v e r to o p e r a t i o n s o v e r a u t o m a t a . L e t ~ : X • V ~ U and )~ : X • V -~ Y b e m a p p i n g s w h e r e U, V, X, and Y a r e n o n e m p t y f i n i t e s e t s ~ T h e u n i t r e a l i z i n g t h e m a p p i n g s ~ and • is d e f i n e d as a s y s t e m (U, V, X, Y, ~, X). If the m a p p i n g • d o e s not d e p e n d on s i g n a l s b e l o n g i n g to X, ioe~ i f X : V ~ Y, s u c h a u n i t w i l l b e c a l l e d a M o o r e u n i t . With e a c h m]it g we s h a l l a s s o c i a t e a o n e - p l a c e p a r t i a l o p e r a t i o n c a l l e d f e e d b a c k v i a t h e unit II and d e n o t e d by t h i s s a m e s y m b o l . By d e f i n i t i o n , t h e f e e d b a c k of an a u t o m a t o n A v i a a unit 7r i s defia]ed i f and o n l y i f A i s a M o o r e a u t o m a t o n and XA=UTr and YA=Vwo In t h i s c a s e t h e a u t o m a t o n r(A) is d e f i n e d a s f o l l o w s :

Yn(A) : Y.~, 6(A I (S,X) ---- 8 A (s, ~ ( x , ~tA (S))), ~A~ (S, X) = Z= (X. ~A (S)), (~A~ (S) = Z (~A (S))). T h e f e e d b a c k of t h e a u t o m a t o n A v i a t h e unit ~r c a n b e i n t e r p r e t e d a s c o n n e c t i n g to t h e a u t o m a t o n A d e v i c e s t h a t r e a l i z e t h e m a p p i n g s ~ and X~r ( F i g . 1)0

~

L e t us d e n o t e by ~A,Tr(s, p) a w o r d t h a t a r r i v e s at the input of an a u t o m a t o n A c o n n e c t e d with t h e unit ( F i g . 1) if t h e w o r d p a r r i v e s at t h e f r e e i n p u t of the unit ~97r and t h e a u t o m a t o n A is at t h e b e g i n n i n g of

o p e r a t i o n in t h e s t a t e s. T h e m a p p i n g ~bA,v : SA • X~r ~ X A is d e f i n e d r e e u r s i v e l y as f o l l o w s : ~4,~.~(s, e) - e,

~A,~ is, px) = ~ . = (s, p) %~(x, FA (6A (S, ~)A,~(S, p)))).

(1.6)

By i n d u c t i o n on t h e l e n g t h of the w o r d p i t i s e a s y to s h o w t h a t

5=~A;(s, p) = ~A (s, r

(s, p)).

(1.7)

A d i r e c t p r o d u c t o r ( m o r e b r i e f l y ) a p r o d u c t of two a u t o m a t a A and B i s an a u t o m a t o n A • B s u c h t h a t SA•215

XA•

la•

taxis,

XAXXB' YAxB=sYA•

6AXZ = 6A 1-16z,

~Ax~ = ~AIZI ~

T h e c o n c e p t of p r o d u c t c a n b e e a s i l y e x t e n d e d to t h e c a s e o f m o r e t h a n two c o f a c t o r s . A n a u t o m a t o n A t • . . . • A k c a n b e i n t e r p r e t e d a s j o i n t l y (in p a r a l l e l ) o p e r a t i n g a u t o m a t a A 1. . . . . . Ak. By i n d u c t i o n on t h e n u m b e r of o p e r a t i o n s u s e d in t h e d e s i g n of an a u t o m a t o n A, i t i s p o s s i b l e to p r o v e the following lemma: L E M M A 1. S u p p o s e t h a t an a u t o m a t o n A i s o b t a i n e d by f i n i t e l y m a n y p r o d u c t s and f e e d b a c k s f r o m Moore automata At ..... A k. T h e n t h e r e e x i s t s a unit r such t h a t A=~r (A 1 • ~ ~ . • Ak). A s y s t e m o f M o o r e a u t o m a t a is s a i d to be e q u i v a l e n t l y ( h o m o m o r p h i c a l l y , i s o m o r p h i c a l l y ) c o m p l e t e in a c l a s s i f f o r any g i v e n a u t o m a t o n of t h i s c l a s s it i s p o s s i b l e to d e s i g n f r o m t h e a u t o m a t a of t h i s s y s t e m ,

388

with the aid of finitely many products and feedbacks, an automaton that equivalently (homomorphically, isomorphically) realizes the given automaton~ An. automaton is said to be equivalently (ere.) universal in a class if it forms a system that is equivalently Fig~ i; Automaton

It(A).

(ere.) complete in this c l a s s . The next l e m m a a s s e r t s the transitivity of completeness. Its p r o o f can be found in [4] ( L e m m a 2)~

LEMMA 2. Suppose that a s y s t e m of Moore automata ~ is equivalently (homomorphically, isomorphically) complete in a class of Moore automata ~f and, on the other hand, let the s y s t e m 9A be equivalently (etc.) complete in a c l a s s ~ . Then the s y s t e m ~ will be equivalently (etco) complete in the c l a s s G o We shall c o n c e n t r a t e our attention on completeness in the c l a s s e s of initial, noninitial, and of all automata. Let us r e c a l l that a subset S of not less than two states of a Moore automaton A is called a subset with a complete s y s t e m of transitions and outputs if for all states s 1 and s2 belonging to S t h e r e exists an input signal x in XA such that 6A(Sl, x)= s 2 and all distinct states s 1 and s 2 in S satisfy the inequality THEOREM i~ F o r a s y s t e m of Moore automata to be i s o m o r p h i c a l l y complete in the class of initial (noninitial) automata, it is n e c e s s a r y and sufficient that it c o m p r i s e automata with a subset containing an init~.al state (containing not less than two initial states), and that it f o r m a complete s y s t e m of transitions and outputs. The p r o o f of this t h e o r e m is analogous to the p r o o f of T h e o r e m 39 of [1] and it can be found in [4] (Theorem It. By applying T h e o r e m 1 to the s y s t e m s of noninitial automata of Medvedev and Moore, it is possible to obtain the completeness conditions of [1] and [2]. Let us define two automata D and Do called noninitial and initial delay, by setting SD : ]D ~ XD =

YD =

{0,

| },

5 D ((Z, ~) ~ ~,

Do = (SD'XD' YD' 5D' ~D' {0}), F r o m T h e o r e m 1 we obtain L e m m a 3. LEMMA 3. A noninitial (initial) delay is an i s o m o r p h i c a l l y u n i v e r s a l automaton in the c l a s s of noninitial (initial) automata. A pair of subsets SO and Sl of states of a Moore automaton A is said to be connectable and distinguishable if t h e r e exist mappings ~ : {0, 1} x YA - - XA' • : YA ~ {0, 1}, such that s E S 0 U S, -+ G (s, m(a, ~ (st)) C S ,

(1.8)

s E S - . Z (~A (s)) = a.

(1,9)

It is easy to v e r i f y the validity of the following proposition which is analogous to T h e o r e m 4 of [7]o L_.E_EMMA4. Let So and S1 f o r m a connectable and distinguishable pair of subsets in a Moore automaton A (Moore automaton A0) and let

So~ IA4=O, Si ~ IA ,4=~

(So~ ]A=~).

Then the automaton ~r(A) [automaton MA0)], where 7r~ (XA, YA, {0, 1}, {0, 1}, r and (1.9), ~dll be a h o m o m o r p h i c extension of a noninitial (initial) delay.

(1.10) k), and q~ and X satisfy (1o87

Let us establish some relationships between different types of c o m p l e t e n e s s . THEOREM 2. Any s y s t e m that is equivalently (etc.) complete in a c l a s s of automata, will be equivalently (etc.) complete in the c l a s s e s of initial and noninitial automata. Any s y s t e m that is equivalently {etc.) complete in the class of noninitial automata, will be equivalently (etc.) complete in the class of all automata. P r o o f . The f i r s t a s s e r t i o n is evident. The second a s s e r t i o n follows f r o m the fact that if an automaton

389

A is equivalently tetc.) r e a l i z i n g a noninitial a u t o m a t o n iS, X, Y, 5, X, St, it will equivalently- (etc.) r e a I i z e an a u t o m a t o n (S, X, Y, 5. k, It. T H E O R E M 3. F o r a s y s t e m of M o o r e a u t o m a t a to be equivalently c o m p l e t e in a c l a s s of noninitial (initial) a u t o m a t a , it is n e c e s s a r y and sufficient that it be h o m o m o r p h i c a l l y c o m p l e t e in this c l a s s . P r o o L A noninitial (initial) delay f o r m s a h o m o m o r p h i c a l l y c o m p l e t e s y s t e m in the c o r r e s p o n d i n g c l a s s . It is e a s y to s e e that any r e l a t i o n of equivalent extension of delay is a r e l a t i o n of h o m o m o r p h i c extension. By v i r t u e of L e m m a 2, we h e n c e obtain the n e c e s s i t y of the conditions of the t h e o r e m . T h e i r sufficiency is evident. T H E O R E M 4. A s y s t e m of M o o r e a u t o m a t a is h o m o m o r p h i c a l l y c o m p l e t e in a c l a s s of noninitial a u t o m a t a if it is h o m o r p h i c a l l y c o m p l e t e in a c l a s s of initial a u t o m a t a and it contains an a u t o m a t o n with two differently labelled initial s t a t e s and c o n v e r s e l y . P r o o f . T h e n e c e s s i t y of the f i r s t condition is evident, w h e r e a s the n e c e s s i t y of the s e c o n d condition can be e a s i l y p r o v e d by a s s u m i n g the c o n t r a r y . C o n v e r s e l y : let a s y s t e m ~f be h o m o m o r p h i c a l l y c o m p l e t e in a c l a s s of initial a u t o m a t a and let it contain an a u t o m a t o n B with differently labelled initial s t a t e s s~ and s~. Let e be a r e l a t i o n of h o m o m o r p h i c extension of initial delay by an a u t o m a t o n A 0 obtained by finitely m a n y p r o d u c t s and feedbacks f r o m a u t o m a t a of the s y s t e m 9~ . Let us w r i t e S'0= # B PB(S0 ')' S~ = S B - S ' 0. We c o n s t r u c t an a u t o m a t o n A = A 0 x A0x B and s u b s e t s SO and S~ of its s t a t e s that will be defined a s follows: --I

--1

--1

--I

S,,=~(0)x~(0)xS~

Us(o0xs(~>

x S 8, ~ = o , t .

we seteet a s i s a l x' from XB and define the mappings r "{0, 1} • YA - - X A and X : ; A

{0, 1}, by

.setting q~ (~, (1~, 1', g')) = (~, 1, x'), Z (1~, "~, V') = a ~ [(13 = 0/',~ = 0 A y '

s

( S ~ ) ) V (1~ = ~/','~ = 1)1.

It is e a s y to s e e that the s u b s e t s SO and Si and the m a p p i n g s q~ and X s a t i s f y the conditions (1o8) and (1.9). Lete =0. Since

(So, So, S'~)~So, (So, So, S;) es,, (s0, s 0, so), (s0, s0, s[) E I A, it then follows that the s u b s e t s S O and S~ s a t i s f y also the condition (1o10). By v i r t u e of L e m m a s 4 and 2 we h e n c e obtain the a s s e r t i o n of the t h e o r e m . 2.

Conditions

of Homomorphic

Completeness

In this s e c t i o n we s h a l l i n t r o d u e e the c o n c e p t s in t e r m s of which the p r i n c i p a l t h e o r e m is f o r m u l a t e d , and we shall e s t a b l i s h t h e i r s i m p l e s t p r o p e r t i e s . An l - l e v e l of an a u t o m a t o n A is defined as the set of all s t a t e s r e a c h a b l e f r o m initial w o r d s of length l; it will be denoted by SA(I), i.e., SA(1 ) =SA(IA, XZAt, w h e r e X / is a set of w o r d s of length l in the alphabet X A. It is evident that a s e q u e n c e of l - l e v e l s SA(0), SA(1) , SA(2 t . . . . of an a u t o m a t o n is p e r i o d i c beginning with s o m e l . By NA and M A we s h a l l denote the p e r i o d and p r e p e r i o d of this s e q u e n c e . Let 9[ be a finite s y s t e m of a u t o m a t a . By N~ and M~ we shall denote the l e a s t c o m m o n multiple of all the n u m b e r s NA, A E~I, and the m a x i m u m of the n u m b e r s M A, A E ~ .

From

t h e s e definitions follows L e m m a 5. LEMMA 5. Let

~

be a finite s y s t e m of a u t o m a t a and let the n u m b e r s i and j b e s u c h that i, ] ~ M ~

and i-~-j {modN~) . T h e n the i - t h and the j - t h levels Of any a u t o m a t o n A belonging to ~I

will coincide.

Next, it is e a s y to s e e that SA,x ..XA~(l) = Sa, (/) X . . . X SAk(l),

(2.1)

w h e n c e follows L e m m a 6. LEMMA 6. L e t 9d be a finite s y s t e m of a u t o m a t a and let A be a p r o d u c t of a u t o m a t a belonging to tt . Then M A~
390

L e t us n o t e t h e p r o p e r t i e s of t h e n u m b e r s N2 LEM1V~. 7. If ~I Proof.

i s a f i n i t e s y s t e m of n o n i n i t i a l a u t o m a t a , t h e n

Let A be a noninitial automaton.

SA(O)~ S A ( 1 ) ~ S A ( 2 ) ~ . . -

for particular systems

~.

N~ = 1.

S i n c e SA(0) = I A = SA and 5A(SA, X A) c SA, i t f o l l o w s t h a t

. H e n c e we find t h a t SA(I + I ) = S A ( I ) f o r s o m e l .

Hence NA=I , which completes

the proof.

XA~

W e st{all say that an automaton A has a loop in the state s if 5A(S,X) = s for a signal x belonging to The following l e m m a ean be proved in a similar way as the previous lemma:

L E M M A 8~ If

0/

i s a f i n i t e s y s t e m o f a u t o m a t a with l o o p s in t h e i n i t i a l s t a t e s , t h e n N,2~= 1.

Two input s i g n a l s x 0 and xi of a M o o r e a u t o m a t o n A a r e s a i d to b e b r a n c h i n g a s t a t e s b e l o n g i n g to S A if

~A (~A (S, X0)) ~ ~A ({~A(S, XI)). T h e s t a t e s i s c a l l e d a b r a n c h e d s t a t e . By l (p) we s h a l l d e n o t e t h e l e n g t h o f t h e w o r d p, and by (P)i t h e i - t h s y m b o l of t h e w o r d p. Next w e s h a l l d e n o t e by p r e f i P an i n i t i a l s e c t i o n o f l e n g t h i of t h e w o r d p, and by sufiP a f i n a l s e c t i o n o f t h i s w o r d s u c h t h a t p = prei~ p. suf~ p,

0 ~ i ~ l (p).

Two i n p u t w o r d s P0 and Pl of a M o o r e a u t o m a t o n A a r e s a i d to b e s e p a r a t i n g a s t a t e s b e l o n g i n g to SA if t h e y s a t i s f y t h e c o n d i t i o n s

~'tA(6A (S, pref I Po)) =# l~A(6A (s, pref I Pl)),

(2.2)

6 A (s, Pa) = s.

(2o3)

T h e s t a t e s i s c a l l e d a s e p a r a b l e s t a t e . L e t us n o t e t h a t if s i s a s e p a r a b l e s t a t e , t h e r e e x i s t w o r d s of e q u a l l e n g t h s e p a r a t i n g it. It is e v i d e n t t h a t t h e r e e x i s t s an a l g o r i t h m t h a t r e c o g n i z e s w h e t h e r a s t a t e o f a M o o r e automaton is separable. Let us also note the following assertion: L E M M A 9. If s i s a s e p a r a b l e s t a t e of a n o n i n i t i a l M o o r e a u t o m a t o n A, t h e n S 6 S A ( / ) f o r any l . P r o o f ~ If P0 i s a s e p a r a t i n g w o r d o f t h e s t a t e s, t h e n 6 A(6d (s, prei~P0), s u f (p~)) = s f o r any u = 0 . . . . . l (P0) and v > 0. In t h i s e a s e s ffSA6 ( v . l (p0)-u), s i n c e 5A(S , pref~P0)61A = SA. H e n c e follows the assertion of the lemma. A s t a t e s of a M o o r e a u t o m a t o n A i s s a i d to be r e g u l a r l y r e a c h a b l e f r o m t h e s t a t e s s o and s 1 by w o r d s P0 and Pl o f e q u a l length i f 8 A ( s ~ , p ~) = s,

~a (64 (So'prei~P0)) = ~A (SA (Sl' prefj Pl)) -~ (P0)i+l : f o r any j =0 . . . . .

l (p0)--l.

(Pl)i+l

L e t us p r o v e t h e f o l l o w i n g 1 e m m a :

L E M M A 10. S u p p o s e t h a t a s t a t e s of a M o o r e a u t o m a t o n A is r e g u l a r l y r e a c h a b l e f r o m the s t a t e s s o and s l . T h e n i t w i l l b e r e a c h a b l e f r o m t h e m with t h e a i d of w o r d s of l e n g t h not e x c e e d i n g t h e n u m b e r

ISA 12. Proof. ditions.

S u p p o s e t h a t t h e s t a t e s So, s l , and s, and t h e w o r d s P0 and Pl of l e n g t h I s a t i s f y t h e a b o v e c o n -

L e t us c o n s t r u c t a s e q u e n c e

|

,, |

of p a i r s of s t a t e s b e l o n g i n g to SA, w h e r e

~ i : (6A(S(~,prefiPo),

6A (sl,pre[iPl)),

]=0 ..... l--1. T h e n u m b e r of a l l p a i r s of s t a t e s of t h e s e t SA is e q u a l to IS A 12. F o r l > [SA 12 t h e r e e x i s t in t h i s c a s e two n u m b e r s u a n d v s u c h t h a t 0 - u < v < I and 5A (sa, pref~Pa) : 6 A (Sa, pref~Pa).

391

f

We shall define the w o r d s p~ and pl, by s e t t i n g Pc~ =prefuPc~ • SUfvP(~' c~ =0, 1. A d i r e c t v e r i f i c a t i o n shows t h a t the s t a t e s is r e g u l a r l y r e a c h a b l e f r o m the s t a t e s s o and s t with the aid of w o r d s P~0 and p~ o f length l - V + u. The d e s c r i b e d p r o c e s s of r e d u c t i o n of the length of w o r d s can be continued u n t i l t h e y b e c o m e s m a l l e r than the n u m b e r [ SAI 2. This c o m p l e t e s the p r o o f of the l e m m a . A s t a t e s of a M o o r e a u t o m a t o n A is said to be r e g u l a r if t h e r e exist t r a n s i t i o n s f r o m it to differently labelled s t a t e s f r o m which s is r e g u l a r l y r e a c h a b l e with the aid of c e r t a i n w o r d s , i.e., t h e r e exist w o r d s P0 and Pi of equal length that s a t i s f y the conditions (2.2)-(2.3) and the i m p l i c a t i o n ~,~ (5 A(s, prefipo)) = ~A (6A(S, prdpl)) -~ (P0)i+l = (Pl)j+~ for any j = l . . . . .

/(p0)--l.

(2.4)

All such w o r d s a r e said to be r e g u l a r l y s e p a r a t i n g f o r a s t a t e so

Let us p r o v e the following a s s e r t i o n : LEMMA 11. Any s e p a r a b l e state of an a u t o m a t o n with a o n e - t o - o n e m a r k e r function is r e g u l a r . P r o o f . F o r s e p a r a t i n g w o r d s P0 and Pi of the state s of an a u t o m a t o n A with a o n e - t o - o n e m a r k e r h m c t i o n we shall denote by c the s m a l l e s t of the n u m b e r s j =2 . . . . . l (P0) for which 5A (s, preii P0) = hA (S, prefi Pc). Let us c o n s t r u c t the w o r d P2 = p r e f c P i " SufcPoo It is e a s y to s e e that the w o r d s Po and P2 a r e r e g n l a r l y s e p a r a t i n g the s t a t e s. This c o m p l e t e s the p r o o f of the l e m m a . LEMMA 12. Any s e p a r a b l e s t a t e of an a u t o m a t o n with loops in each state is r e g u l a r ~ Proof.

If Po and Pl a r e s e p a r a t i n g w o r d s of the state s of an a u t o m a t o n A that has loops in each state,

then b~A(S) q= btA(8A (S, preflp~)) for c~ = 0 or oz = 1. Let the input signals x and xc~ be such that 5d (s, x) = s,

6 A (5A (s, preflp~), X~)=hA(S, pre[~ p~).

Then it is e a s y to s e e that the input w o r d s p~ = xpa and PlT = p r e f i P ~ "xc~ "suf~Pc~' w h e r e ~ s a t i s f i e s the above inequality, a r e r e g u l a r l y s e p a r a t i n g w o r d s f o r the state s. This c o m p l e t e s the p r o o f of the lemmao Input w o r d s P0 and Pi of lengtb not s m a l l e r than n, n > 0 , a r e said to be n - d i s t i n g n i s h i n g for a s t a t e s of a M o o r e a u t o m a t o n A if they s a t i s f y the condition (2.3) and also if f o r s o m e i n t e g e r I > 0 the following conditions hold: FA (hA (S, preil(~_ipo)) ~= ~A (6A (S, prefb(p,l_ipl) )

(2.5)

for any i = / , . . o, l + n - - 1 and

FA (SA (S, pre[z(po)_/po) ) = ~A (6A (S, prefl(p,)_,p~))

-->-

(Po)t(p.)-i+~

=

(P,)l(,,)-i+~

(2oG)

for any j =1 . . . . . I . H e r e the s t a t e s is said to be n - d i s t i n g n i s h a b l e , and the s m a l l e s t of the n u m b e r s I that s a t i s f y for s o m e w o r d s P0 and pI the conditions (2.3) and (2.5)-(2.6) is c a l l e d the weight of the s t a t e s. It follows d i r e c t l y f r o m the definition that any r e g u l a r s t a t e is 1 - d i s t i n g u i s h a b l e . It is e a s y to s e e that if the w o r d s P0 and Pt s a t i s f y for s o m e I the conditions (2.3) and (2.5)-(2.6), t h e s e conditions will be also s a t i s f i e d (for the s a m e l) by w o r d s p~ =P0 "Pt and P~=Pl "P0 of equal length. H e n c e i f s i s a n n - d i s t i n g u i s h a b l e state, t h e r e exist w o r d s of equal length that a r e n - d i s t i n g u i s h i n g for it. In the s a m e way it is e a s y to s e e that if w o r d s P0 and Pl of equal length s a t i s f y for s o m e l the conditions (2.3) and (2.5)(2.6), then for l' =l + r . l (P0) t h e s e conditions will be also s a t i s f i e d by the w o r d s p~ =Pl "P~ and p ~ = p r + i f o r a n y r > 0o 0 It follows f r o m t h e conditions (2.3) and (2.4) that the state s is r e g u l a r l y r e a c h a b l e f r o m the s t a t e s 5A (s, p'~), w h e r e p ~ = prefa~)_lp~, with the aid of w o r d s p~ = suf,p~)_~p~, ~ = 0,1o It t h e n follows f r o m L e m m a 10 that the w o r d s Pa can be s e l e c t e d in such a way that l (p~) -< 1SAI 2

Let us also note that the

w o r d s p~ can be s e l e c t e d in such a way that 1 (p~) -
392

If Pl, . . . . Pk a r e w o r d s of l e n g t h n in t h e a l p h a b e t s X 1. . . . . Xk, we s h a l l d e n o t e by p t ~ . . " ~ P k t h e c o n v o l u t i o n of t h e s e w o r d s , i . e , , a w o r d in t h e a l p h a b e t X 1 • . . ~ x Xk, s u c h t h a t (p, I-!.-.I-I

p~)z = ((p,l~ .....

(p~)~),

i = 1 .....

n.

C o n v e r s e l y , if p i s a w o r d in t h e a l p h a b e t X 1 x ~ ~ , x Xk, w e s h a l l d e n o t e by p r l p . . . . .

PrkP words such that

p = pr, P l Z I . - - I Z I p r ~ p . We s h a l l a l s o a d o p t t h e f o l l o w i n g n o t a t i o n : P r i ( a 1. . . . .

ak) = a i , i -<-i -< k.

L E M M A 13. S u p p o s e t h a t a M o o r e a u t o m a t o n A t x . . o x A k c o n t a i n s an n - d i s t i n g u i s h a b l e s t a t e t h a t i s r e a c h a b l e f r o m an i n i t i a l s t a t e . F o r an h, 1 -< h -< k, t h e a u t o m a t o n A h w i l l c o n t a i n in t h i s c a s e a 1 - d i s t i n g u i s h a b l e s t a t e t h a t i s r e a c h a b l e f r o m an i n i t i a l s t a t e . P r o o f . If P0 and Pl a r e n - d i s t i n g u i s h i n g w o r d s of t h e s t a t e s of t h e a u t o m a t o n A = A t x . . . x Ak, w e s h a l l d e n o t e by l ' t h e s m a l l e s t o f t h e n u m b e r s j = 1 . . . . . l f o r w h i c h t h e p r e m i s e o f t h e i m p l i c a t i o n (2.65 i s f a l s e . T h e n t h e r e e x i s t s an h, 1 - < h - k , s u c h t h a t ~h (8~ (prh s, preit(Oo)_e pr,, Po)) 4~ ~ (5~ (prh s, pretl(p,)_e 9prhp I)), w h e r e # h and 6 h a r e t h e t r a n s i t i o n f u n c t i o n and t h e o u t p u t f u n c t i o n of t h e a u t o m a t o n Ah~ It i s e v i d e n t t h a t in t h i s c a s e (Prh Po)t(Do)-:+I = (pr~ Pl)l~p,l-j-+~ f o r any j =1 . . . . .

l' and 6~ (prh s, prhp.) = prhs

H e n c e PrhS w i l l b e a l - d i s t i n g u i s h a b l e s t a t e in the a u t o m a t o n A h. It i s r e a c h a b l e f r o m an i n i t i a l s t a t e i f t h i s i s t h e c a s e f o r a s t a t e s in t h e a u t o m a t o n A . T h i s c o m p l e t e s t h e p r o o f of t h e l e m m a . L E M M A 14. S u p p o s e t h a t an a u t o m a t o n A c o n t a i n s an n - d i s t i n g u i s h a b l e s t a t e t h a t i s r e a c h a b l e f r o m an i n i t i a l s t a t e . T h e n a n y o f i t s i - l e v e l s , w h e r e i-> MA, w i l l c o n t a i n an n - d i s t i n g u i s h a b l e s t a t e r e a c h a b l e f r o m an i n i t i a l s t a t e . Proof.

If P0 a n d Pl a r e w o r d s t h a t a r e n - d i s t i n g u i s h i n g f o r a s t a t e s o f the a u t o m a t o n A, i t i s e a s y

to s e e t h a t t h e w o r d s p~ = SUfuP 0 ~

"prefuP0, w h e r e 0 < u < l (P0), c~ = 0, 1, w i l l b e n - d i s t i n g u i s h i n g f o r t h e

s t a t e s ' = 5 A(S, p r e f u P 0) [the c o n d i t i o n s (2.5) and (2.6) a r e s a t i s f i e d f o r t h e m f o r l' =l + u]. H e n c e if s~ SA(h5 , t h e n s' E SA(h+ u + v 9 l (P0)) in a c c o r d a n c e with (2.3). By v i r t u e of L e m m a 5 w e h e n c e o b t a i n t h e a s s e r t i o n of of t h e l e m m a , tf t h e w o r d s P0 a n d Pl s a t i s f y (2.3) and (2.5) and if

(Po)~po~-i+1 = (POm,,~-i+l

(2~

f o r any j = 1, . . ~ l , we s h a l l s a y t h a t t h e y a r e c o r r e c t l y n - d i s t i n g u i s h i n g f o r a s t a t e s, and t h e s t a t e s is s a i d to b e c o r r e c t l y n - d i s t i n g u i s h a b l e . It i s e v i d e n t t h a t a c o r r e c t l y n - d i s t i n g u i s h a b l e s t a t e i s a l s o n - d i s tinguishable. L E M M A 15. L e t A=~r(B). T h e n if s i s a c o r r e c t l y n - d i s t i n g u i s h a b l e s t a t e of the a u t o m a t o n A, i t w i l l b e a l s o an n - d i s t i n g u i s h a b l e s t a t e o f t h e a u t o m a t o n B. P r o o f . S u p p o s e t h a t t h e input w o r d s P0 and Pt o f t h e a u t o m a t o n A s a t i s f y f o r s o m e l t h e c o n d i t i o n s (2.35, (2,55, and (2.75. L e t us w r i t e p ~ = r ~ (s, p ~ ) , c~ =0, 1 , w h e r e t h e m a p p i n g eB, 7r i s d e f i n e d in (t,65. F r o m t h i s r e l a t i o n and f r o m (1.6) w e o b t a i n prefkP~ = ~z~ (S, prefkp~),

(Ps f o r arty k = l ~ , . . ,

l (pa).

= q)~ ((Pa)k+i, ~tB (SB (S, pref~p~)))

By u s i n g (1o7) and t h e s e f o r m u l a s , it i s e a s y to s e e t h a t t h e i n p u t w o r d s p~ and

p] of t h e a u t o m a t o n B s a t i s f y f o r t h i s s a m e l t h e c o n d i t i o n s (2.3) and (2.5)-(2.6), w h e n c e w e o b t a i n t h e a s s e r tion of the lemma.

393

Let

9! be a finite s y s t e m of a u t o m a t a .

By Q~[ we shall denote a n u m b e r defined by the follov/mg

recursive scheme: Q~A~= IS~ 12, O~u~ ~ = { s + I S~ 12, otherwise.

~f A ~ ,

Now we can f o r m u l a t e the n~xt t h e o r e m . T H E O R E M 5. F o r a s y s t e m of M o o r e a u t o m a t a to be h o m o m o r p h i c a l l y c o m p l e t e in a c l a s s of initial a u t o m a t a , it is n e c e s s a r y and sufficient that a finite s u b s y s t e m 92 of this s y s t e m s a t i s f y the following c o n ditions: 1. F o r any i = 0,1 . . . . .

M ~ - - 1 t h e r e exists an a u t o m a t o n in g[

w h o s e i - l e v e l contains a b r a n c h e d

state. 2. F o r any i = M~, ..., M~ -I- N~ - - 1

t h e r e e x i s t s an a u t o m a t o n in

9/ w h o s e i - l e v e l c o n t a i n s a

s e p a r a b l e state. 3. T h e r e exists a p r o d u c t of not m o r e than N,)~ + 2Q~ a u t o m a t a in 9/

that contains an N~j - d i s t i n -

g u i s h a b l e state r e a c h a b l e f r o m an initial state. It is evident that the a b o v e - f o r m u I a t e d c o m p l e t e n e s s conditions hold f o r finite s y s t e m s . On the o t h e r hand it is difficult to v e r i f y in p r a c t i c e the condition 3. The above e s t i m a t e of the n u m b e r of c o f a c t o r s i s quite o v e r r a t e d . H o w e v e r f o r actual s y s t e m s , in p a r t i c u l a r f o r the s y s t e m s c o n s i d e r e d in Section 6, the condition 3 needs v e r i f i c a t i o n only for p r o d u c t s c o n s i s t i n g of one c o f a c t o r (if at all). 3.

Necessity

of Conditions

of Homomorphic

Completeness

This p r o o f u s e s the ideas of [6] and it e o n s i s t s of the following: A s e t c o n s i s t i n g of an a u t o m a t o n a s s e m b l e d f r o m a u t o m a t a of a s y s t e m and r e a l i z i n g an initiM delay wilI s a t i s f y the conditions 1-3 of T h e o r e m 5. It then follows that the set of a u t o m a t a u s e d in the s y n t h e s i s of such an a u t o m a t o n will s a t i s f y the f i r s t two conditions and also t h e t h i r d condition, but without limitation on the n u m b e r of f a c t o r s of the p r o d u c t . H o w e v e r , l a t e r on it is e s t a b l i s h e d that condition 3 is s a t i s f i e d also by a p r o d u c t o f t h e s e a u t o m ata h a v i n g the n u m b e r of f a c t o r s listed above. Suppose that a s y s t e m of M o o r e a u t o m a t a is h o m o m o r p h i c a l l y c o m p l e t e in a c l a s s of initial a u t o m a t a and that ~ is a r e l a t i o n of h o m o m o r p h i c extension of an initial delay D O by an a u t o m a t o n A a s s e m b l e d f r o m automata Al ..... A k of the s y s t e m u n d e r c o n s i d e r a t i o n with the aid of finitely m a n y p r o d u c t s and f e e d b a c k s . In a c c o r d a n c e with L e m m a 1 we have A=Tr(A 1 x . . . x Ak) for a M o o r e unit ~r. Let us w r i t e 92 = { A t ..... Ak}. By s o we shall denote an initial s t a t e of an a u t o m a t o n A that is equivalent to the state 0 of an initial delay, i.e., e(s0) = 0, s0E I A . Let us a s s i g n a w o r d p in the alphabet XA = {0, 1}. In a c c o r d a n c e with (1.6) we find that the state 5A(S 0, p) is equivalent to the s t a t e 5D(0 , p). It is e a s y to s e e that any delay state is a b r a n c h e d state. H e n c e foIlows that the state 5A(S 0, p) is also b r a n c h e d . It is evident that it beIongs to an l (p)-level of the a u t o m a t o n A. Next, f r o m the fact that the state 5A(S 0, p) is b r a n c h e d in the a u t o m a t o n A, it follows that it is also b r a n c h e d in the a u t o m a t o n B = A l x . . . XAk, s i n c e A=Tr(B)o H e r e it is evident that 5A(S 0, p) E SB(/(p)). Next it is e a s y to s e e that f o r a j, 1-< j-< k, the s t a t e prjSA(S0, p) is b r a n c h e d i ~ the a u t o m a t o n A~ E ~ .

A c c o r d i n g to (2.1) we then h a v e p r j 5A(S0, p)E SAj(/(p))o Since the w o r d p has been

a r b i t r a r i l y selected, we h e n c e obtain the condition 1 of T h e o r e m 5. L e t S o be a s e t of s t a t e s of the a u t o m a t o n A g e n e r a t e d by the s t a t e s So, Joe., S O= 6A(S0, X'A). It is evident that SO is a n o n e m p t y stable set. By S we shall denote a m i n i m a l n o n e m p t y s t a b l e s u b s e t of the set S 0. It is evident that 5A(S0, p) ES for a p E X *A. Let us take a w o r d q such that l(pq) ~ N ~ o It is e a s y to s e e t h a t 5A(S0, pq) is a b r a n c h e d state of the a u t o m a t o n A and that 0 and 1 a r e s i g n a l s which a r e b r a n c h i n g this state. It follows f r o m T h e o r e m s 6.4, 6.5, and 6.6 of [10] that the set S is s t r o n g l y c o n n e c t e d . In this c a s e we have f o r input w o r d s P0 and Pl of the a u t o m a t o n A the r e l a t i o n f3A (So, pq~zp~) = 5 A (so, pq).

Hence foilows that the w o r d s 0 . P0 and 1 . p t s e p a r a t e the state 6A(S0, pq), and h e n c e the s t a t e 5A(S0~ pq) is s e p a r a b l e in the a u t o m a t o n A. It is evident that 5A(S 0, pq) E SA(/(pq)). By r e a s o n i n g in the s a m e way as in

394

the proof of condition I, we find that for a j, 1-< j-
with Lemma

5 the eonditi0n 2 of Theorem

5.

Let us show that the system ~ satisfies the condition 3'. There exists a product of automata ing to 91 that contains an N~-distinguishable state that is reachable from an initial state. For this purpose is reachable

from

let us find in the subset S defined above a correctly

an initial state.

i=0, I, . o o~ where

the word

pis

Let us consider such thatbA(S0,

a sequence p)~So

N~-distinguishable

of states of the automaton

belong-

state s that

A : 6A(S 0, p 9 li),

Then

6 A (So, p 91~) = 5A(s0, p. 1")

(3.1)

for n u m b e r s b >a -> 0. By a s i m i l a r e x a m i n a t i o n of the s e q u e n c e 5A(S0, p ~ i a o0 i) i =0, 1 . . . . . t h e r e e x i s t n u m b e r s d > c >- 0 s a t i s f y i n g the r e l a t i o n

we find that

6A (S0, P" [~ "0d) = 5A(S0, P" t~'0~). L e t us d e t e r m i n e two n u m b e r s u and v such t h a t a - < u < b , c - v < d , u -F N ~ = a -F f ( b - - a),

for numbers

(3.2)

and (3.3)

v 4- N ~ = g ( d --- c)

f , g -> 0. Since the s e t S i s s t r o n g l y c o n n e c t e d , t h e r e e x i s t w o r d s q0 and ql i n X*A s u c h t h a t 5A (s0, p. 1"- ft. q0) = 5A (So, P" 1~. 0~). 5A (So,P" 1~'0~'ql) = 5A (S0' P" 1~)"

With the aid of the formulas the set S, the words

(3~4)

(3.1)-(3o4) it is easy to see that the state

P0 =q0 "0N~+c, P~ ~ q~~ IN~'OC , and the numbers

I =c,

s = 8 A (so,p. F.0$

n =N~

satisfy the conditions

(2.5), and (2.7)~ Hence s will be a correctly N~-disting~ishable Lemma 15 we hence obtain the assertion 3'0

state of the automaton

For completing two propositions:

of Theorem

the proof of the necessity

of the conditions

belonging to

A.

(2o3),

By virtue of

5, let us formulate

the following

LEMMA 16. Suppose that the product A i• o . . x A k of Moore automata contains an n-distinguishable state that is reachable from an initial state. Then there exists a product of automata belonging to the system {A i ..... Ak} that contains an n-distinguishable state which is reachable from a_n initial state and has a weight not exceeding the number 2Q{A i ..... Ak}o LEMMA 17. Suppose that a product A i • . . . x A k of Moore automata contains an n-distinguishable state of weight I that is reachable from an initial state. Then there exists a product of not more than I +n automata of the system {A i ..... Ak} that contains an n-distinguishable state which is reachable from an initial state. These

propositions

show

at once that the conditions 3 and 3' are equivalent.

Proof of Lemma 16. Suppose that the conditions of the lemma are satisfied. Let us write ~ = {A I ..... A~}., and consider the case that the weight of the investigated n-distinguishable state is larger than the number 2Q~ . Let u s c o n s t r u c t a r e c u r s i v e s e q u e n c e of M o o r e a t t t o m a t a t h a t s a t i s f i e s t h e following c o n d i t i o n s : 1. Any a u t o m a t o n of t h i s s e q u e n c e is a p r o d u c t of a u t o m a t a b e l o n g i n g to the s y s t e m 9I. 2. A 1 x o . o x A k is the f i r s t a u t o m a t o n of this s e q u e n c e . 3. If i n an a u t o m a t o n A of this s e q u e n c e the weight l of m~ n - d i s t i n g u i s h a b l e s t a t e s r e a c h a b l e f r o m an i n i t i a l s t a r e i s l a r g e r t h a n 2Q~ , t h e n the nex~ a u t o m a t o n A' w i l l have a n n - d i s t i n g u i s h a b l e s t a t e s' that is r e a c h a b l e f r o m a n i n i t i a l s t a t e and has a Weight l ' such t h a t l ' < l . It is e v i d e n t t h a t the a s s e r t i o n of t h e l e m m a follows d i r e c t l y f r o m t h e e x i s t e n c e of this s e q u e n c e . Let us show how it is p o s s i b l e to s a t i s f y the c o n d i t i o n 3. L e t s be ml n - d i s t i n g u i s h a b l e s t a t e of the a u t o m a t o n A t h a t is r e a c h a b l e f r o m a n i n i t i a l s t a t e . By P0 and Pi we s h a l l denote t h e i n p u t w o r d s of the

395

a u t o m a t o n A t h a t s a t i s f y t h e c o n d i t i o n s (2.3) a n d ( 2 . 5 ) - ( 2 . 6 ) f o r a n u m b e r ! e q u a l to t h e w e i g h t of t h e s t a t e s, W e h a v e n o t e d a b o v e t h a t t h e y c a n b e s e l e c t e d i n s u c h a w a y t h a t l (P0) = l (Pl)- L e t u s d e n o t e t h e i r l e n g t h by d. L e t r b e t h e n u m b e r o f c o m p o n e n t s of t h e a u t o m a t o n A . W e s h a l l w r i t e

U {(pr~s',prJ, pr,A)}.

| ~1

It i s e a s y t o

see that

]| ] = Q~.

s',s"ES 4

Let us construct

subsets

Se_~+~ . . . . . |

of t h e s e t |

that are defined

as f o l l o w s : ~t = {(Pr16A (s, preftp0), pr15 A (s, preftpl), pqA) . . . . . (pr 6A (s, preffl0), pr,6 A (s, preftpl), pr,A)}, t =d--I

- - 1 . . . . . d.

S i n c e t h e n u m b e r of d i s t i n c t n o n e m p t y s u b s e t s of the s e t i n e q u a l i t y l > 2 Qe

that

definition of the sets such that

|

|

~

is smaller

t h a n 2 lel , i t f o l l o w s f r o m t h e

= | f o r u and v s u c h t h a t d - l < u < v -< d. F r o m t h i s r e l a t i o n a n d f r o m t h e w e find t h a t f o r any z = 1 . . . . , r t h e r e e x i s t s a n u m b e r a b e l o n g i n g to {1 . . . . , r}

(3.5)

P@A (S, pref.p.) = pr 5 A (s, pref~p.), prA = prA, and a l s o t h a t f o r any z = 1, . . :, r t h e r e e x i s t s a n u m b e r b b e l o n g i n g to {1, . . . .

r} s u c h t h a t

p r 6 a (s, pref~p~) = pr~6 A (s, pref.pa).

(3.6)

p r A = prbA. F o r any z l e t u s a s s i g n two n u m b e r s

a a n d b w h i c h a r e d e n o t e d by a ( z ) and b(z)~

T h e a u t o m a t o n A' , i t s s t a t e s ' , and t h e i n p u t w o r d s P0' and p~ w i l t b e d e f i n e d a s f o t l o w s : A' = p r ( ~ ) A • 2 1 5 2 1 5 2 1 5 2 1 5 s' -~ ~pr( l)s . . . . . pr (,)s, prls . . . . . prfi), p~ = preff . s u f g ~ . p r e f g . s u f j , , where we used the notation f~ = p r m p , [ ] . . .

[ ] p r ( , ) p ~ [] prlp ~ [ ] . . . [2]prp~,

g~ = pr~pa [ ] . . . prrp a [] prb(~)pa ~ . . . ce = 0, 1. It is e a s y to s e e t h a t A' = A x A and 1 (p~) = 2d. for z=l ....

, r, fl=O, 1, a n d h = 2 d - l ' - n ,

....

2d.

D Prb(,)Pa,

L e t us w r i t e l ' = l - v

+ u and f i n d pr~+~6A, (s',prefhps

L e t u s c o n s i d e r two e a s e s .

1. 2 d - l ' - n -< h -< d + v . It is e v i d e n t t h a t in t h i s c a s e w e h a v e d - l - n t d e f i n i t i o n of t h e s t a t e s' and of the w o r d s Pc~ w e t h e n o b t a i n

<- h - v - d + u - <

u.

F r o m the

pr~6A, (s', prefhp~) = 6p~A' (prfi', pr prefhp~) =6p~A (pr ~)s, p r e f ~ p r ] , s u f p r g , .prefh_o_d+" pr,g~), By u s i n g t h e d e f i n i t i o n of the w o r d s f o , f l and g0, g~, and t h e f o r m u l a s

( 3 . 5 ) - ( 3 . 6 ) , we o b t a i n

prz6A, (s', prefhp~)= P@A (S, prefa_o_~+,p,)

(3.7)

prz+,6 A, (s', prefhps = pra(~)6A(s,preih_v_a+~fl~).

(3,8)

and similarly

2. d + v -< h-<2d.

In t h i s c a s e 0 -< h - v - d - <

d-v

and v-< h - d - < d. A s i n c a s e t , we t h e n o b t a i n

prz5A, (s', prefhp~) = 6vz A (pr~(z)s, pref~prz/~ 9suf~pr g . prefuprfla 9prefh_~= a (sufvpr]~)), w h e n c e we o b t a i n w i t h t h e a i d o f (3.5) and (306) t h e f o r m u l a przt~A, (s', prefhp~) = pr~(z)bA (s, prefa_ap ~)

396

(3.9)

and s i m i l a r l y . 9 P1" ~+~A" (St , pref~pa) I

=

(3.1o)

pr~6A (s, prefh_aPe)-

T

F r o m t h e d e f i n i t i o n of t h e w o r d s P0 and Pl we o b t a i n

if 2 d - / '

(przp'e) h -- (pr pe)h_~_v+u, (Prz+rP'e)l; = (pra(~lpa)h_d_v+ .,

(3,115

(pr p~)h = (pr cz)p=)h_e,(pr +,p~)~ = (pr,p=)h_ a,

(3.12)

--< h-< d + v , and

if d + v < h -< 2d. By u s i n g (3.9)-(3.10) and t h e d e f i n i t i o n of t h e s t a t e s, we o b t a i n prz5A, (s', p~) = pr2s', prr+z5 A, (s ', p~) = prr+zs', w h e n c e we find t h a t t h e w o r d s P'o, P'I and t h e s t a t e s' o f the a u t o m a t o n A' s a t i s f y t h e c o n d i t i o n (2.3). Next, b y u s i n g (3.7) and t h e i n e q u a l i t y (2.5) which is s a t i s f i e d by the n u m b e r l , the w o r d s P0 and Pl, and t h e s t a t e s of t h e a u t o m a t o n A, w e c a n e a s i l y p r o v e (by a s s u m i n g t h e c o n t r a r y ) t h a t t h e n u m b e r l ' , t h e w o r d s p~ and p{, and t h e s t a t e s' of t h e a u t o m a t o n A' a r e a l s o s a t i s f y i n g t h e i n e q u a l i t y (2.5). F i n a l l y , by u s i n g (3~ (3.10)-(3.12), and t h e i m p l i c a t i o n (2.6) s a t i s f i e d by t h e n u m b e r l , the w o r d s P0, Pi, and t h e s t a t e s o f t h e a u t o m a t o n A, we c a n s e e t h a t the n u m b e r l ' , the w o r d s P'0' P'I' and t h e s t a t e s' of t h e a u t o m a t o n A' a r e a l s o s a t i s f y i n g t h e i m p l i c a t i o n (2.6). T h u s s' w i l l b e an n - d i s t i n g u i s h a b l e s t a t e of t h e a u t o m a t o n A ' , with l ' < I . It i s e v i d e n t t h a t i f s e SA(m), t h e n s' e S A, (m); i . e . , the s t a t e s' is r e a c h a b l e f r o m an i n i t i a I s t a t e in t h e a u t o m a t o n A ' . T h i s c o m p l e t e s t h e p r o o f of t h e l e m m a . P r o o f o f L e m m a 17. S u p p o s e t h a t an n - d i s t i n g u i s h a b l e s t a t e s of w e i g h t I of a M o o r e a u t o m a t o n A = A / x o . ~ x A k and i t s input w o r d s P0 and Pl s a t i s f y t h e e o n d i t i o n s (2.3), (2.5), and (2~176 L e t us find n u m b e r s ti, . . . , t r , w h e r e n < - r - < l + n , s u c h t h a t 1 - < t l , o o . , t r < - k and t h e n u m b e r l , t h e s t a t e s ' = ( P r t r S , o . o , P r t r S ) a n d t h e i n p u t w o r d s p~ = P r t I P c ~ [] . . ~ [ ] p r t r P ~ ~ =0, 1, of the a u t o m a t o n A' = A t x . o . x A t r a l s o satisfy these conditions. F r o m (205) it f o l l o w s t h a t f o r i = l ,

....

l + n - 1 t h e r e e x i s t s a n u m b e r t in { t . . . . .

k} s u c h t h a t

~t (at (pros, pr t prefa_~p0)) 4:~t (~t (prts, Prt prefa-~Pi))-

(3.13)

F o r any i = / . . . . . l + n - 1 we s h a l l fix s u c h a n u m b e r t and d e n o t e i t by t(i). L e t us w r i t e t t = t ( / ) . . . . . t(l +n-l). Next, f r o m (2.6) we o b t a i n f o r j = l . . . . . l t [ i e f o l l o w i n g i m p l i c a t i o n . If

f o r a t b e l o n g i n g to {1 . . . . .

tn=

(prflo)a_j+ 1 4: (pr~pl)e_~.+~

(3.14)

~xt ((5t (Prts, prf prefa_flo)) 4= tat ((5t (prts , pr t prefd_/pl) )

(30155

k}, t h e n

f o r a t b e l o n g i n g to {1 . . . . . k}. L e t j(1) . . . . . j(m) b e a l l t h e n u m b e r s t h a t s a t i s f y t h e i n e q u a l i t y ( 3 . 1 4 ) . T h e n m < / and t h e i n e q u a l i t y (3.15) w i l l h o l d f o r any j = j(h5 f o r a t = t ( h ) . Now l e t u s w r i t e r = m + n and tin+ ~ = t(1) . . . . . t r = t(m). With t h e a i d of (3.13) and (3,155 we c a n s e e t h a t t h e n u m b e r s t 1. . . . . tr satisfy the conditions form u l a t e d at t h e b e g i n n i n g of t h e p r o o f . H e r e it is e v i d e n t t h a t s' ~ SA, (m) if s ( S A ( m ) o T h i s c o m p l e t e s t h e p r o o f of the l e m m a . 4.

Sufficient

Criterion

of

Homomorphic

Completeness

L e t us p r o v e t h e f o l l o w i n g p r o p o s i t i o n w h i c h w i l l s e r v e as a b a s i s f o r the p r o o f of t h e s u f f i c i e n c y of t h e c o n d i t i o n s of T h e o r e m 5. T H E O R E M 6.

Let a finite system of Moore automata

g[ s a t i s f y t h e f o l l o w i n g c o n d i t i o n s -

1. F o r any i = 0, 1. . . . . M ~ L - 1 t h e r e e x i s t s an a u t o m a t o n in ~ w h o s e i - l e v e l c o n t a i n s a b r a n c h e d state. 2. F o r any i = M~ . . . . . M g I - k N ~ - - 1 t h e r e e x i s t s an a u t o m a t o n in 92 w h o s e i - l e v e l c o n t a i n s a r e g u l a r s t a t e . T h e n t h e s y s t e m 92 w i l l b e h o m o m o r p h i c a l l y c o m p l e t e in t h e c l a s s of i n i t i a l a u t o m a t a .

397

For proving this theorem, let us assign two automata in ~ that satisfy the conditions ! and 2, and then specify in them the corresponding states, signals, and words, as well as some of their properties. After that we construct the product of these automata, i.e~ an automaton A, and we specify in is a subset of states. At the second step of the proof we study the properties of the states of this subset and we partition it into subsets S O and S I such that SoD IA 4= ~ 9 At the third step we shall show that S O and S t are a connectable and distinguishable pair of subsets. By virtue of Lemma 4 we hence obtain the assertion of the theorem. First Step of Proof. we shall write m=

M~I . We

We

shall assume

that the subscript i takes the values 0, l, .:. ,M~ -i.

select an automaton

Ai= (Si, Xi, Yi, 59 #i, li) from

an input word Pi of length i in such a way that the state 5i(si, pi ) is a branched

f o r c e r t a i n i n p u t s i g n a l s xoi a n d xfi in Xi. Hence we obtain

T h e n we c o n s t r u c t

superwords

For brevity

~I, its initial state s i and state, i.e.,

~rai =PiXaiX0iX0i . . . . .

k ~: i + t -+ (n0~)h = (n~&,

~ = 0 , 1.

(4.1)

k ~< i -+ 6 i (s i, pref~no~) = 6; (s~, prefknii ),

(4.2)

~i (6i (si, pref~+fi0~)) @ t~i (5~ (s~, prefi+l~Li)).

(4.3)

T h e r e e x i s t s a n u m b e r n s u c h t h a t f o r any r e g u l a r s t a t e s i t i s p o s s i b l e , in any a u t o m a t o n A b e l o n g i n g to N, in w h i c h s u c h a s t a t e e x i s t s , to find i n p u t w o r d s P0(S, A) and p l ( s , A) o f l e n g t h n s u c h t h a t 6A (s, p~ (s, A)) = s,

(4.4)

~a (6A (s, pref.p 0 (s, A))) ~ ~A (SA (S, prefjp I (s, A))), (4.5) ~tA (6A (s, prefkpo (s, A))) = ,uA (6 A (s, prefkp I (s. A))) --~ (P0 (s, A))k+l = (Pl (s. A))k+p These formulas

hold for all k=l,

....

n-i,

and, m o r e o v e r ,

6A (s. prefkp0 (s, A)) = 6A (s, prefkp I (s, A))

for all k=n/2 ..... n. Indeed, by for words p~(s, A) and p[ (S, A) of i, . .., n(s, A)- I]. Let us denote a regular state of the automaton A

(4.6)

(4.7)

virtue of the regularity of the state s the conditions (4.4)-(4.6) are satisfied equal length n(s, A) [for thesewords the condition (4.6) holds for any k= by n the least common multiple of all the numbers 2 .n(s, A), where s is and A~I. Let us construct the words p0(s, A) and pi(s, A) by setting

p,~ ( s, A) = p'~ (s, A)"(Po (s, A)) (~/~'A))-~, ~z = O, 1. By a direct verification we can see that c o n d i t i o n s (4.4)- (4.6). B y n o t i n g t h a t

l(pa(s, A ) ) = n and t h a t the w o r d s P0(S, A) a n d p l ( s , A) s a t i s f y t h e

5A (s, prefkp ~ (s. A)) = 5A (s, prefk_n(s,A) X (p; (s, A)) (n/n(s'AI)-I) f o r a l l k=n/2 .....

n, w e c a n s e e t h a t t h e c o n d i t i o n (4.7) i s s a t i s f i e d .

L e t us a s s i g n s u c h a n u m b e r n a n d w o r d s P0(S, A) and p l ( s , A) f o r e a c h r e g u l a r s t a t e s of an a u t o m a t o n A b e l o n g i n g to g[ . S u p p o s e t h a t t h e s u b s c r i p t j a s s u m e s the v a l u e s m . . . . . m+n-1. F o r any j we s h a l l s e l e c t an a u t o m a t o n Aj = (sj, Xj, Yj, 5j, #j, Ij) f r o m ~I, i t s i n i t i a l s t a t e sj and a n i n p u t w o r d p j of l e n g t h j in s u c h a w a y t h a t t h e s t a t e 6 j ( s j , pj) i s r e g u l a r . T h e o r e m 6 and of L e m m a 5. Thenwe shall construct superwords r e l a t i o n s . S i n c e 1 ( p j ) = j , it f o l l o w s t h a t

Such a s e l e c t i o n is p o s s i b l e by v i r t u e o f c o n d i t i o n 2 of

ha] =pip. (6](s r pj), Aj) pc, (6j (s], Pi)' Aj) . . . . . c~ : 0, 1 and e s t a b l i s h s o m e k ~< i ~ (~0i)k = (~j)k.

(4~

By v(k, j) w e s h a l l d e n o t e t h e s m a l l e s t n o n n e g a t i v e r e s i d u e of the n u m b e r k - j m o d u l o n, i.e~ k = j + r . n + v (k, j) f o r an i n t e g e r r . T h e n it i s e a s y to s e e t h a t

398

(4~

(~/)~ = (p. (5 i (s i, Pi), Aj)).(~.i),

(~/(si, pref~gcq) = 5 i (5 i (s i, p ) ,

(4.1o7

pref.(~j) p~ (8i (s], Pi) Ai)) for any k >_ j, which y i e l d s

(4.11)

v (k, ]) = 0 -+ 5 i (s i, prefknoi) =6] (s r prefkn~]).

By c o m p a r i n g (4.107 with (4.55 and then with (4.7), we obtain (4,12)

v (k, ]) = 1 -> P~i(6i (s/, prefk~o/)7 :~[~j (6i, pref~n~/)), (k, ]) ~ n/2--~ 5i(s}, prefkn0i) = 5i (s i, prefknli),

(4.13)

and by c o m p a r i n g (4.95 and (4.10) with (4.6), we obtain the i m p l i c a t i o n (4.145

~i (5i (si, prefk~o/)) = i~i (6/(s/, prefk:~l/)) ~ (~o/)k+l : (al/)k+~, if v(k, j) ~0.

F i n a l l y , r e c a l l i n g that l (pj) =j, we obtain k ~< ]-+ 6i (si, prefkn0j) = 6/(s:, prefkul).

We shall c o n s t r u c t an a u t o m a t o n A = A0x A 0 x A l • A 1 x . . .

(4.15)

• A m + n-1 x A m e n _ l , c a l l e d the c h a r a c -

t e r i s t i c a u t o m a t o n of the s y s t e m ~i, and define in it a s u b s e t of s t a t e s S as follows: We shall u s e the following notation: ~ 0 ---- 1, ~ 1 = 0, a ( 9 0 = a, a (9 1 = ~ a, a = 0 , 1 . A state s of an a u t o m a t o n A belongs to a s u b s e t S if and only if t h e r e e x i s t s an i n t e g e r k - > - I n u m b e r c~(r) belonging to {0, 1} such that

such that for any r = 0 , 1, . . . , m + n - 1

t h e r e exists a

Pr2r+l+./S = 6 r (Sr, prefe+ln~(~)e~w), 7 =0, 1.

(4.167

T h e n u m b e r s k and c~(r) that s a t i s f y (4.165 a r e c a l l e d the r a n k and the r - t h index of the state s. note that the s t a t e S O= (So, So, SI, S l . . . . . S n+n_i ' Sm+~_z)

Let us (4.177

is an initial s t a t e in the a u t o m a t o n A and that it belongs to the s u b s e t S. Second Step of P r o o f .

Let us c o n s i d e r s o m e p r o p e r t i e s of s t a t e s belonging to the s u b s e t S.

L E M M A 18. Let S be a s u b s e t of s t a t e s of the c h a r a c t e r i s t i c a u t o m a t o n A of the s y s t e m ~ defined by the conditions (4.165. Next, let k and l be the r a n k s of s t a t e s s and t belonging to S. It then follows f r o m p.A(S5 =#A(t! that k - / ( r o o d nS, if k, l -> m, and k = l o t h e r w i s e . P r o o f . Suppose that the conditions of the l e m m a a r e s a t i s f i e d and that the s t a t e s is such that f o r c e r t a i n n u m b e r s c~(r) belonging to {0, 1}, r = 0 , 1, . . . . r e + n - 1 the r e l a t i o n s (4.16) a r e satisfied, w h e r e a s the s t a t e t is such that f o r c e r t a i n n u m b e r s fl(r5 belonging to (0, 1}, r = 0 , 1 . . . . . m + n - 1 , we have the relations pra+~+ t = 6, (s,, pref~+#~(,)$v,),

7=0. I.

F r o m t h e s e r e l a t i o n s and f r o m the f o r m u l a #A(S)=~A(t), we find that ~t (6r (s,, prefk+jna(,),)) = b~.(6 (s., preft+1 zc~t~)~), ~, (5 (s,, prefk+in 7~{r~r)) : lx~ (6, (s,,

[

(4.185

[

I Let us consider

three

cases:

1. L e t k , l > - m a n d k ~ l ( m o d n ) . F r o m the l a t t e r f o r m u l a we find that v(k, m5 : v ( 1 , m). By @ we s h a l l c o n s i d e r s u b t r a c t i o n modulo n, and c o n s i d e r two s u b c a s e s :

399

l a . ~ (k, m) 0 v (l. m) ~< n/2 . L e t us s e l e c t a n u m b e r r such that r-> m and v (k + 1, r) = 1. Then e i t h e r v ( l + l , r ) = 0 , o r v(l +1, r) > n / 2 . F r o m (4.18) we then obtain in a c c o r d a n c e with (4.12) the f o r m u l a ~, (5, (sr, pre[/+l~( r )r)) =/= ~. (St, prefl+,~(,).)), which c o n t r a d i c t s (4.11) if v (l +1, r) =0, and (4.13) if u(t +1, r) ->n/2. lb. v ( k , m ) Q , ~ ( l , m ) > n/2 . L e t us s e l e c t a n u m b e r r such that r >-m and v(l +1, r). T h e n e i t h e r u(k+ 1, r ) = 0, o r v(k + 1, r ) > n / 2 + 1. S i m i l a r l y to the p r e v i o u s s u b c a s e we obtain f r o m (4.18) the f o r m u l a ~r (8 (s~, prefk+l~(~)r) ) 4: g~ (6r (~, prefk+l~n~(~)r)),

(4.19)

which c o n t r a d i c t s (4.11) if v ( k + l , r ) = 0 , and (4.13) if v ( k + l , r) >n/2 +10 The c o n t r a d i c t i o n s in the s u b c a s e s (a) and (b) show that k - l (rood n), if k, 1 ~ m. 2. L e t k < m a n d l - > m . Let us s e l e c t a n u m b e r r such that r -> m and v (l + l, r ) = l . In a c c o r d a n c e with (4.127 we then obtain (4.195 f r o m (4.185, which c o n t r a d i c t s (4.15), s i n c e k < m -< r. S i m i l a r l y to the f o r e going, we a r r i v e at a c o n t r a d i c t i o n by a s s u m i n g that l < m and k >- m. H e n c e the e a s e 2 is not feasible. 3. Let k, l < m . A s s u m i n g that k < m , we obtain a c c o r d i n g to (4.3) f o r r = / f r o m (4.18) the f o r m u l a (4.19), which c o n t r a d i c t s (4~ We also a r r i v e at a c o n t r a d i c t i o n by a s s u m i n g that / < k . Hence k = l if k, I < m. This c o m p l e t e s the p r o o f of the l e m m a . By v i r t u e of L e m m a 18 it is p o s s i b l e to define a m a p p i n g p :PA(S) ~ { - 1 , 0, 1 . . . . . m + n - 1 } in such a way that for any state s the n u m b e r p(#A(S)) coincides with the r a n k of the state s if it is s m a l l e r than m, and with one of the n u m b e r s m, . . . , m + n - 1 that is c o m p a r a b l e with the r a n k of the state s o t h e r wise. It is e a s y t o see that f r o m the r e l a t i o n p(~A(S)5= - 1 it follows that s = s~ w h e r e the s t a t e s ~ e~cp r e s s e d by (4.17). Let W be the set of all p a i r s (y, j) belonging to #A(S) x {m . . . . .

m+n-1}

m ~< p (y). v(~ (y) + t, ]) 4= 0

that s a t i s f y the inequalities (4.20)

By v i r t u e of L e m m a 18 and of the condition (4.14) it is p o s s i b l e to define the m a p p i n g a : W x {0, 1} ~ XmU . . .U X m + n _ l , in such a way that for any s belonging to S and any j s a t i s f y i n g (4.205, w h e r e y = ~ A ( S ) , we have (y, ], ~?) = (~(/)~vi)0(u)+2, ~?----0, 1,

(4.21)

w h e r e ~ (j) is the fixed j - t h index of the s t s t e s. In a c c o r d a n c e with L e m m a 18, it follows f r o m (4.16) and (4.10) that pr2,+~+vs = 6 i (s/, pre[Q(~A(S))+lr~a(i)$vi), y = 0, 1. F r o m this f o r m u l a , by u s i n g once m o r e the r e l a t i o n (4.16), we find that f o r any s belonging to S and any j s a t i s f y i n g (4.20), w h e r e y=/~A(S), we have 6/(pr2~+l+vs, ~ (~tA (s), ], ~})) = ~i (s/, pref~+2~(]),vi), 7 = 0, l,

(4,22)

w h e r e k i s the r a n k of the s t a t e s and ~(j) is its j - t h index. L E M M A 19. Let S be the s u b s e t of s t a t e s o f the c h a r a c t e r i s t i c a u t o m a t o n A of the s y s t e m ~ s p e c i fied by the conditions (4.16). Next, let c~ and fi be the p(#A(S))-th and the p(t~A(t))-th indices of the s t a t e s s and t belonging to S. Hence if PA(S) =t~A(t) a n d p ( # A ( S ) ) ~ - 1, then a =ft. P r o o f . Suppose that the conditions Of the l e m m a a r e satisfied. As in the p r o o f of the p r e v i o u s l e m m a , we can obtain f r o m ttA(S)=~A(t) the f o r m u l a (4.18). Let us c o n s i d e r two c a s e s : 1. p(#A(S))-m. Here, too, we shall w r i t e r=P(#A(S)).

A c c o r d i n g to L e m m a 18 we have k - p ( # A (s))

( 9d n) and l - p(PA(s)) (mod n), which y i e l d s v ( k + l , r) =1 and v(l +1, r ) = l . (4.125, we find that a =/3. This c o m p l e t e s the p r o o f of the l e m m a .

400

By c o m p a r i n g (4.18) with

By v i r t u e of L e m m a 19 it is p o s s i b l e to define a m a p p i n g X' : #A (s) -* {0, t} in such a way that for any s t a t e s in S o t h e r t h a n t h e s t a t e s o the n u m b e r X' (PA(S)) will be equal to the p(/XA(S))-th i n d e x o f the s t a t e s, and X' (#A(S~ = 0, w h e r e the s t a t e s o is s p e c i f i e d in (4.17). L e t us define a p a r t i t i o n of the set of s t a t e s S into s u b s e t s SO and S~ by the following f o r m u l a (for any s belonging to S and fi=O, 1):

Z' (t~ (s)) = 6 ~ s~S~.

(4.23)

It is evident t h a t s~ So, w h e n c e we obtain So (q IA e 73. Let us go o v e r to the t h i r d step of the p r o o f . We shall define the m a p p i n g s ~:YA-~{0, l} as follows: F o r any y e # A ( S ) we s h a l l w r i t e .

,

[(~(y,r,'~),

if

r,~(y)>~m and

v(s

(p : {0, 1} x Y ) -* X A

and

, r)=~-0,

pr2~+~+~~P(~' g) = / (naew)o(m+~ otherwise, 7 = 0, 1 and ?t(y)=• F o r any y ( Y A - # A ( S ) we shall define t h e m a r b i t r a r i l y . L e t us show that the s u b s e t s So, St and the m a p p i n g ~o s a t i s f y the condition (1.8)o Let s ( S = SoUS t. We shall c o n s i d e r two e a s e s . 1. L e t p(#A(S)) < m.

F r o m (4.16) and the definition of the m a p p i n g

pr2~+~+v6A (s, q) (15, t~A(S))) = (}r [6r (Sr, prefe+~ n~(~)~w), (rti~.~v)~+~),

(4.24)

w h e r e k= p(#A(S)) is the r a n k of the s t a t e s. In a c c o r d a n c e w i t h (4~ pref~+l~$vr

if r < m

= pref~+lx~$v,

and k + l >r, and

(~aew)~+2 = (u~vr)k+2,

(4.25)

if r < m and k + 1 > r, w h e r e a s a c c o r d i n g to (4.8) we have pref~+t ~ v ,

= pref~+l~tl3~.W'

if r_> m and k + l - -< m~ By c o m p a r i n g (4.24) and the last equations, we obtain Pr2.+t+v 6A (s, (p (~, ~A (s))) = 5, (sr, prefk+2~(.)~v), if r < Q(PA(s)), 6 (s~, prefk+2a6~w), ff r >ip QxA (s)), 7 = 0, 1, s i n c e k+ 1 = p(/~A(S)) + 1 ~ m .

F r o m this f o r m u l a and the definition of the m a p p i n g X', we obtain %' (~A (SA (S, q0([, FA (S))))) = [

(4~

2. Let p(pA(S)) -> m~ S i m i l a r l y to (4.24), we obtain [5 (pr2~+~+vs, (5(~A (S), r, 7)),

if

r ~ m and

= I v (P (PA (s)) + 1, r) ~ O,

pr2,+~+v(5A (s, ~p ([~, #A (S)))

|] 6 (6 (S, pref~+i~(~)ew), (~$w)e(~A(~))+2)

(4.27)

' otherwise,

T= 0, I, where k is the rank of the state s. Since according to L e m m a follows that

18 we have k - [(~tA(S))(mod n), it

,~ (/~ + l, r) = ,~ (p (~)(s)) + L r),

9~(/~ + 2, r) = v (p (~A (S)) + 2, r). H e n c e follows that if r >- m and v(p(/xA(S))+ 1, r)= 0, then 6 (s,, pre!~+ln~,) = (5, (s,, prei~+~%|

by virtue of (4.11), and

401

by v i r t u e o f (4o9). By c o m p a r i n g (4.27) with t h e l a s t two e q u a t i o n s , and a l s o with (4.25) and (4.22), w e o b t a i n

i6r (st, pref~+2aa(r)$,~r),

if

r >/m and

pr2r+i+~ (5A (s, % (if, btA (S))) = Iv (p (~A (S)) + 1, r) =/=0, [6 (s, preik+2n~.~w) otherwise, 7 = 0, 1, w h e r e k i s t h e r a n k of t h e s t a t e s. As in t h e p r e v i o u s c a s e , we h e n c e o b t a i n (4.26). By v i r t u e of (4.23), we o b t a i n f r o m t h e l a t t e r f o r m u l a the i n c l u s i o n 5A(S , ~0(fi, #A(S)))E Sfl, which s i g n i f i e s that t h e c o n d i t i o n (1.8) i s s a t i s f i e d . At t h e s a m e t i m e the s u b s e t s So and St and t h e m a p p i n g • s a t i s f y the c o n d i t i o n (1.9), which f o l l o w s d i r e c t l y f r o m t h e i r d e f i n i t i o n . By v i r t u e of the r e m a r k s m a d e at the b e g i n n i n g of t h e p r o o f , we h e n c e o b t a i n t h e a s s e r t i o n of t h e t h e o r e m . 5,

Sufficiency

of

Conditions

of Principal

Theorem

In t h i s s e c t i o n we s h a h show t h a t f r o m t h e a u t o m a t a of t h e s y s t e m s a t i s f y i n g t h e c o n d i t i 0 n s of T h e o r e m 5 i t is p o s s i b l e to a s s e m b l e with the a i d of p r o d u c t s a s y s t e m of a u t o m a t a 9/ t h a t s a t i s f i e s the c o n d i t i o n s of T h e o r e m 6. By v i r t u e of L e m m a 2 w e h e n c e o b t a i n t h e s u f f i c i e n c y of t h e c o n d i t i o n s of T h e o r e m 5. L e t us p r o v e t h e f o l l o w i n g p r e p o s i t i o n s : L E M M A 20. S u p p o s e t h a t a p r o d u c t of a u t o m a t a b e l o n g i n g to a f i n i t e s y s t e m 9/ c o n t a i n s an Nu d i s t i n g u i s h a b l e s t a t e t h a t is r e a c h a b l e f r o m an i n i t i a l s t a t e . T h e n t h e r e e x i s t s f o r any p o s i t i v e N a p r o d u c t of a u t o m a t a b e l o n g i n g to 9~ t h a t c o n t a i n s an N - d i s t ~ g n i s h a b l e s t a t e which is r e a c h a b l e f r o m an i n i t i a i s t a t e . P r o o f . S u p p o s e t h a t a p r o d u c t of a u t o m a t a o f t h e s y s t e m ~ , i . e . , t h e a u t o m a t o n A, c o n t a i n s an N,~d i s t i n g u i s h a b l e s t a t e s that i s r e a c h a b l e f r o m an i n i t i a l state~ L e t us s h o w t h a t f o r any p o s i t i v e i n t e g e r k t h e r e e x i s t s in t h e a u t o m a t o n A k a k . N ~ - d i s t i n g u i s h a b l e s t a t e t h a t i s r e a c h a b l e f r o m an i n i t i a l s t a t e . L e t us a s s i g n a p o s i t i v e k a n d s e l e c t N~ - d i s t i n g u i s h i n g w o r d s P0 and Pi o f e q u a l l e n g t h d e n o t e d by c. We s h a l l d e f i n e a n o n n e g a t i v e i n t e g e r r s u c h t h a t r . c - > ( k - l ) - N ~ . T h e n we c o n s t r u c t s t a t e s s t . . . . . s k and input w o r d s P0; . . . .

h=l .....

, P0k and Pit, 9 9

k, c ~ = 0 , 1 , and n = N ~ .

Ptk by s e t t i n g Sa = 6A (S, pref . . . . (k-a),P~),

(5.!)

P~a = suf. . . . (k--h)~P~'P~prei . . . . (~--a>P~),

(5.2)

It is e a s y to s e e t h a t l ( P c ~ h ) = r c + c "

We shall obtain several auxiliary formulas. u = 0, 1 . . . . . r. c + c- (k-h)n the formula

F r o m (5.1)-(5.2) and (2.3) we o b t a i n f o r h = 1, . . . .

k and

5A (% pref(~_a>+,p~) = 6A(s, pref (p~preI _~_~>pg)). By s e t t i n g in t h i s f o r m u l a u = c - i ,

where i=l,

. .., I +n-l,

we o b t a i n

6a (s, pref(~_a~+~_,p.h) = 5A (s, pre[ ~pa), w h e r e a s by s e t t i n g u = c - j ,

w h e r e j =1 . . . . .

l , we o b t a i n

6 A (s, pre[(i~_hm+c_ipaa) = 6A (S, prei _/pa) F i n a l l y , by s e t t i n g u = r c + c - ( k - h ) n ,

(5.4)

we o b t a i n 5A G , &h) = %

Similarly, for h=l .....

(5.3)

k a n d u=0, 1 . . . . .

rc+c-(k-h)n-1

(5.5) we h a v e

(P~)(~.-a)r,+~+1 = (P. "preir~-(k-~,)nP~)=+p w h e n c e we o b t a i n (Pa~)(k-l,)a+r if u=c--j, where j= 1.....

= (Pa)c-j+P

l , and

(Poh)(~-a)n+,~+~ = (Pta)(~-a)n+u+l, if u~

402

c.

(5.~) (5.7)

L e t us c o n s t r u c t an a u t o m a t o n B =A k, i t s s t a t e t = (sl, o . . , a = 0 , 1. It t h e n f o l l o w s f r o m (5.5) t h a t

Sk), and t h e input w o r d s q a = p a t D . . , E S p a k ,

G(t~ q~) = t.

(5.8)

L e t u s w r i t e l ' = l + r e - ( k - 1)n, w h e r e n = N~ mud I i s a n u m b e r s u c h t h a t t h e s t a t e s and t h e i n p u t w o r d s P0 and Pl of the automaton A satisfy the conditions (2.3) and (2.5)-(2.6). Let the number i' be such that l' ~< i'
Next, f o r any j ' = 1 . . . . .

re-(k-1)n

(5.9) we o b t a i n f r o m (5.7) t h e e q u a t i o n

(qo)l(go~-r+, = (q~)mo-r+,"

(5.10)

F i n a l l y , any n u m b e r j' s u c h t h a t r e - ( k - 1)n < j' < l ' , c a n b e r e p r e s e n t e d in the f o r m j' = r c - ( k - 1)n + j, w h e r e j i s s u c h t h a t 1 -< j-< I . T h e n , by u s i n g (2.6), as w e l l a s (5.4) and (5.6) f o r h = l and (5.7) for h > l , we f i n d t h a t ~ (6s (t, preil(qo)_i.q0)) = ~ (6B (t, prefl(q~)_j.qt)) -> (q0)L(q~)-/'+l = (qO~(qO-i'+~

(5.11)

f o r t h e j' u n d e r c o n s i d e r a t i o n . F r o m t h i s f o r m u l a and f r o m (5.10) w e find t h a t t h e i m p l i c a t i o n (5.11) h o l d s f o r any j = 1, . . . , 1 '0 H e n c e t w i l l be a k . N ~ - d i s t i n g u i s h a b l e s t a t e . it remains to show that the s~ate t is reachable from an initial state in ~he automaton for a number v. From (5.1) and (5.5) we hence obtain the inclusion

sa E S A (v + r c - - ( k - - h ) n +

wd), h = 1. . . . .

sincen=N~o

Hence

t~SB(V+rc+wd

Let s~SA(V)

k, w > O ,

w h e r e d = l (P0k)" By s e l e c t i n g w in s u c h a w a y t h a t v + r c - - ( k -- l ) n + w d > N ~ , Lemmas 5 and 6 that sh ES A(v + r c + w d ) ,

B.

we find in a c c o r d a n c e with

h = l . . . . . k,

). T h i s c o m p l e t e s the p r o o f of the l e m m a .

LEMMA 21o Suppose that a finite system of automata ~ satisfies the conditions 2 and 3 of Theorem 5~ Then there exists for any i=M~l ..... M~, + N~ -i a product of automata in 9J whose i-th level contains a regular state. _Proof. F o r any s e p a r a b l e s t a t e s of an a u t o m a t o n A in qA in which s u c h a s t a t e e x i s t s , l e t us a s s i g n i n p u t w o r d s p0(s, A) s p t ( s , A) of e q u a l length c ( s , A). By c we s h a l l d e n o t e t h e l e a s t c o m m o n m u l t i p l e of t h e l e n g t h s of t h e a s s i g n e d w o r d s , and we s h a l l s e l e c t a n u m b e r i f r o m t h e s e q u e n c e M ~ . . . . . M ~ + N ~ - - 1. A c c o r d i n g to L e m m a s 13 and 20, t h e r e e x i s t s i n a p r o d u c t of a u t o m a t a b e l o n g i n g to 91, i . e . , t h e a u t o m a t o n B, a c - d i s t i n g u i s h a b l e s t a t e t f r o m the i - l e v e l of t h e a u t o m a t o n B. L e t u s s p e c i f y c - d i s t i n g u i s h i n g w o r d s q~ ~:ad ql of t h e s t a t e t w h o s e l e n g t h s c o i n c i d e . By d we s h a l l d e n o t e t h e l e a s t c o m m o n m u l t i p l e of t h e n u m b e r s l (q~), c, and N ~ , and w e s h a l l c o n s t r u c t the input w o r d s q0 and ql b y s e t t i n g

% = q'~ "(qo)(~'(qo'-', ~ = 0,1. It i s e v i d e n t t h a t l ( q a ) = d a n d t h a t t h e w o r d s q and qt a r e e - d i s t i n g u i s h i n g the s t a t e t, i . e . , t h e c o n d i t i o n s (5~ a r e s a t i s f i e d f o r s o m e l and any i = l . . . . . c + l - 1 , w h e r e a s (5.11) h o l d s f o r any j ' = 1 . . . . . l. L e t h a s s u m e t h e v a l u e s 0, 1, . . . , d - c - / ~ F o r any h w e s h a l l s e l e c t an a u t o m a t o n Ah f r o m 9d and t a s e p a r a b l e s t a t e s h' f r o m t h e ( c + i + h ) - l e v e l , i~176S h E S A h ( C + i + h ) ~ F o r any h we s h a l l c o n s t r u c t a s t a t e s h and i n p u t w o r d s P0h and Pth o f t h e a u t o m a t o n A h by s e t t i n g sa = 6~ (ss preid_~_~p0 (s~, An)),

G~ = suf,-c-~ % G , Ah))d~ (p~(s~, G)) ch preC._c_ h (PoG" & ) ) %

(5.12)

(5.13)

403

= 0, 1, w h e r e the P a (s~, A h) a r e p r e a s s i g n e d w o r d s for a s e p a r a b l e s t a t e s~ of an a u t o m a t o n A h belonging to ~ , and Ch=C/C(S~, Ah) , dh= (d/c(s~, A h ) ) - c h. It is e a s y to s e e that l (pah 5 = d and

5~(s~, p~)

(5.145

-----s~,

~h (6h (s~, preIh+,po~)) 4= t~h6~ [sh, preih+,plh)).

(5.155:

Let us c o n s t r u c t an a u t o m a t o n A = A 0 x A t x o o o • Ad_c_ / x B, its state s = (So, sl, ~ . . , Sd_c_/, t), and the input w o r d s Pa = Pao D PatU . o , [] Pad_c_tf~_ qa' ~ = O ' l "

We then obtain f r o m the conditions (5.14) and (5.85 the equation (2.3), w h e r e a s f o r h= 0 we obtain f r o m the condition (5.1) the inequalities (2.2). Next, f r o m the condition (5.15) f o r h = 0 , 1 . . . . . d-c-/ and f r o m (5.95 f o r j' = d - c - l + 1 . . . . . d - 1 we obtain the i m p l i c a t i o n (2~ for j= 1 . . . . . d - l . Finally, let us a s s u m e that the c o n c l u s i o n of the i m p l i c a t i o n (2.45 is f a l s e f o r a j such that d - l
Conditions

of Completeness

of Particular

Systems

F r o m the g e n e r a l t h e o r e m on h o m o m o r p h i c c o m p l e t e n e s s we shall d e r i v e in this s e c t i o n the conditions of c o m p l e t e n e s s of p a r t i c u l a r s y s t e m s obtained in [3] and [6-9]; we shall also e s t a b l i s h the existence of m i n i m a l h o m o m o r p h i c a l l y c o m p l e t e sets of any finite p o w e r . The conditions of h o m o m o r p h i c c o m p l e t e n e s s of s y s t e m s of noninitial M o o r e a u t o m a t a w e r e obtained by L e t i c h e v s k i i [7] ( T h e o r e m 5). It is p o s s i b l e to obtain t h e m in different f o r m f r o m T h e o r e m 5 of the present paper. T H E O R E M 7. F o r a s y s t e m of noninitial M o o r e a u t o m a t a to be h o m o m o r p h i c a l l y c o m p l e t e in the c l a s s of initial (noninitial) automata, it is n e c e s s a r y and sufficient that it contain an a u t o m a t o n with a s e p a r a b l e state and an a u t o m a t o n with a 1 - d i s t i n g u i s h a b l e state. P r o o f . By v i r t u e of condition 2 of T h e o r e m 5, any h o m o m o r p h i c a l l y c o m p l e t e s y s t e m in the c l a s s of initial (noninitial) a u t o m a t a contains an a u t o m a t o n with a s e p a r a b l e state, w h e r e a s by virt-ae of condition 3 of T h e o r e m 5 and of L e m m a t3 it contains an a u t o m a t o n with a 1 - d i s t i n g u i s h a b l e s t a t e . C o n v e r s e l y , let A be an a u t o m a t o n with a s e p a r a b l e s t a t e s, and B a n a n t o m a t o n with a 1 - d i s t i n g u i s h a b l e state. By v i r t u e of L e m m a 9 it then follows f o r any L=0, 1 . . . . . M{A ' 13}-1 that the i - l e v e l of the a u t o m a t o n A contains a s e p a r a b l e , and h e n c e b r a n c h e d s t a t e s; this signifies the fulfillment of condition 1 of T h e o r e m 5 f o r the s y s t e m ~ = {A. B}. By v i r t u e of L e m m a 9 we obtain also the condition 2. Finally, by v i r t u e of L e m m a 7 the a u t o m a t o n B contains an N,~ - d i s t i n g u i s h a b l e state, which indicates that condition 3 is fuKilled. T h e a s s e r t i o n of the t h e o r e m f o r the c a s e of c o m p l e t e n e s s in the c l a s s of noninitial a u t o m a t a follows by v i r t u e of T h e o r e m 4 f r o m the fact that the e x i s t e n c e of a s e p a r a b l e s t a t e in a noninitial a u t o m a t o n i m p l i e s the e x i s t e n c e of d i f f e r e n t l y l a b e l l e d initial s t a t e s in this automaton. This c o m p l e t e s the p r o o f of the theorem. F o r f o r m u l a t i n g this t h e o r e m in the t e r m s of [7], let us i n t r o d u c e the following c o n c e p t s : A c y c l e in an a u t o m a t o n is a s e q u e n c e of s t a t e s such that we can go o v e r f r o m one state to the next and f r o m the last state to the f i r s t . A p a i r of c y c l e s in an a u t o m a t o n is s a i d to be c o n n e c t e d if t h e i r last s t a t e s coincide. It is e a s y to s e e that if (fo, ft) is a c o n n e c t e d p a i r of c y c l e s in an a u t o m a t o n A, we have for w o r d s P0 and Pt belonging to X-*A-{e} and f o r a s t a t e s belonging to SA that s a t i s f y (2.3) the following f o r m u l a : fa = 5A (S, preflp~)... 5A (s, pref;(pa)p~), c~ = 0, 1.

404

(6.1)

F o r c o n n e c t e d p a i r s of c y c l e s of M o o r e a u t o m a t a we shall i n t r o d u c e n o n n e g a t i v e i n t e g e r p a r a m e t e r s X, *, and p. Let (f0, f l ) be a c o n n e c t e d p a i r of c y c l e s of a M o o r e a u t o m a t o n A, w h e r e f 0 a n d f 1 a r e defined by (6.1) f o r s o m e P0 and pi belonging to X ~ and s belonging to SA. T h e n the n u m b e r X(f0 , f l ) will be equal to the m i n i m u m length of the w o r d s P0 and Pl. T h e n u m b e r "r(fo, f 1) is equal to the l a r g e s t 1 such that

l <- X ( f o , f l )

and ~A (SA (S, prefl(po)_~p0)) 4= ~tA(5A (s, preft(.,)_ipl))

(6.25

for any i = 1 . . . . . l --1. The n u m b e r P(fo, f l ) is equal to the l a r g e s t l such that I <- X(fo, f l ) and f o r any j = 1..... l - 1 t h e r e exists an input s i g n a l x belonging to X A that s a t i s f i e s for any c~ = 0, 1 the i m p l i c a t i o n ~tA(6A (s, preftr

= ~tA (~A (S, preitr

) -+ 5A(s, preil(o.)_ip a -x) = 5A (s, preizco.)_,+lpa).

(6.3)

It is evident t h a t the p a r a m e t e r s X, ~, and p do not depend on the c h o i c e of the w o r d s P0 and Pl s p e c i f y i n g the c o n n e c t e d p a i r of c y c l e s (fo, f l ) o Suppose N a t the w o r d s p~ and p'~ s p e c i f y a c o n n e c t e d p a i r of c y c l e s (fo, f l ) with the aid of the f o r m u l a s (6.i)o By J we s h a l l denote the set of all n u m b e r s belonging to 1 . . . . . p(fo, f l ) - I for which the p r e m i s e of the i m p l i c a t i o n (6~ is satisfied, and f o r any j belonging to J we shall s p e c i f y a signal x= x(j) belonging to ! X A t h a t s a t i s f i e s (6.3). L e t us c o n s t r u c t the w o r d s P0 and p~ by setting l(Pot)=l (pc~) and j E J -~ (p~)j = x (1), ] ~ J ~ f o r any j = l . . . . . f o r any j =1 . . . . .

(P2, = (P,:)/

I (pc~), c~= 0, 1. By v i r t u e of (6.3) we hence find that 5A(S , prefjPc~)=fA(S , p r e f j p ~ ) 1 (p~) and c~ =0, 1, whence we obtain the i m p l i c a t i o n ~td (5a (s, prefl(p~

= ~tA (~A(S, pref,(p,)_/pl)) -> (P0)t(o,)--i+l = (Pl)l(p,)--/§

(6.4)

f o r any j = 1 . . . . . p(f0, f l ) - - l . Thus if (f0, f l ) is a c o n n e c t e d p a i r of c y c l e s in an a u t o m a t o n A, t h e n w o r d s P0 and Pl b e l o n g i n g to X ~ - {e} and a s t a t e s belonging to SA that s a t i s f y (2.3) will s a t i s f y also the conditions (6.1) and (6.4). Let us note the validity of the following lemma: LEMMA 22. If P0 and Pl are l-distingnishing words for a state s of a Moore automaton A, and (f0, fl) is a connected pair of cycles defined by (6.1), then T(f0 , fl) < P(fo, fl)o Conversely, if a connected pair of cycles (fo, fl) of a Moore automaton A satisfies the inequality ~'(f0,fl) - l +I. Hence follows the first assertion. Conversely, let s be the last (common) state of cycles f0 andfl belonging to a connected pair of cycles (f0, fl), and let P0 and pl be input words satisfying the conditions (2.3), (6ol) and (6~176 By virtue of (6.2) and (6.4) it then follows from the inequality T(fo , fI) < P(fo, fi5 that s is a l-distingnishable state. This completes the proof of the lemma. By using (6.1) and Lemma

22, we can reformulate

Theorem

7 as follows:

THEOREM 8. A system of noninitial Moore automata is homomorphically complete in a class of initial (noninitial) automata if and only if it contains an automaton A with a connected pair of cycles (f0,fl) and an automaton B with a connected pair of cycles (g0, g15 that satisfy the following conditions: i. The markers

of the first states of the cycles f0 andfl

are distinct.

2, "r(go, gl) < P(go, gl)!t is easy to see that this theorem

is a stronger version of Theorem

Let us obtain the completeness conditions for systems of automata A particular case of such automata is Medvedev's automaton.

5 of [7]. with one-to-one

marker

functions.

THEOREM 9. For a system of automata with one-to-one marker functions to be homomorphicaIly complete in a class of initial automata, it is necessary and sufficient that a firAte subsystem 91 of this system satisfy the following conditions:

405

1. F o r any i = 0 , 1 . . . . . M ~ - - 1 t h e r e e x i s t s an a u t o m a t o n in ~f w h o s e i - l e v e l c o n t a i n s a b r a n c h e d s t a t e . o

a]..

2. F o r any i = M ~ , . o . , M ~ - N ? ~ - - I there exists an a u t o m a t o n in ~ w h o s e i - l e v e l c o n t a i n s a s e p a r a b l e state~

a 0

"

1

b F i g 2. a) G r a p h of a u t o m a t o n Ai, i = 0 , 1, . . . , n - l ; b) g r a p h of a u t o m a t o n An. T h e i n i t i a l s t a t e s a r e m a r k e d by d o u b l e c i r c l e s .

Proof~ The necessity of the conditions follows from Theorem 5, and the sufficiency from Theorem 6 (by virtue of Lemma Ii). T H E O R E M 10. F o r a s y s t e m of n o n i n i t i a l a u t o m a t a with o n e - t o - o n e m a r k e r f u n c t i o n s to be h o m o m o r p h i c a t l y c o m p l e t e in a c l a s s of i n i t i a l (noninitial) a u t o m a t a , it i s n e c e s s a r y and s u f f i c i e n t t h a t it c o n t a i n an a u t o m a t o n with a separable state.

P r o o f . T h e n e c e s s i t y of the c o n d i t i o n s f o l l o w s d i r e c t l y f r o m T h e o r e m 7, w h e r e a s t h e s u f f i c i e n c y f o l l o w s f r o m T h e o r e m 7 by v i r t u e of L e m m a 11, s i n c e any r e g u l a r s t a t e i s 1 - d i s t i n g u i s h a b l e . T h e c o m p l e t e n e s s c o n d i t i o n s f r o m T h e o r e m 10 and 9 w e r e o b t a i n e d by L e t i c h e v s k i i [7] and t h e a u t h o r [3], r e s p e c t i v e l y . L e t us o b t a i n t h e c o m p l e t e n e s s c o n d i t i o n s f o r s y s t e m s of a u t o m a t a with l o o p s i n the i n i t i a l s t a t e s and in a t l t h e s t a t e s . T H E O R E M 11. F o r a s y s t e m of a u t o m a t a with l o o p s in t h e i n i t i a l s t a t e s to be h o m o m o r p h i c a l l y c o m p l e t e in a c l a s s of i n i t i a l a u t o m a t a , it is n e c e s s a r y and s u f f i c i e n t t h a t it c o n t a i n an a u t o m a t o n with an i n i t i a l b r a n c h e d s t a t e , an a u t o m a t o n with a s e p a r a b l e s t a t e r e a c h a b l e f r o m an i n i t i a l s t a t e , and an a u t o m a t o n with a 1 - d i s t i n g u i s h a b l e s t a t e r e a c h a b l e f r o m an i n i t i a l s t a t e . P r o o f . T h e n e c e s s i t y of the f i r s t conditiOn f o l l o w s f r o m c o n d i t i o n 1 for i = 0, the n e c e s s i t y of the s e c o n d f o l l o w s f r o m c o n d i t i o n 2, and the n e c e s s i t y of t h e t h i r d f o l l o w s f r o m c o n d i t i o n 3 of T h e o r e m 5 by v i r t u e of L e m m a 13. C o n v e r s e l y , s u p p o s e t h a t t h e a u t o m a t o n A c o n t a i n s an i n i t i a l b r a n c h e d s t a t e s, t h e a u t o m a t o n B c o n t a i n s a s e p a r a b l e s t a t e t r e a c h a b l e f r o m an i n i t i a l s t a t e , and the a u t o m a t o n C c o n t a i n s a 1 - d i s t i n g u i s h a b l e s t a t e r e a c h a b l e f r o m an i n i t i a l s t a t e , with A, B, and C b e i n g a u t o m a t a with l o o p s in t h e i n i t i a l s t a t e s . It is e a s y to s e e t h a t for any i = 0 , 1 . . . . . M,~ - - I, w h e r e 9I = {A, B, C}, s E S A (i), we h e n c e o b t a i n c o n d i t i o n 1 of T h e o r e m 5. Since SB(i) C S B ( i + 1) f o r any a u t o m a t o n B with loops in t h e i n i t i a l s t a t e s and for any i, it f o l l o w s t h a t t ES B(M~I), w h e n c e we o b t a i n by v i r t u e of L e m m a 8 the c o n d i t i o n 2 of T h e o r e m 5. C o n d i t i o n 3 of t h i s t h e o r e m f o l l o w s f r o m the d e f i n i t i o n of the a u t o m a t o n C. T h i s c o m p l e t e s t h e p r o o f of the theorem.

THEOREM 12. For a system of automata with loops in each state to be hom0morphically complete in a class of initial automata, it is necessary and sufficient that it contain an automaton with an initial branched state and an automaton with a separable state reachable from an initial state. Proof. The necessity of the conditions follows directly from Theorem Ii, and the sufficiency from Theorem ii by virtue of Lemma 12, since any regular state is 1-distinguishable. By virtue of Lemma

12, Theorem

7 yields Theorem

13.

THEOREM 13. For a system of noninitial automata with loops in each state to be homomorphically complete in a class of initial (noninitial) automata, it is necessary and sufficient that it contain an automaton with a separable state. The completeness conditions formulated in Theorem 13 were obtained [i0]. In the same way it is possible to interpret also Red'ko's result [8]. In conclusion

let us establish a relationship between

completeness

in different form by Spivak

and the power

of the basis.

THEOREM 14. From any system that is homomorphically complete in a class of initial (noninitial) automata, it is possible to select a finite subsystem that is homomorphically complete in the e]ass under consideration.

406

Proof, Such a system is the system ~ (or ?I [J IA}), where ~I is a finite systemthat satisfies the conditions 1-3 of T h e o r e m 5 (and A is an automaton with not less than two distinctly labelled initial states). THEOREM 15, For any n -~ 1 there exists a minimal system that is homomorphically complete in a class of initial automata and that consists of n automata~

Proof. If n=l, then {Do} will be such a system. Let n >io 91 - ~A~ ..... A~_l, A~} specified by their graphs (Fig~ 2)~ The initial states are marked

Let us consider a system of automata

by double cireleso

A direct verification shows that the system 91 satisfies the conditions 1-3 of Theorem 5. On the other hand, any proper subsystem 91~ = 91 -- {A~} of this system does not satisfy the condition 1 if i= i, .... n-l, and the condition 2 (and 3) if i=no Hence follows the assertion of the theorem~ LITERATURE

!o 2o 3. 4. 5o 6o 7. 8. 9~ I0~

CITED

V.M. Glushkov, "Abstract automata theory," Uspekhi Matematicheskikh Nauk, No. 5 (1961)o V.M. Glushkov, Synthesis of Digital Automata [in Russian], Fizmatgiz, Moscow (1962). A. Ao Donis, "The completeness problem in automata theory," in: Kibernetika (Donetsk Branch), No. I, Kiev (1970)o Ao Ao Donis, "Completeness conditions in a class of Moore automata," in: Issledovaniya po Algebre, Noo 2, Saratov State University- Press, Saratov (1970). Vo B. Kudrya~sev, "On the power of sets of precomplete sets of functional systems related to automata," in: Problemy Kibernetiki, NOo 13, Nauka, Moscow (1965)o A. Ao Letiehcvskii, "Completeness conditions for finite automata," Zhurnal Vychislitel'noi Matematiki i Matematicheskoi Fiziki, No. 4 (1961)~ A.A. Letichevskii, "Completeness conditions in a class of Moore automata," Materials of Seminar on Theoretical and Applied Cybernetics, No. 2, Kiev (1963). V.N. iled'ko, "On a class of compositions of automata," in: Teoriya A-vl,omatov, Naukova Dumka, Kiev (1966). M. Ao Spivak, "The problem of completeness in a class of Moore automata," Kibernetika, No. 3 (1968). Mo Ao Spivak, Introduction to Abstract Automata Theory [in Russian], Saratov State University Press, Saratov (1970).

407