INTERACTING AUTOMATA UDC 519.713.2

A. N. Chebotarev

Compatibility of interacting partial nondeterministic automata is defined. Two interacting automata are compatible if an input signal from one automaton always induces a defined transition in the other automaton.

INTRODUCTION Finite automata are widely used as a mathematical model of operation of many discrete systems. These include various regulators, control systems, processor control units, control components of algorithm and program models, etc. All these systems interact with the environment in the process of their operation. Thus, control systems interact with the controlled plant, the processor control unit interacts with the operating unit, the program control component interacts with the data component, etc. The information about the behavior of the environment also can be often defined in the form of an automaton. Then the interaction of the discrete system with the environment may be analyzed by considering the interaction of two automata. Two interacting automata form a system in which the inputs and outputs of one automaton are connected respectively with the outputs and inputs of the other automaton. Whether or not the automata (one or both) are partial has an essential impact on the behavior of this system. If the interacting automata are partial, we have the problem of ensuring correct joint operation of the two automata, i.e., eliminating cases when the input signal received from one automaton produces an undefined transition in the other automaton. This problem arises in discrete system design and it can be stated in the following terms: using information about the environment, design a discrete system so as to ensure correct joint operation of the system and the environment. The notion of correct interaction of automata in the course of their operation is refined and formalized by introducing the concept of mutual compatibility and compatibility of interacting automata. Compatibility is a property of the cyclic composition of automata that defines the appropriate mode of interaction. We consider some issues of compatibility analysis of automata and propose an analytical procedure for synthesis of automata from a given specification that characterizes the behavior of both the automaton and its environment. In general, automata describing the behavior of the discrete system and the environment are nondeterministic. The nondeterminism is a consequence of incompleteness of information about the operation of the objects described by the automata. The specification of the automaton being designed usually defines a whole class of automata, and the design problem focuses on the construction of a particular automaton from this class. The information about the environment restricts the choice of the representative automaton from this class in compliance with the compatibility requirements of the corresponding automaton models. It is therefore desirable to have a method for identifying in the set of all automata that satisfy the specifications a subset of automata that are compatible with the environment. An automaton is then chosen from this subset without further consideration of the environment specifications, by applying optimality criteria of the synthesized automaton. The nondeterminism of the automaton model of the environment essentially complicates the solution of the first of these problems. In our paper, we solve the problem for the case when the interacting system is modeled by an automaton with finite memory. This restriction of the class of automaton models does not particularly limit the applicability of the results, because most realizations of discrete systems described by automata are in fact constructed in the class of finite-memory automata. An

Translated from Kibernetika i Sistemnyi Analiz, No. 6, pp. 17-29, November-December, 1991. Original article submitted October 12, 1990. 810

1060-0396/91/2706-0810512.50

©1992 Plenum Publishing Corporation

,,x

x

(

(x)

a

Fig. 1

Fig. 2

d ~ Fig. 4

Fig. 3

fxy/

®

Cxy)

®

k.L) ~*'

(s ~)

(igJ

~5~

.X

Fig. 5

Fig. 6

811

essential property of these automata is their cyclicity, i.e., nonexistence of deadlock states where the automaton stops. As a result, these automata can continue functioning for an infinitely long time. Most real systems have this property, in particular a system with initial and final states may be assigned to this class of automata if there exists a signal (emitted by the environment) that takes the automaton from the final state to the initial state or if all input signals take the final state to itself. 1. MAIN DEFINITIONS

Definition 1. A finite nondeterministic Moore X-Y-automaton A is the 5-tuple (X, Y, 9.1, XA, /*A), where X, Y, 9~ are finite sets of input symbols, output symbols, and states, respectively; XA: ~ × X - + 2 93and/~A: 2 ~ Y are everywhere defined transition and output functions. If there exist x E X and a E ~ such that XA(a, x) = Z , then the nondeterministic Moore automaton is called partial. If ]X I = 1, then the automaton A is called an autonomous Y-automaton. The transition function of this automaton has the form XA: 2( --~-293. Let x i E X, Yi E Y, a i E 9~ (i = 1,2 ..... k). Definition 2. The input-output word (X × Y-word) l = (x 1, Yl)-. i(Xk, Yk) is acceptable for the nondeterministic Moore X-Y-automaton A if there exists a state word aoa 1.... a k such that for any i = 0,1 .... ,k - 1 we have ai+ 1 E XA(ai, xi+l), P'A(ai+l) = Yi+l" Any state word that satisfies these conditions is called corresponding to the input-output word I. We say that the word (xl, Yl)..-(Xk, Yk) is acceptable in the state ao of the automaton A if a corresponding state word starting with the state a o exists. The definition of acceptability of an X × Y-word is extended to superwords (infinite words): a superword (xl, yl)(x2, Y2)... is acceptable if and only if any initial section of the superword is acceptable. For an autonomous Y-automaton, we consider acceptable Y-words and superwords. Definition 3. A nondeterministic X-Y-automaton A = (X, Y, ~[, XA, /~A) is called cyclic if for each a E 9A there exist al, a 2 E 9~ and xl, x 2 E X such that a 1 E XA(a, xl) and a C XA (a z, x2). To describe the interaction of automata, we introduce the concept of cyclic composition of automata. Let A = {X, Y, 9~, XA, #A) and B = (Y, X, ~3, XB, ~13) be partial nondeterministic Moore X-Y- and Y-X-automata, respectively. Definition 4. The symmetric cyclic composition of the automata A and B (denoted A o B) is the autonomous nondeterministic Moore Z-automaton C = (Z, ~, Xc, #c), where Z = X × Y U Y × X, ~ = 9.1 × ~ U ~ × 9~, and the transition function Xc and the output function/~c are defined as follows. For all a E ~, b E Xq (a, b) = {(b, al) l al E Za (a, IxB(b))}, 'Xe(b, a) = {(a, b 0 1bl E XB(b, lXa (a))}, IXc (a, b) -----(~tA(a), I*B(b)), ~c (b, a) = (lxe (b), ~a (a)). We see from this definition that the transition graph of the automaton A o B is a bipartite graph with transitions from states in 2 x ~i' to states in ~ × 2 , and conversely. Consider the Z-word l of length 2k which is acceptable for the automaton A o B. This word has the form (xl, Yl)(Yl, x2)(x2, Y2).-'(Yk, Xk+l) or (Yl, Xl),(xl, Y2)(Y2, x2)--'(xk, Yk+l), where x i E X, Yi E Y (i = 1,2,...,k + 1) and it is representable as a pair of words (p, q) of length k formed respectively from all odd and all even symbols of the word I taken in the same sequence in which they occur in 1. It is easy to see that each word from this pair is acceptable for an automaton for which it is an input-output word. LEMMA 1. If (p, q') and (p, q") are words of even length acceptable for A o B, then the words q' and q" differ only by the second component of the last symbol, i.e., a symbol of the output alphabet of an automaton for which q' and q" are input-output words. The proof follows directly from the form of the words p and q. The above definition of cyclic composition is symmetric with respect to the automata A and B, and this property is reflected in its name. In applications, it is helpful to have two additional cyclic compositions, which are unsymmetric with respect to the automata A and B. One of these compositions is called a right cyclic composition and the other a left cyclic composition.

812

Definition 5. The right cyclic composition of the automata A and B (denoted A-eB) is the autonomous nondeterministic Moore Z-automaton C = (Z, 6, Xc,/Zc}, where Z = Y × X, (g = !8 ~< ~, and the transition function Xc and the output function/*c are defined as follows. For all a E 9/, b E 2~ ;¢c fb, a) -- {(b'i a')l b' E x8 (b, ~*A(a)), at E ~A (a, [213(b'))},

Fc (b, a) = (Ix~ (b), IXA (a)).

The left cyclic composition is defined similarly (symmetrically to the previous definition). Both right and left cyclic compositions are uniquely constructed from the symmetric cyclic composition. We use A * B to denote any of the previously defined cyclic compositions. LEMMA 2. A l - A, Bj - B imply (A l * Bl) - (A * B), where - stands for equivalence of automata [1]. The proof easily follows from the definitions of the concepts entering the lemma. The maximum cyclic subautomaton of the automaton A * B is called the core of the corresponding cyclic composition. To define compatibility of interacting automata, we need first to define the concept of determinization of a nondeterministic automaton. Definition 6. Any maximum deterministic subautomaton of the nondeterministic automaton A is called a basic determinization of the automaton A. By the maximality condition, any basic determinization of the automaton A has the same state set as A° Definition 7. The maximum cyclic deterministic subautomaton of the cyclic nondeterministic automaton A is called the basic cyclic determinization of the automaton A. The following proposition is easily proved. LEMMA 3. Any basic determinization of a cyclic automaton has a nonempty cyclic subautomaton. Thus, to any basic determinization of a cyclic automaton A uniquely corresponds a basic cyclic deterrninization of the automaton A, which is the maximum cyclic subautomaton of the basic determinization. Definition 8. A basic determinization of any automaton equivalent to the automaton A is called a determinization of the automaton A. We similarly define the notion of cyclic determinization of a cyclic nondeterministic automaton. We see from the definition that the set of all determinizations (cyclic determinizations) of the automaton A is countable, because the set of all automata equivalent to A is countable. Alongside determinization of automata, we also consider determinization of transitions. Definition 9. A transition from state a under the action of an input signal x in a nondeterminisfic X-Y-automaton A is the triple (a, x, XA(a, x)). A transition from state a in the autonomous nondeterministic Y-automaton A is the pair (a, xA(a)). A transition is called nondeterministic if

Ixm(a, x)l

> 1

(IXA(a)l > 1) and deterministic if [XA(a, x) I = 1

(IXA(a)[ = 1). A determinization of the transition (a, x, xA(a, x)) is the transition (a, x, a'), where a' E Xn(a, x). Every basic determinization of the automaton A may be obtained by replacing each transition of the automaton A with some determinization of this transition. Definition 10. Two cyclic partial deterministic Moore X-Y- and Y-X-automata are called compatible if their symmetric cyclic composition has a cyclic subautomaton. Definition 11. A partial nondeterministic cyclic Moore X-Y-automaton A and a partial nondeterministic Moore Y-Xautomaton B are mutually compatible if each cyclic determinization of the automaton A is compatible with each cyclic determinization of the automaton B. Definition 12. A partial nondeterministic cyclic Moore X-Y-automaton A is compatible with a partial nondeterministic cyclic Moore Y-X-automaton B if there exists a cyclic determinization of the automaton A compatible with each cyclic determinization of the automaton B. The last definition is important for design problems in the following sense: if A is a partial automaton being designed and B is the automaton characterizing the given environment for A, then A must be compatible with B.

813

2. COMPATIBILITY T H E O R E M S In this section, we present some results that take us from nonconstructive definitions of compatibility to constructive definitions, which may be used to construct practical algorithms that analyze automata for compatibility. These results were obtained for the case when both automata A and B are automata with finite memory. Definition 13. A nondeterministic X-Y-automaton is called an automaton with finite memory of depth 6 if for any acceptable input-output word (x 1, yl)(x2, Y2)...(xk, Yk) of length ~_6 and any two corresponding state words ao'al'...a k' and ao"al"...ak" the states a k' and ak" are equivalent. For each X-Y-automaton A with finite memory of depth 6 and each natural 81 _ 6 we can construct an X-Y-automaton equivalent to A such that for any acceptable input-output word of length 81 all the corresponding state words end with the same state and for different input-output words of length t31 these states are different. This automaton is called a 61-normal form of the automaton A. In the fl-normal form of a cyclic automaton, there is obviously a one-to-one correspondence between acceptable input-output words of length 61 and states. Let A and B be respectively X-Y- and Y-X-automata with finite memory, and A* and B* their f-normal forms (f _> max(6A, /~B)). LEMMA 4. The automaton A o B has a finite memory and A* o B* is its 26-normal form. The proof is obvious. T H E O R E M 1. A partial nondeterministic cyclic X-Y-automaton A with finite memory is mutually compatible with a partial nondeterministic cyclic Y-X-automaton B with finite memory if and only if the symmetric cyclic composition of the automata A and B has a cyclic subautomaton whose state set is closed with respect to the transition function of the automaton AoB.

Proof 1. We will first show that the existence in A o B of a cyclic subautomaton whose state set is closed with respect to the transition function of the automaton A o B implies that each cyclic determinization of the automaton A is compatible with each cyclic determinization of the automaton B. Let A 1 and B 1 be arbitrary automata that are respectively equivalent to the automata A and B. Since A 1 o B 1 - A o B (Lemma 2), A l o B 1 has a cyclic subautomaton C 1 whose state set is closed with respect to the transition function of the automaton A 1 o B 1. Now let A l' and B 1' be basic determinizations of the automata A 1 and B 1 and A1* and Bl* the corresponding basic cyclic determinizations. Denote by (A 1 o B1)' the basic determinization of the automaton A l o B 1 that is identical with A 1' o B 1' and by (A 1 o B1)* the corresponding cyclic determinization. It is easy to show that (Aj o B1)* is identical with the core of the cyclic composition Al* o BI*. Since A 1 o B l has a cyclic subautomaton whose state space is closed with respect to the transition function of the automaton A 1 o B1, we see by Lemma 3 that the determinization (A 1 o Bl)' also has a nonempty cyclic subautomaton, and therefore Al* o BI* has a nonempty core. Thus, the automata AI* and B1* are compatible. Since A1* and BI* are arbitrary cyclic determinizations of the automata A and B, then by Definition 11 the automaton A and B are mutually compatible. 2. Let us now prove the converse proposition: if A o B does not have a cyclic subautomaton whose state set is closed with respect to the transition function of the automaton A o B, then there exist incompatible cyclic determinizations of the automata A and B. Two cases are possible: a) The automaton A o B does not have a cyclic subautomaton. It is easy to note that in this case any basic cyclic determinizations of the automata A and B are not compatible. b) The automaton A o B has a cyclic subautomaton and the state set of any cyclic subautomaton of the automaton A o B is not closed with respect to the transition function of this automaton. Let fA be the depth of the memory of the automaton A, fiB the same for B, f = max(f A, fB), and let A* and B* be/~-normal forms of the automata A and B. By Lemma 2, A* o B* is equivalent to A o B, and therefore the state set of any cyclic subautomaton of the automaton A* o B* is not closed with respect to the transition function of this automaton. Thus, there exists a basic determinization (A* o B*)' of the automaton A* o B* without a cyclic subautomaton. We will now show how to construct basic determinizations of the automata A* and B* so that the symmetric cyclic composition of the corresponding basic cyclic determinizations does not have a cyclic subautomaton. To each transition in the automaton A* o B* corresponds a transition in one of the automata A* or B*. Thus, to a transition from the state (a, b) of the automaton A* o B* corresponds a transition from the state a of the automaton A* induced by the input signal/~B,(b), and to a transition from the state (b, a) corresponds a transition from the state b of the automaton B* induced by the signal /XA.(a). A determinization of a transition in the automaton A* o B* uniquely defines a determinization of the corresponding transition in the automaton A* or B*. This, however, is insufficient in order to construct 814

from a basic determinization of the automaton A* o B* basic determinizations of the automata A* and B*, because the same transition in the automaton A* or B* may correspond to several different transitions in the automaton A* o B*. Let Cl* be the subautomaton of the automaton A ~ o B* generated by its core. LEMMA 5. If (a, hi) and (a, b2) are states of the automaton CI* and b 1 ~ bE, then/~B.(bl) ~ /ZB.(b2). Proof By Lemma 4, to the states (a, bl) and (a, b2) correspond different Z-words of length 2t5 that are acceptable for A* o B*. Let the word l 1 = (.Pl, ql) correspond to the state (a, bl) and the word l2 = (P2, q2) correspond to the state (a, b2). Since A* is a &normal form of the automaton A, then a unique acceptable input-output word of length t5 corresponds to the state a. Hence Pl = P2. The word l 1 ends with the symbol (/Zg.(a), p.B.(bl)) and the word l2 ends with the symbol (#A.(a), tzB,(b2)). Since l 1 ;~ l2, then by Lemma 1 /zB.(bl) ;e #B,(b2). Q.E.D. An assertion similar to Lemma 5 also holds for the states (b, al) and (b, a2) of the automaton CI*. Thus, different transitions in the automata A* and B* correspond to different transitions in the automaton C1". The sought determinizations A' and B' of the automata A* and B* are basic determinizations in which the determinizations of the transitions corresponding to transitions in the automaton Cl* are defined by the determinizations of the latter in the automaton (A* o B*)', and the determinizations of the remaining transitions are arbitrarily defined. It is easy to see that for these determinizations the symmetric cyclic composition of the corresponding basic cyclic determinizations does not have a cyclic subautomaton. Thus, the determinizations A' and B' are not compatible. This concludes the proof of Theorem 1. Q.E.D. T H E O R E M 2. A partial nondeterministic cyclic automaton A = (X, Y, 9~ , XA, /~A) with finite memory is compatible with a partial nondeterministic cyclic automaton B = (Y, X, 2~ , XB, /~B) with finite memory if and only if the symmetric cyclic composition of the automata A and B has a cyclic subautomaton whose state set is closed with respect to transitions in the automaton A o B from the state set ~ × 9~. Proof 1. We will show that the existence in A o B of a cyclic subautomaton whose state set is closed with respect to transitions in A o B from states in ~ × 9~ implies the existence of a determinization of the automaton A which is compatible with all determinizations of the automaton B. Let 6A, 6~, and 6 be as defined in the proof of Theorem 1, and let A* = (X, Y, 9.I*, XA*, P'A*) and B* = (Y, X, ~*, XB*,/~B*) be &normal forms of the automata A and B, respectively. Since A* o B* - A o B, we conclude that A* o B* has a cyclic subautomaton whose state set is closed with respect to transitions in the automaton A* o B* from states in ~3" × ~*. By Lemma 5, each determinization of transitions from the core states of the automaton A * o B* that belong to the set ~* × ~3" defines a set of basic determinizations of the automaton A* and thus also a set of its basic cyclic determinizations. Take a determinization of these transitions in the automaton A* o B* such that the resulting automaton (A * o B*)' has a cyclic subautomaton whose state set is closed with respect to transitions in (A* o B*)'. Let A' be a cyclic determinization of the automaton A* that corresponds to the chosen determinization of transitions in the automaton A* o B*. The cyclic composition A' o B is identical with some subautomaton of the automaton (A* o B') ' that contains its core. Therefore, A' o B* has a cyclic subautomaton whose state set is closed with respect to transitions in A' o B*. By Theorem 1, the automaton A' is mutually compatible with the automaton B* and it is therefore compatible with each cyclic determinization of the automaton B*. Since the sets of cyclic determinizations of the automata B and B* are identical, the determinization A' of the automaton A is compatible with each cyclic determinization of the automaton B. 2. We will now show that if the automaton A o B does not have a cyclic subautomaton whose state space is closed with respect to transitions from ~ x 9.I, then there exists a cyclic determinization of the automaton B which is not compatible with any cyclic determinization of the automaton A. Let A* and B* be as in part 1 above. We can choose determinizations of transitions from the core states of the automaton A* o B* in such a way that by replacing these transitions with their determinizations we obtain an automaton (A* o B*)' without a cyclic subautomaton. Determinizations of transitions from the core states of the automaton A* o B* define the set of basic cyclic determinizations of the automaton B* such that the symmetric cyclic composition of each of these determinizations with the automaton A* is identical with some subautomaton of the automaton (A* o B*)'. Let B' be one of these determinizations of the automaton B*. The automaton A* o B' does not have a cyclic subautomaton, and therefore any determinization of A ", and thus any determinization of the automaton A is not compatible with B'. This completes the proof of Theorem 2. Q.E.D. Necessary and sufficient conditions of mutual compatibility and compatibility of automata formulated in Theorems 1 and 2 can be easily restated in terms of unsymmetric cyclic compositions. Thus, the corresponding propositions for the right cyclic composition are stated as follows. Let A and B be automata that satisfy the conditions of Theorems 1 and 2. i. The automaton A is mutually compatible with the automaton B if and only if A~oB has a cyclic subautomaton C' such that any state (b, a) of this subautomaton satisfies the following condition: for each b I E xB(b, /~A(a)) and each a I E XA(a, /xB(bl)) the state (bl, al) is contained in the state set of the subautomaton C'. 815

2. The automaton A is compatible with the automaton B if and only if A ~ B has a cyclic subautomaton C' such that any state (b, a) of this subautomaton satisfies the following condition: for each b 1 @ XB(b, /zA(a)) there exists a I @ Xh(a, /ZB(bl)) such that (bl, al) is contained in the state set of the subautomaton C'. These propositions can be applied to construct algorithms that analyze mutual compatibility and compatibility of automata using a different definition of closed state for each problem and each form of cyclic composition. As an example, consider an algorithm that analyzes the automata A and B for compatibility using the notion of right cyclic composition of automata. Definition 14. The state (b, a) of the right cyclic composition of the automata A and B is closed if: 1) XB(b, /~A(a)) = ~l or there exists b' E XB(b, /zA(a)) such that XA(a, /ZB(b')) = ~i; 2) there exists b' E ×B(b, /~A(a)) such that for each a' E XA(a, /~B(b')) the state (b', a') is closed. The algorithm constructs the set of all closed states of the right cyclic composition of the automata A and B. If the set of all closed states is identical with the set of all states of the composition, then A is not compatible with B; otherwise A is compatible with B. Example. Consider the automata A and B shown in Figs. la and lb, respectively. Their symmetric cyclic composition is shown in Fig. 2 and the right cyclic composition in Fig. 3. We see from Fig. 2 that the automaton A is compatible with the automaton B (there is a cyclic subautomaton with the state set {ld, lc, 2c, cl, c2, dl} which is closed with respect to transitions from !8 × 9~); the automaton B is compatible with the automaton A (there is a cyclic subautomaton with the state set {la, 2b, a2, bl} which is closed with respect to transitions from 9/× ~); however, the automata A and B are not mutually compatible (there is no cyclic subautomaton whose state set is closed with respect to transitions in A o B). Let us consider how right cyclic composition can be used to decide compatibility of automaton A with automaton B. Successively construct the set of all closed states ("propagating" the closed states). By part 1 of Definition 14, states la and 2a are closed. Then using part 2 of Definition 14 we obtain that states lc and 2c are closed. There are no additional closed states. Since the set of all closed states is not identical with the set of all states of the composition, automaton A is compatible with automaton B. 3. PRACTICAL METHODS OF COMPATIBILITY ANALYSIS OF AUTOMATA In this section, we consider the analysis of compatibility of a partial nondeterministic cyclic Moore X-Y-automaton A with a completely defined nondeterministic cyclic Moore Y-X-automaton B for the case when A and B are automata with finite memory. The proposed approach does not require constructing the cyclic composition of the automata and produces a simpler algorithm than that in Sec. 2. The approach relies on a number of new concepts and related results.

Definition 15. A left X-shift of the X × Y-superword l

= (x1,

yl)(X2, y2)(x3, Y3)-" is the superword ,~x

-- (x2,

Yl)(X3, Y2). . . . Let A be a cyclic X-Y-automaton and L A the set of all its acceptable X × Y-superwords. T H E O R E M 3. There exists a cyclic X-Y-automaton A~- for which the set of all acceptable X × Y-superwords is identical with ~'~ L A --- ~i x I i E LA}. The theorem is easily proved by constructing the automaton A-. Any such automaton is called a left input-shift of the automaton A. Note that not all left input-shifts of the automaton A are equivalent. Let B = (Y, X, 58, XB, ~B) be a cyclic Moore Y-X-automaton with finite memory of depth/t. T H E O R E M 4. There exists a cyclic Moore Y-X-automaton ~B with finite memory of depth 5 which is a left inputshift of the automaton B.

Proof The automaton

= {Y, X, ~, XV, t~g) is defined as follows:

---{(b,y)IbE~3&yEY&zB(b,y)=/= IZi}, %y((b,y),yl) ---816

={(b,,h,O!bi~7~B(b,y)&;~(bi, y~)V=iD},

btg((b,y))=txe(b).

We will show that L~ = k~. B 1. Let l = (Yl, Xl)(Y2, x2)(Y3, x3)'-, be an acceptable Y x X-superword for Y, which corresponds to the state superword bob~b2. . . . We will show that the Y × X-superword (Y2, Xl)(Y3, x2).-- is acceptable for B and the corresponding state superword is (bo, yl)(b~, Y2). . . . Indeed, ~*~-((b i, Yi+l)) = #B(bi) = xi (i = 1,2 .... ). Since the superword l is acceptable for B, we have bi+ 1. ~ XB(bi, Yi+ 2) and XB(bi+ 1, Yi+2) ;~ lgl (i = 0,1,2 .... ). Thus, by definition, Z.ff (b~+l, &'+2) E X~-((bi, &-~ ), &+2)

for all i = 0,1,2,....

2. Let 7 = (Y2, Xl)(Y3, x2)(Y4, x3)-., be a Y × X-superword acceptable for B , which corresponds to the state superword (bo, Yl')(bl, Y2') . . . . We will show that the Y × X-superword l = (y', Xl)(y2, x2).., is acceptable for B and the corresponding state superword is boblb 2. . . .

Indeed, by acceptability of ~- for B

it follows that (bi+2, Yi+2') E

7.~- ((bi, Yi+l'), Yi+2) and >~- (bi+ 1, Yi+2') = Xi+l (i = 0,1,2...). Therefore, from the definition of X~- and lu~- we have Yi+2' = Yi+2, bi+l E XB(bi, Yi+l') and/XB(bi+l) = xi+ 1 (i

=

0,1,2 .... ). Thus, l is acceptable for B and l is its left Y-shift.

It remains to show that B is an automaton with finite memory of depth 6. Let I = (Y2, Xl)...(Y6+l, xa) be a Y x X" " b tt word of length 6 acceptable for the automaton B and (bo' , yl)(bl', Yz)...(bcs' , Ya+~) and (bo " , yl)(bl", Yz).-.t 6 , Ya+l) two gb " corresponding state words. We will show that the states (b6', Y6+l) and ~ 6 , Y6+1) are equivalent, i.e., the sets of all

acceptable Y x X-superwords in these states are equivalent. Let (Y6+2, X6+l)(Y6+3, x6+2)'" be an arbitrary (acceptable for continuation of 7" to the superword 1% . By paragraph 2 in the first part of the proof, the Y × X-superword (Yl, Xl)(Y2, Xz)...(y6, x~)(ys+l, xa+l).., whose left Y-shift is ~ is acceptable for B and it has two corresponding state superwords bo'bl'...ba'ba+ 1r... and bo"b I 1,... b~"~" u6+ 1" .. " " The state superwords b6' b6+l '... and bo"ba+ l ' . . , correspond to the superword (Ya+l, x6+l)(Y~+2, x6+2) . . . . By paragraph 1 in the first part of the proof, the state superwords (b6', y~+l)(ba+l', ys+2)o.. and (ba", y6+l)(b6+l", Y~+2).-. correspond to the superword (Ys+2, x6+I)(Y6+3, x6+2) . . . . Thus, the superword (Y~+2, xa+l)(y~+3, xa+2).., is acceptable both in the state (b6', Ya+l) and in the state (b6", Ya+l)- This completes the proof of Theorem 4. Q.E.D. The automata A and B are called weakly equivalent if L A = LI3. We know (for instance, from [2]) that for cyclic automata with finite memory weak equivalence implies equivalence. Thus, for each cyclic automaton B with finite memory there exists a unique Cup to equivalence) left input-shift with finite memory. In what follows, when we talk about left input-shift for an automaton with finite memory, we mean an automaton with finite memory. Our approach to compatibility analysis of automata uses yet another form of composition of automata, which we call parallel cyclic composition. Definition 16. The parallel cyclic composition of the automata A = (X, Y, 9I, XA, /*A) and B = (Y, X, ~, XB, /~B)(denoted by A ]]B) is the autonomous nondeterministic Z-automaton C = ( Z , g, Xc,/~c), where Z = Y × X, g = ~ × 91, and the transition function Xc and the output function/xc are defined as follows: for any a, a' E 9I and b, b' E 2}., (b', a') E Xc(b, a) if and only if a' E XA(a, /,B(b')), b' E xu(b, #A(a')), #c(b, a) = (/xB(b), ixn(a)). Let A = (X, Y, 91, XA, #A) be a partial nondeterministic cyclic Moore X-Y-automaton, B = (Y, X, ~, XB,/~B) a completely defined nondeterministic cyclic Moore Y-X-automaton with finite memory, and B a left input-shift of the automaton B constructed by the rules from the proof of Theorem 4. THEOREM 5. The core of the automaton D = A]l ~ is contained in a subautomaton isomorphic to the automaton

C = Ao-~B. Proof Let oe be an injective mapping of the state set of the automaton C to the state set of the automaton D, defined as follows: for any b E ~3 and a E 91 , a(b, a) = ((b,/~a(a)), a). First note that the mapping ~ preserves the state labels, because/,c(b, a) = >o((b, /~A(a)), a) = (/~u(b), /*A(a)). 1. We will show that (b~, a 1) ~ xc(b, a) implies c~(b~, a~) ~ XD(C~(b, a)) = XD((b, ~A(a)), a). From Definition 16, ((b 1, /xA(a0), as) ~ XD((b, ~a(a)), a) if and only if al E~A (~'.ILL~-" (hi, ~'~A(al))) = ~A (a, ~.~B(hi))

(i) 817

and (ba, IxA(aO) E X~- ((b, ~A (a)),

[~A (al))"

(2)

From the definition of Z~- (2) holds if b 1 E xa(b, /zA(a)). On the other hand, (bl, al) E Xc(b, a) implies that b 1 E XB(b, /zA(a)) and a E XA(a, /ZB(bi)). Thus, (bl, al) E Xc(b, a) implies c~(bl, al) E XD(CX(b,a)). 2. We will show that ((bi, y), al) E XD((b, /zA(a)), a) implies that y = /zA(al) and a - l ( ( b l , /zA(al)), al) E Xc(a-l((b, /za(a)) , a), i.e., (bl, al) E Xc(b, a). From ((bl, y), al) E XD((b, /zA(a)), a) we obtain that al E ~A (a, ~ - ((hi, y)) = ~A (a, ~ and (bl, y) E XF((b , /zA(a)), #A(al)). From the definition of XF

(b0)

(3)

y = /zA(al) and

bl EX~ (b, ~A (a)).

(4)

From (3) and (4) it follows that (bl, a l) E xc(b, a). We have thus proved isomorphism of the automaton A '~ B and a subautomaton of the automaton A From the proof in part 2 we also see that any state of the automaton A IIB of the form ((bl, y), al) such that y ~ /~h(al) is unreachable from any other state of the automaton A II B. Therefore, the subautomaton of the automaton A II f f isomorphic to A ~.B contains the core of the automaton A II B. This completes the proof of Theorem 5. Q.E.D. Example Continued. Figure 4 shows the automaton "B, which is a left input-shift of the automaton B (Fig. lb). The parallel cyclic composition A If F is shown in Fig. 5. In this figure, we can easily identify a subautomaton isomorphic to the right cyclic composition of the automata A and B (Fig. 3). Theorem 5 implies that in analyzing compatibility of the automaton A with the automaton B we can replace the <--. composition AoB with the composition A I1 B, which as we shall see is much easier in some cases. To this end, we introduce an appropriate definition of a closed state in terms of the automata A and B. For the Moore Y-X-automaton B, we denote xu(b) = U y E y xu(b, y) and by x[XB(b)] we denote the set of all states in xu(b) which are labeled by the symbol X. Definition IZ The state (b, a) of the parallel cyclic comopsition of the automata A and B is called closed if 1) there exists x E X such that x[x~(b)] :4= ~ and XA(a, x) = ~ ; 2) there exists x E X such that all states from XAI~(b, a) whose first component is a state from x IXF (b)] and the second component is a state from XA(a, x) are closed.

II'-B.

The automaton A is not compatible with the automaton B if and only if all the states of A I1B are closed. However, there is no need to consider all the states of the automaton AII B : it suffices to consider only the states that belong to the subautomaton of the automaton A II B generated by its core. Definition 18. The X × Y-word (xl, yl)...(Xk, Yk) and the Y x X-word (Yl', xl')'"(Yk', Xk') are called conjugate if t t xi = xi , Yi = Yi for all i = 1..... k. Let A* and B* be b-normal forms of the automata A and B , respectively. The state a of the automaton A* and the state b of the automaton B* are called conjugate if they correspond to conjugate input-output words of length ~. Clearly, all states of the subautomaton of the automaton A* II B* generated by its core are pairs of conjugate states. Thus, it suffices to consider only pairs of conjugate states. There is one-to-one correspondence between the conjugate states of the automata A* and B*, and thus the cardinality of the set of all pairs of conjugate states does not exceed the cardinality of the state set of the automaton A. There is no need to construct the parallel composition of the automata A* and B*, and it suffices to consider the states of the automaton A* together with the conjugate states of the automaton B* (if such exist). Let 95* and ~* be the state sets of the automata A* and B*., respectively. The state a E 95* is caUed partial if there exists x E X such that XA.(a, x) = ~ . Now the algorithm based on "propagation" of closed states reduces to successive removal of partial states from the set 95" by the following rule. The partial state a E 95* is removed from 95* if: a) ~* does not contain a state which is the conjugate of a, b) there exists b' Ez~(b) such that ;~a (a, ~t~ (b')) = ~ , where b is the conjugate o f a . After each removal of partial states, new partial states appear, for which the issue of removal is again considered. The process is continued until either all the states from 95* have been removed (in this case, A is not compatible with B) or no new

818

candidates for removal remain. If the set of remaining states is nonempty, the automaton A is compatible with the automaton B.

In conclusion, some remarks concerning practical implementation of the last algorithm. Let A be an X-Y-automaton with finite memory of depth 6. Definition 19. The partition p on the set of all X × Y-words of length _>6 acceptable for A is said to be compatible with the state set of (the same or some other) X-Y-automaton A' with finite memory if: a) all words from each class of the partition O are either acceptable or unacceptable for A'; b) if all words of the same class of the partition p are acceptable for A', then all the corresponding state words end with the same state of the automaton A'. Definition 20. An automaton with finite memory of depth 6 is called quasireduced if there exists a partition p on the set of all acceptable input-output words of length 6 of this automaton which is compatible with its state set. The 6-normal form of the automaton A is obviously a quasireduced automaton. Let A and B be X-Y-automata with finite memory of depth 6A and 6B respectively, and 6 = max(tA, 6B). Definition 21. The automaton A is called quasireduced relative to B if there exists a partition p on the set of all X × Ywords of length 6 acceptable for A which is compatible with the state sets of the automata A and B. A Y-X-automaton also may be used as B. In this case, compatibility of the partition p with the state set of the automaton B is defined by considering the conjugates of the input-output words of the automaton A. In the compatibility analysis algorithm for the automata A and B, it suffices to consider the automaton A* which is equivalent to A and quasireduced relative to B or an equivalent automaton. For the automaton A (Fig. la), such is the automaton A* shown in Fig. 6. The number of states in this automaton may be substantially less than in the 6-normal form of the automaton A. Thus, the automaton in Fig. 6 has seven states, while the 6-normal (6 = 3) form of the automaton A has 22 states. The proposed algorithm is particularly useful when the automata A and B are defined by formulas of first-order predicate calculus that express the properties of acceptable input-output superwords [3]. With this specification, the transition from the automaton B to B is trivial, and one procedure removes partial states by rules a) and b). Example Continued. Let us consider the execution of the algorithm when the input data are the automata A* (Fig. 6) and B (Fig. 4). For these automata, the pairs of conjugate states a r e a 1 - ly, a 2 - ly, b~ - 2 7 , b 2 - 17 , c 1 - 2 y , ca - ly, d - 17. Here the conjugate states are the states corresponding to the same class of the partition O on the set of all input-output words of length 3 acceptable for A* which is compatible with the state sets of the automata A* and "B. The original automaton A* has only two partial states a 1 and a2'. Both are removed by rule b). Once a 1 and a 2 are removed, b I and b 2 become partial states. They are also removed, making d a partial state. Its conjugate state is 17. All states from X'~ (17) are labeled x. However, the transition from d under the action o f x is defined, and therefore d is not removed. As there are no other partial states, the algorithm stops. LITERATURE CITED .

2. 3.

V. Mo Glushkov, Synthesis of Digital Automata [in Russian], Fizmatgiz, Moscow (1962). I. K. Rystsov, "On weak equivalence of automata," Kibernetika, No. 4, 30-34 (1990). A. N. Chebotarev, "Functional design of automata," in: Intelligent Software for Information/Computing Systems [in Russian], Inst. Kiber. ira. V. M. Glushkova AN UkrSSR, Kiev (1990), pp. 12-17.

819