T HE UN I V E R S I T Y O F M I C H I G AN COLLEGE OF LITERATURE, SCIENCE, AND THE ARTS Computer and Communication Sciences Department Technical Report MODELING AND SIMULATION: STRUCTURE PRESERVING RELATIONS FOR CONTINUOUS AND DISCRETE TIME SYSTEMS Bernard P. Zeigler with assistance from: Department of Health, Education, and Welfare National Institutes of Health Grant No. GM-12236 Bethesda, Maryland and National Science Foundation Grant No. GJ-519 Washington, D.C. administered through: OFFICE OF RESEARCH ADMINISTRATION ANN ARBOR April 1971

ABSTRACT This paper has established a basis for the formal treatment of modeling and simulation when continuous time system occur as elements of the basic simulation triad (i.e., either the system to be simulated, the model or the computer doing the simulating is a continuous time system). The key idea is that of constructively specifying a system in a way analogous to the use of the one step transition and output functions of the usual sequential machine formulation. This enables one to develop useful criteria for determining when one constructively specified system simulates or models another.

I. INTRODUCTION Recently, there have been a number of efforts toward a framework in which system models commonly distinguished along a digital-analog axis could be given unified treatment. Mesarovic [1] and Windeknecht [2], Zodeh and Desoer [3] have considered abstract formulations of systems theory. Kalman, Falb and Arbib [4] work with a more structured formulation which specializes more readily into the sequential machine and optimal control formalisms commonly employed. Wymore [5] has taken the first steps in considering the new applications areas made possible by a unified systems theory. These areas relate to systems containing components of both the digital and analog variety in which an adequate understanding of overall system operation can be better gained by treating such components and their interaction in a unified way. The utility of such a systems approach is most readily apparent in the consideration of hybrid computing systems but there are other important areas of applications such as in the digital simulation of continuous state models a,1nd t lhc design of asynchronous processors. In this paper, I shall be concerned with the formalization of a relation existing between two systems whereby the first might be said to be a "simulation" or "realization" of the second or the second might be said to be a "model" of the first. The basis for such a development has been laid in Zeigler and Weinberg [6] and Zeigler [7]. The former paper showed how the system theoretic concepts of homomorphism and coordinate aggregation could be usefully applied in actual computer simulation of biological systems. Zeigler [73 showed how a simulation could be regarded as a triple (system to be simulated, model, computer) in which a preservation relation holds between model and system (determining what properties of the system

are to be preserved in the model) at the same time that another preservation holds between model and computer (which governs the manner in which the model is implemented on the computer). The relations in question were formalized as structure preserving morphisms (with varying degrees of strength) and shown to be inclusive of existent notions of modeling and simulation. Complexity measures relevant to usage of time and space resources of a simulation were defined and their behavior under structure preserving morphisms studied with a view toward the construction of models with reduced complexity. The entities in a simulation (simulated system, model, computer) however, were taken to be automata - i.e., essentially discrete time systems, though continuous state spaces were allowed. The theory developed in this way presupposes a discretization of time which would be unnatural when applications to continuous time models and hybrid or analog computers are considered. Thus by extending the notions of "system" and the class of structure preserving morphisms which can relate systems, a more adequate Land applicable simulation theory can be developed. The plan of this paper is as follows: 1) A concept of system is developed which allows both continuous and discrete time operation. This is essentially based on Arbib's definition [8] which I feel to be much less clumsy than Wymore's [5]. 2) Behavior and function preserving morphisms are defined and studied for these systems. Behavior and function preserving morphisms are weaker than the structure preserving morphisms of [7] but are necessary prior elements in dealing with these stronger preservation concepts. There is not space in this paper to complete the connection. 3) A notion of. constructive specification of systems is developed.

This is a generalization of the usual sequential machine one step transition struct&~ formulation for discrete time systems. The great advantage afforded by such a specification is that it makes possible a practical procedure for constructing a system which will simulate or model another. This is analogous to the case of sequential machines where judgements concerning the behavioral relations of machines (involving extended operation) can be determined by examination of the single step transition and output functions. Constructive specification of continuous time systems involves difficulties which do not arise in the discrete time case. Much of the paper is devoted to providing reasonable solutions to these problems. 4) Examples are provided which give evidence for the applicability of the theoretical development. It is shown, for example, how Wymore's [51 results on the realization of discrete time systems by continuous time systems and simulation of continuous time systems by discrete time systems are more easily formulated in this framework.

II. SYSTEMS 2.0 System Definition A time invariant mathematical system thereafter called a system when the context is clear) is a structure S = <QQ,Y,6,X> where n is a set of input ssegments, Q a nonempty set of states, Y a set of outputs and 6:Q x Q + Q X:Q x Q + Y are the state transition function and output function respectively. The objects above must satisfy the following axioms: A.1 Structure of Q T denotes the underlying time set where T is either the reals R or the integers I. X denotes the input value set. A.1.2 (w is a function on a finite closed interval.) u e i => there are totl e T, to < t1 and w is a map w:[totl] + X. A.1.2 (Closure under Translation) w e a => for every Tr T there is an w' C f such that ': [tO+T,tl+T] 4 X and w'(t) = W(t'-T) for all t e [tO+T,t1+t]. w' is said to be a translate of w. Remark: From here on we do not distinguish between an input segment and any of its translates. More formally we define the equivalence relation - on Q where = W' <=> w' is a translate of w. An equivalence class [X] will be represented by any one of its members as is appropriate. For example, if we are interested in segments starting at some time to and write w we mean that segment in [w] defined on an interval [t0,-].

A. Z. 3 (CZosure under concatenation) w s Q and w' e Q~ => there is a segment ww' s ~, where if w: [to0tl] - X and ': [tl t2] X then ww':[t0,t2] X and is given by Wo'(t) = w(t) for t c [to,tl] = w'(t) for t C [tlt2] and T = R. For T = I the usual concatenation operation is assumed. Remark: With this condition ~ becomes a semigroup since as can readily be'verified concatenation is associative. A.2 Time Invariance For all w,w' ~ ~, q ~ Q w w' => 6(q,w) = 6(q,w') and X(q,w) = X(q,w'). Remark: This means that 6(q,w) and X(q,w) are uniquely determined once the state q and any representative w of the equivalence class [w] are given. As a consequence we adopt the same convention as in A.1.2, i.e., we let the context determine the particular translate of w which is of interest. This convention makes possible an enormous gain in notational manipulation; c.f., Wymore [5] and Kalman, et al. [4] who do not make use of this convention. Of course, it relies on a time invariant system formulation, but this is always possible to achieve by considering T as a state space component. A.3 Composition or Semigroup Property For all w,w' ~ ~, q e Q 6 (q,ww') = 6(6(qo),o') and X(q,ww') = X(6(q,w),w').

With w ~c represented by w: [O,T] - X we associate two segments wt] and w[t for every t e [0, T]. The left segment wt] = ][Ot]' i.e., the function w restricted to the subdomain [O,t]. The right segment w [t = J[t,] A system S = <R,Q,Y,6,X> is called input decomposable if in addition to A.1-A.3 it satisfies: A.4 Restriction Closure w C Q and w:[O,T] + X => I[t t'e] E Q for all 0 < t s t' < T. A.5 Consistency For all q e Q, 6(q,A) = q, where A is any translate of W[0,0]' the zero length input segment. 2.1 Time Discrete Systems A discrete time sequential system is a structure M = <X,Q,Y,=6 X > where X,Q,Y are nonempty sets of inputs, states and outputs respectively and M':Q x X + Q, X:Q + Y are the one step transition and output functions respectively. This is the usual Moore Machine except that no finiteness restriction is placed on X,Q,Y. We may associate with a discrete time system M a general system SM as follows:

10 SM = <,Q Y,, X> where Q is the translation closure of X+, -:Q x X+ + Q and A:Q x X+ Y are the extended transition and output function respectively defined by 6(q,s) = 6(q,s) for s c X 6(q,xs) = 6(6(q,x),s) for x c X+, and X(q,x) = AM(6(q,x)). Here X+ = {ww:{1,2,...,n} -+ X, n=l,2,... }, i.e., the set of all finite sequences of elements of X. The underlying time set has been assumed to be the integers I. Note that by the translation closure assumption each sequence x1x2..xn E X+ represents any of its possible translates in n The reader may verify that SM satisfies the axioms for a time invariant system,

2.2 Time Continuous Systems Before exemplifying a class of continuous time systems we need the following concepts: A system S = (QQY,6,A) defines trajectories through the state and output sets as follows: With each q c Q, X C Q there are associated segments STRAJ OTRAJ (q ) Choosing the representative w: [O,T] + X we have (q,w). STRAJ(q ):[0,] + Q given by STRAJ(qq) )(t) = 6(qwt]) for t ~ [0,T]; STRAJ (q,) is state trajectory associated with initial state q and input segment w. Similarly OTRAJ )' [0,T] + Y (q,w) is the output trajectory associated with initial state q and input segment where OTRAJ (q, t) = X(q,,w]) for t C [O,T]. Remark: It is easy to see that in the same way that w represents its translates in [w], STRAJ (q,) and OTRAJ(q w) also represents translation equivalence classes. A DifferentiaZ Equation Specified System, DESS is a structure

12 D = (C,Q,Y,f,N) where Q is a set of input segments satisfying A.1 with T = R and XTRm for some m > 1 Q Rn for some n > 1 YcRP for some p > 1 and f,N are maps f:Q x x - Q N:Q + Y Remark: Often D is presented in the form = f(q x) dt y(t) = N(q(t)). A time segment:[O,T] + Q is a state trajectory of D if there is an input segment w c Q2 and a (starting) state q ~ Q such that i) D(0) = q and ii) dt (t) = f ( (t), (t)) for all t c [O,T]. A segment Y: [O,T] -+ Y is an output trajectory of D if there is a state trajectory 0:[O,T] -+ Q such that P(t) - N(O(t)) for t ~ [O,T]. A DESS will be said to have unique solutions of given any q s Q, w E Q there is a unique state trajectory satisfying i) and ii), call it ~(q,,). Uniqueness of Q (qw) clearly implies uniqueness of output trajectory '(f.]

The following is well known from other approaches: 2.2 Theorem 1: Given a DESS with unique solutions D = (Q,Q,Y,f,N) we may associate with D an input decomposable system SD as follows: SD = (,QY,6,x) where for q s Q, w s Q2, t C T 6 (qmt]) = o(q,w) (t) X(qwt]) = t(qw) (t). Moreover SD represents D in the sense that it generates exactly the same set of trajectories, i.e., for all q C Q, w s ~f STRAJ(q,w) (= q,w) and OTRAJ (q,w) = Tq,w). An interesting subclass of the differential equation systems are the linear (time invariant) systems. A DESS D = (t,Q,Y,f,N) is Zinear if X,Q,Y are vector spaces and f,N are linear transformations given by f(q,x) = Aq + Bx N(q) = Cq The underlying differential equation takes the usual form 0o q = Aq + Bx. /The corresponding system SD = (Q,Q,Y, 6x) has t (qt]) = eAt + eA(t-t')B,(t,)dt;Lnel X (t' 'l)t]) (=C (,l,, t]).

14 III. MODELING AND SIMULATION RELATIONS 3.0 The Esscntial Difference Between.. Discrete and Continuous Time SysteMs It is important to note the essential differences between the two general classes of systems just mentioned. i, ~Aie s;;;. mc.,Aine case, the transition function 6 is determined by extending the given one-step transition function 6. Thus given an input string Sl)s...sn and a state q we can compute the trajectory ql,q2,... q where ql = q and for i = 1,2,...,n-1, qi+l = 6(qi,si). This step by step iteration is preciseZy the idea underlying digital computer simulation of systems. More explicitly, given two sequential machine derived systems SM and M SM, there are a number of criteria available for determining whether SM simulates SM, or whether SM, is a model of SM. This is done essentially by examining the one-step transition and output functions (6,X) given in by the M,M' specifications. In the continuous time case very few such criteria are unknown. We are reduced to having to compare the total system descriptions S and S' to determine whether S can simulate S'. To see the import of this, consider the case where we have two DESS's D and D' and wish to determine whether SD can simulate SD,. Since D,D' are known we can program an analog computer to simulate SD and SD, just as knowing M and M' we can program a digital computer to simulate each. In contrast to the discrete time case however, it is generally unknorwn how to use the structure of these programs (or equivalently the functions f,N) to determine whether SD can simulate SD,. This must be done by an

15 exhaustive generation and comparison of their trajectoriec. (The only exception to this I know of, concerns linear systems where one can determine behavioral equivalence from the similarity of the matrices A,BC.) The following sections present an approach to this problem within the system theoretic framework given above. The essential idea is consider continuous time systems which have enough of the properties of discrete time systems to enable the application structure preserving criteria already known in the latter area. 3.1 Basic Preservation Relations We begin by reviewing and generalizing known behavior and function preserving relations for systems. The input-output behavior of a system S = <Q,Q,Y,S,X> is the collection of functions {SIjqqQ} where for qcQ, qq + Y and is given by Sq(w) = X q,w) for all w C Q. A behavior preserving morphism from S to S' is a triple (hl,h2,h'n3) where hl: ' + h2:Q' -S Q h13:Y Y' such that for all qsQ', q= h3 aSh2(q)( hl' Remark: More expansively, let us say that 5' [PSq q(' divides Sq) using an input encoding map hI and an outpu..., map h if $' = h Oq~h1 Then the existence of a behavior morp:'..:, (;.,hi,h3) means that for each

16 state q'sQ' there is a state qcQ (namely h2(q')) such that X3'q 'q using (hl,h2). A function preserving morphism (homomorphism) from S to S' is a triple (g,h,k) where g:Q' 2+ h:Q1 + Q' (onto) k:Y + Y' where ij Q1 Q is closed under g (S'): W'a'.,qeQ1 => 6(q,g(W'))Q1 ii) for all qsQl, 'sQ' h(6(q,g(w'))) = 6'(h(q),w') and h(q)- ko qOg A behavior morphism will be said to time locaZ if hl:'Q' - is a semigroup homomorphism, i.e., for all ',W2E s', h1(W1W2) = hl(Wl)hl(W2). A function morphism is similarly designated if g:Q' -+ is a semigroup homomorphism. Remark: Time local morphisms are desirable since they enable input segments to be encoded by concatenating encoded subsegments. Their existence comes much easier for discrete time systems than for continuous time systems, as we shall see. 3.LlTheorem: The existence of a function morphism from S to S' implies the existence of a behavior morphism from S to S'. Proof: Let (g,h,k) be a function morphism from S to S'. Construct a behavior morphism (h1,h2,h3) as follows: Set h1 =g h = k, and define h2:Q' +- Q by h2(q') is a designated representative of the inverse image h-l(q') = {qlh(q) = q'}. Then h(h2(q')) = q' implies

q, = koBh (q)og [ii) of function morphism 2 condition] - h3h (q') hi A system S = <Q,Q,Y,6,X> is reduced if for all ql,q2sQ, Bq = Bq => ql = q2' 312 Theorem: The existence of a time local behavior morphism from S to S' implies the existence of a time local function morphism from S to S' if S' is reduced. Proof: Let (hl,h2,h3) be a time local behavior morphism from S to S'. Construct a function morphism (g,h,k) as follows: Set g = h k = h and define h:Q1 + Q' by a) Q1 = {qeQJ there is a q'cQ' such that $' q,l using h h$} q q h1h3 b) For qsQ1, h(q) = q' <=> B' |,Js Lemma: S' qtlq => S' IS(q )6 q 'q 6'(q',w') (q, g (w')) Proof: For all 1,,W2'cQ q' q' 2) => 3q 1 = h 2) > q' (W1W2) = h3 0q(h (W)h1(W2)) [hl is a homomorphism]:> X' (6'(q',W12) = h3oX(q,h1(l)hl (2)) => X'(6'(q',w1w2) = h30X(6(q,hl(Wl)),hl (2)) [composition property] => '6t(qUw )(W2) = h30 6(q,h ()) 1 h l(2) => Bl ~' 6' (q ',i) 6(q,hl (l))' Using the Lemma we see readily that Q1 is closed under g(r') as required. To show that h is well defined by b), note that if 3q, ' q and 3;, 1q we have 8q, = h3~q~h = 8,,. Since S' is reduced q' = q";.s is reiuireid. Next we show that (g,h,k) as defined above have t!;e requisite conmmlutative

18 properties. From definition b) of h, h(q) = q' => 8'l => h(q)lBq as required. Also by the Lemma, ', (q',w') I 6(q,g(w') So from definition b) of h h(6(q,g(ow'))) = 6'(ql,') = 6'(h(q),w') as required. Remark: That the homomorphisms of topological dynamics (e.g., Ura [9]) are special cases of the behavior morphism can be seen as follows: Let S be an autonomous input decomposable continuous time system, i.e., X is a singleton set. Since E2 now consists of all constant value segments, these segments are uniquely identified by the length of their associated interval. Thus we may set S = R; w + w' then represents the segment ww'. 6:Q x +- Q now satisfies the composition law: 6(qj, + w') = 6(6(q,w),w') and the consistency law 6(q,O) = q. Given two such systems, for time local function morphism (g,h,k) to exist, g must be a homomorphism of the real additive group R into itself. This result is the usual homomorphism of topological dynamics except that the topological structure of the state space may also be preserved. 3.2 Constructive Nature of Discrete Simulation For time discrete systems the ability to go back and forth between transition function descriptions and behavior descriptions can be significantly strengthened. Consider time discrete systems M = <X,Q,Y,6,X>. A function preserving morphism from M to M' is a triple (g,h,k) where g:X' - X+ h:Q1 Q' (onto) k:Y + Y' where Q1 Q'is closed under g(X') and for all seX',qsQl,(g,h,k) satisfy h(6(q,g(s))) = 6' (h(q),s)) and k(X(q)) = i' (h(q)).

19 3.2.1 Theorem: Let SM,SM, be systems derived from time discrete systems NI and M'. There is a function preserving morphism from M to M' if, and only if, there is a time local function morphism from SM to SM,. Proof: => Let (gMhM,kM) be a function morphism from M to M'. We construct a function morphism (g,h,k) from SM to SM, as follows: Set h = hM k = kM and define g: (X')+ - X+ by g(sls 2..s') = g M(S)g (S2)g n)(sI) for all strings s...sls in (X')+. g is the extension to homomorphism of semigroups of the function gM defined on the generators. Since (X')+ is a free semigroup this extension is well-defined Isl's...s = s... ns" implies n=m and s!=s" for all i=1,2,,...n]. Since g is a homomorphism as required (g,h,k) will be a time local function morphism if h(6(q,g(x'))) = 6'(h(q),x') and B'h(q) Bq using g,k. for all qCQl.x' (x')+. Using induction on Z(x') (the length of x') we can readily show that h(6(q,gM(s))) = 6'(h(q),s) for all ssX', qsQ1 implies h(6(q,g(x')) = 6'(h(q),x') for all x'l(X')+, qQ1 as required. Also the closure of Q1 with respect to g(X') readily implies the closure of Q1 with respect to g(X')+.

Finally, for all x'a(X')+,qeQ1, kog (x') = k(X(qg(x'))) [definition of?P,] = k(X(6(q,g(x')))) [definition of A] = ' (h(6(q,g(x')))) [definition of function Xv morphism] = X'(6'(h(q), x')) [definition of function l morphismQ = X'(h(q),x') [definition of X'] =' h(q)x') as required. <= Let (g,h,k) be a function morphism from SM to SM,. We construct a function morphism (gM,hM,kM) from M to M' as follows: Set h = hM k = kM and let gM:X' + X+ be the restriction of g:(X')* -+ X+ to X', i.e., g(s') = gM(s') for all s'EX'. The requisite properties now follow immediately.

IV. CONSTRUCTIVE SPECIFICATION OF CONTINUOUS SYSTEMS 4.0 Introduction We see from the Theorems of Section 3 that the ability to determine whether one system simulates or models another by examining their one step transition structures depends crucially upon the existence of certain properties of the input encoding map g:2' + Q. Namely - 1) g is a semigroup homomorphism and 2) Q' is generated by a smaller subset such that g need only be defined on this subset. In the case of discrete time systems these conditions are readily satisfiable. However, corresponding constructs for continuous time systems have been lacking. Thus the task now is to give a constructive specification for classes of continuous time systems analogous to that available for discrete time systems. From here on we restrict attention to state transition system S = <Q,Q,6> since we shaZZ be interested in function rather than behavior morphisms as appropriate for modeZing and simulation. 4.1 Maximal Length Segmentation Analogous to the case of discrete time systems we seek a generating set QG for Q with certain useful properties. Given a subset TS Q where A~T we designate by T+ the least set of segments containing T and closed under concatenation. It is easy to see 00 i i that T+ = U Ti where T {w1w2...wij icTj=l.,.. *i}. i=l T generates Q (T is a generating set for Q) if T+ = Q2. Members of T are called generators or generating elements. We shall say that W1,W2,.. en is a decomposition of w C a by T if 1 2 *** n

22 A set QG is an admissibZe set of generators if for all w C SG, if t* = max {tjwt] c QG} then wit, c QG Explanation: Refer to Figure 4.Llwhere Wt*] is the longest generator which is also a left segment of w. The condition for admissibility is that the remaining right segment W[t* must be generated by 2G. Examples of admissible sets are given in Section 4.2. Suppose now that -- Q. This means that for every element in n can be obtained by concatenating a finite number of generators. However, there may be more than one way to do this. That is, in contrast to the discrete time case G+ is not necessarily a free semigroup. To remedy this situation we do not try to force uniqueness of compositions but seek conditions guaranteeing a unique cannonicaZ decomposition of elements of Q in terms of generators QG' The requirement of admissibility is just such a condition as we now show: A decomposition WlW2,.,eWn of w by QG is said to be a maximaZ Zength segment (m..s.) decomposition if for each i s {1,2,...n} whenever there is an w' e QG such that w' is a left segment of w.w.ii. n then w' is a G z+l n left segment of Wi. In other words for each i,.i is the longest generator which is also a left segment of wwii+l... 1 +1 n 4.1.1 Assertion: If W has a m.Z.s. decomposition by QG it is unique. Proof: Let W1,W2,. Sw and w',w,...w' be m.Z.s. decompositions of w. Then W1 is a left segment of wj (since Wj is the longest generator which is also a left segment of w) and vice versa wt is a left segment of 1 So W1 = Wt. This establishes the basis for an induction hypothesis: X. = Wi for i < j => Wj+l = W+l the proof of which is straightforward. 1i 1 +1'

I< - x__- C *uo~lvzu~wOS tllfu~ -, - rx-EW LTO! Ian.:! m

4.1.2 Theorem: If QG is an admissible set of generators for.Q then every G w e f has a unique m.Q.s. decomposition by iG.o Proof: Refer to Figure 4.1.2. Let o c 2. Since QG generates ~, X = 1l2... m for some. G i=l, 2,...n. We wish to resegment X so as to obtain a m.k.s. decomposition w,w2,...w. Let us call the points to0tlst2P* Ott the break points of the decomposition W12.OZ'@2 'wn; i.e., t1 = t =1 ]'2 = [t lt2], etc. Let t{ be the greatest value of t such that wt] E QG. (t1 exists since all segments are defined on cZosed intervals.) Then t' is the first break point of the m.2.s. decomposition and W= ttW Since 2G is admissible, [t e QG 1 1 Note that t' 2 t > 0 since tl] 1 and l A. Let k be the integer such that tk < t' < tk (k=2 in Figure 4.1.2.) k- k+1' Now [t, is a proper right segment of X and we proceed to find the break point t' and a maximal length segment w2 of to Continuing in this 2 2 [t way we generate a sequence t{,tI,... which must terminate since if tz < t2 < tl+1 then ti > tk, etc. Thus, there is an integer m < n such that w',,w tm., is a m.k.s. decomposition of o. By the Assertion 4.1.l,it is unique.

'uoT:TSodmo:op 's'' ** o.UOUIws iVTZ!uI Z'I' * oIn2T ~4 I I 1 LI-0 v

24 4.2 Admlissible C;enlel;ators There are more transparent but also more stringent conditions that guarantee admissibility. 4.2.1 Proposition: Consider the following conditions: ') (Prefix property) W1 G QG and w1"2 ~ G e 0 2 = A (no generator is a proper left segment of another generator). ") No generator is a proper left or right segment of any ther. "') QG is closed under right segmentation. "") QG is closed under both left and right segmentation. Then ") => ') => G is admissible and "") => "') => SG is admissible. Proof: Left as an exercise for the reader. 4.2.1 Corollary: For discrete time systems M = <X,Q,6> the input symbols S are admissible generators. Proof: {ww:{l1}+X*X satisfies Proposition 4.2.1'. 4.2.2 Corollary: If Proposition 4.2.1' (the prefix property) holds then if WlW2,...,wn is a decomposition of w by QG it is the m.i.s. decomposition. We now give some examples of admissible sets. Example 1: Step Function Inputs Let at denote a constant real valued function on a segment of Zength t, i.e., at: [O,t] + R where at(t') = a for all t' s [0,t]. Then QG = {at ltR,aeR} is an admissible set of generators and generates the set a'{ tla a"...a(n) In = 1,2,3...}

25 Note that the segments at can have arbitrary length hence that essential use is being made of the continuous time base. That 2G is admissible follows from Proposition 4.2.1". Figure 4.2.1 shows three distinct decompositions of the same segment. The decomposition in a) is the m.i.s. decomposition. Note that there are infinitely many decompositions but only one m.k.s. decomposition. For this case of step functions the break points of the m.Z.s. decomposition are just the points at which step changes occur. Example 2: Pulse inputs The set QG {at0t t1 ]a#O,tlO} is admissible. This can be determined directly from the definition and does not follow from Proposition 4.2.1. See Figure 4.2.2. Counterexample 3: The set 2 = (a 0 lao t O)U (a 0 b a,b) is not G t t2-t1 ' 1 t Iis admissible since a 0 b is the m.Z.s. of a 0 b 0 but 1 2 1 3 2 1 t2-t t3t2 t4t Ot - L QfG. See Figure 4.2.3. Example 3: Fixed Interval Inputs Let T be any interval and let G RT; i.e., aG is any subset of the set of all functions with domain T. Then QG is an admissible generating set since Proposition 4.2.1' is satisfied. By Corollary 4.2.2, every decomposition is an m.Z.s. decomposition. A well known special case is where QG consists of a single segment w; then GI consists of finite length periodic functions. See Figure 4.2.4. Example 4: Piecewise Continuous Functions Let QG = {mIW:[ST] + R is a continuous function}. Then. = {>4 is a piecewise continuous function with a finite numSer of disccnti;~ K....

a aI - I to t '2 t3 (a) to tl t2 f3 t4 t5 (b), 2 to tl t2 t3 t1 t1 (C) Figure 4.2.1 Three distinct decompositions of the same segment. The m.Z.s. decomposition is shown in a).

i a a a O tj t2 0 tj 2 t3 t(a) (b) Figure 4.2.2 Generator shown in a) and generated segmnent shopwn in b).

I I I2 t3 t2 t5 Figure 4.2.3 Adding generator shown in 4.2.3 destroys admissibility of generating set.

0 - 2- 3r Figure 4.2.4 Periodic input segments.

26 That nG is admissible follows from Proposition 4.2.1"'. Note Example 1 is a special case of Example 4. Many other subsets of the continuous functions lead to admissible generators. 4.3 Some Properties of Admissible Sets We shall need the following results later on. For any decomposition W1,W2,., wn of w by %G let #(w) = n, the number of generators used. Let size(w) = n, where n is the number of generators used in the m.Z.s. decomposition of w by QG 4.3.1 Assertion: size(w) = min{#(w)} where the minimization is over all decompositions of w by G.' Proof: Follows from the proof of Theorem 4.1.2. The following is a consequence of the fact that segmentation by maximal length sequences is a "causal" operation. 4.3.2 Lemma: Let Q be an admissible set. G a) If WI2' I'n is a m.. s. decomposition for w' c SG then for any w' s;G n Aw 1 is the first part of a m.L.s. decomposition for V W b) Conversely, let w1,W2...Wn be a m.2.s. decomposition for w E nG. For any left segment wt]E G the m.1 s. decomposition of wt] is 1,2,... Proof: a) Refer to Figure 4.3.1 Clearly the maximal length segmentation of wt does not depend on n-1 w". [n=3 in the figure.] The segment Wn = lt] however may be subsumed by a new m.L.s. segment when adjoining a left segment of w".

I _-6-OJ i_ i - I - -- -" >- Figure 4.3.1 t3' is the new break point after concatenating w' with w".

27 b) Refer to Figure 4.3.2. Let m be the integer for which tm < t < t The segmentation of wt ] does not depend on [tlt This gives w 1] -m'W where W' w [t tl wl'2 M m m [tm, 4.3. 3 Proposition: Let QG be admissible and w ~ nG' a) size(w) > 1 b) size(w) = 1 <=> w e 0 G + c) X = w'w" for wzw" E nG => size(w) f size(w') + sizeCd") + d) w = W'w" for '4w" c SG => size(w') < size(w) Proof: a) A G- => size(w) > 1 b) For X E nG such that w: [O,T] - X, max{wtiwt E fG} = T. c) Refer to Figure 4.3.3. Let,w2,'..,w and 'x" w' W" be m. s. decompositions of t' 1' 2' p 1' 2'e F q and t" respectively; then X = o,...,wp '",...,to; (p=4,q=3 in the Figure). Lemma 4 a) tells us that p[,. p1 q ' Lemma 4.3.2 a) tells us that WIW,...w begins the m.l.s. decomposition of W. Since t' E QG and W", c 1 1 e Let wW,...,= S be the p G GS p 1 q G 2 r m.L.s. decomposition for wot'.. w". Then SW i the? 1 q p 2 -1 1 r m.L.s. decomposition of W. Thus size(o) = p-l+r. But by Assertion 4.3.1, r = size(w'w" t..") < l+q. p10 q So size(w) < p-l + l+q = p+q = size(w')+size(O"). Thus part c) is proved d) Note that size(wto') = p = size(w)+l-r. Now by b) r - size(w' o") = 1. 4.3.2 Proposition: Suppose Proposition 4.2.1', the prefix property holds. Then if...w is a m..s. decomposition for t' and 'w is a m.L.s. decomposition for 2" then o'j w', "." is a m.L.s. decomposition

' t sT;uTo.'-lxT q Oqtt 0otI7 lou SOOp ssoszo d uo!!TSodwooop s '*ut aotu 't;El >>Z:1; ouTS Z''V7 aicnTz. '.... c..... 7..... ''9

4e @1 3 me E 1 32 3 Figure 4.3.3 Size(w). SizeC(') + Size(w")

28 for W'W". Proof: Immediate from the discussion of Proposition 4.3.3. 4.4 Constructive Specification We shall want to define a one-segment transition function %:Q x G 2 Q in such a way that it can consistently be extended to QG. We proceed as follows: Given a set n of segments, a segment p (not necessarily in 2) is a right remnant if for some w c S, wQ s ~. A constructive specification is a structure G = <,Q, G> where QG is a set of generators Q is a nonempty set (of states) and 6G:Q x QG + Q is the one-segment transition function. QG must satisfy the axioms: C.1 AdmissibiZity QuG is an admissible set of generators C.2 CZosure with respect to right remnants p a right remnant w.r.t. G => P C SG 6G must satisfy the axiom: C.3 Internal composition For all w,w' s Q ' W G => 6G(q' w') = 6G(6G(qw)'wm') for all q c Q. Remark: If fG has the prefix property then C.2 is vacuously satisfied since there are no right remnants. On the other hand, if -G is closed with respect to right segmentation than C.2 is (more than) satisfied. Remark: Although they look similar, C.1 and C.2 are independent axioms. In ~Tt one can show:

29 4.4.1 Proposition: Let nG be closed under right remnants. n is admissible if, and only if, SG is closed under right remnants. Proof: Left for the reader. Remark: Given a system S = <SI,Q,6> we can generate constructive specifications as follows. Let SG be any subset of SI which satisfies C.1 and C.2. Let 6G be 6 restricted to nG, i.e., set 6G(q,w) = 6(q,w) for all q c Q, w e fG' Since 6 satisfies the composition axiom A.3, 6 will automatically satisfy C.3. Actually, if S is derived from a DESS wi&h unique solutions we need only solve the differential equation for the segments in fG to obtain dG satisfying C.3. Example: Step Responses of Linear First Order Lag System Consider G = <0GQ,6G> where nG = {at t~R,aeRl Q = R and 6G:Q x %G + Q is given by -t/T -t/T 6(q,at) = qe t/T+a-aet/ Since n is closed under right segmentation it is both admissible and closed under right remnants. Since 6G is derived from a DESS with unique solutions it is internally decomposable. Thus G is a constructive specification. 4.4.1 Theorem: Given a constructive specification G = <G,Q,6G> we can associate with it a system SG. <+,Q,6> where 6:Q x + Q is defined as follows: For w C nG, q e Q 6(q,w) = 6G(q,); for w e n~G q e Q 6(q,w) = 6(6 (qlw), 2... n)) where W1W2'...'Wn is the m.L.s. decomposition of w by fG' Note that W2'W3'h,,Wn is the m.L.s. decomposition for i..."n.

30 Proof: Since 6G is assumed to be time invariant, 6 will be time invariant. That 6G is well-defined follows from the uniqueness of the m. Q.s. decomposition. Thus we need only show that the composition property obtains, i.e., we must show that 6(q,w'w") = 6(6(q,w')w") for all w',w" C Ci. IWe proceed by induction on maxisize(w'), size(w",}. Basis: Max{size(w'), size(w")} = 1. By Proposition 4.3.2 a), b) size(w') = size(w") = 1 and wW'" c SG. Now by 4.3.2 c) size(w'w") < size(w') + size(w") < 2. If size(w'w") = 1 then w'w" c QG (by 4.3.2 a)) and by the internal composition of 6G we have 6 (q,w'w") = 6G (q, ' ") = G (6G (:C q' )' ") 6 (d (q,' ), w"). If size(w'w") = 2, refer to Figure 4.4.1. Let ii, be the m.Z.s. decomposition for w'w" and let u = w'd, so that IP = w". Since w'd s QG and W' E QG, p is a right remnant and by C.1, Now, 6(6(qw' ),w") = 6 (6 (q, '),O") [W'w" I G] G (6G (q" > ) Apes) [IWi" = bes] G( G ( 6G(qW') ' );) [p; W eG] =G( G(q,1'w),E)) [wuV C QG] GG( G(q'7) '~) [a') = ~] = (6 (q, ",w) [X ' ] ~G qG'"

31 For the induction step, assume 6(q,w'w") = 6(6(q,,w'w")) for max{size(w'), size(w"))} n. Let w w'"' where max{size(w'),size(w")1} n+l. Refer to Figure 4.4.2. Let w1,w 2,.,w be the m.Q.s. decomposition for.' where p s n+l. Let op begin the m.s.s. decomposition for wp w" and let w be the associated P right segment, i.e., wpw" = w p By Prop. 4.3.3c, l+size(;) e size(w') size(m) < size(w") < n+l. Let Up = Wpp; then since p is a right remnant p ~ fG. 6(6(qw'),w") 6(6(qw w2..w wP )'")),W =[,o 1 2 p.- p ] 6(6(6(q,w *.w 1)'pw),'w")) [size(w1 Owpl) S n and size(wp) = 1] 6(6(6 (q,wl...w 1 )' p) ')) [VW = (6(6(q,wl... _.1),,Op),) [wp e nG] = 6(6(6(q,wl*...p1),p) [p- = Wp] (6(ql***Wp. )6') [size(w... ) < n and size t 1] 6(q,w 1* *wp-lw3 ' =6 (q,w't ").* The next to the last line relies on the easily proved Lemma: If Wl@2,.,.,~n is the m.Q.s. decomposition for w then for i ~ {1,2,...,n-1) (/ (q,1l2... i)Wi+9l9...n)- 6(qw)

Z = (Ilm1r~) oz Is 'Gse at, Itj *,b ' tn2-t =1 _ I. I.; E=.0- m '.114- Im

OQ - CD (") F.I ili '..

32 V. MORPHISMS FOR CONSTRUCTIVELY SPECIFIED SYSTEMS 5.0 Definitions With the foregoing definition of constructively specified systems, we are ready to formulate a notion of simulation which retains the essential character of the discrete time idea. A function morphism from G = <GQ 6G> to G' = <,Q' > is a pair (g,h) where g G G h:Q1 + Q' (onto) and i) Q1 Q is closed under g(Q%) ii) h(6G(q, g(')) = 6(h(q),w')) for all w' s Q', q s Q1. RemarK: 6G:Q x G + Q is 8G extended to fG by the m.Z.s. definition of Theorem 4.4.2. Actually, to determine whether ii) holds we need only extend 6G to segments in g(01). If g is "size preserving", i.e., cg( )-cG then 8G need not be extended at all. A function morphism from SG to S' is a pair (g,h) such that g: ()G G W:Q1 -+ Q' (onto) where i) Q1 Q is closed under g((S) +) and ii) h(d(q,g'(a' )):= 6' (h(q),x' ). for all q C Q1i W' X (G)+

33 Generalizing Theorem 3.2.1 we have: 5.0.1 Theorem: There is a function morphism from G to G' if, and only if, there is a function morphism from SG to SG, Proof: => Let (g,h) be a function morphism from G to G'. We construct a function morphism (W,i-) from SG to SI as follows: Set h =h and define gj (01)'+ +' by and define g G by g(w) = g(wl)g(w2)... g(wn) where wl,w2,..., is the m.Z.s. decomposition of w C QG. First note that g is well defined because of the uniqueness of the m..s. decomposition. We use induction on size(w') to show that for all q Q1 h(6(q,g(w')) = 6 (h(q),' ). Basis: size(w') = 1 => ' SI'. Thus g(') = g(w) and the equality is just that given. Assume the equality holds for all w' such that size(w') = n. Let size(w') = n+l, and let w' W. ' be the m.k.s. decomposition L' 2= "' n+l for W'. h(6(q,g(wm (...w 1)) = ((q g(. g(n+l))) [definition of g] h(6(S(qg (w...) w*,g(*l)) [composition of 6] 6, (h(6 (q,g(w **.W )),W ) [size(+l.)=: ] ((sl1 nnl n'nos1.n f1 = 6'(6(h(q),w...w'),w41)l [size(w'...w)=n] =- q..w'') [composition of -6' = 6' (h~)I.. nW~~ nt~i

34 That Qi is closed under g(2')+ now follows readily from its assumed closure under g(Q). This establishes the forward direction. The reverse direction is immediate. Remark: In the foregoing theorem g is not necessarily a semigroup homomorphism of (W)+ to QG In general, we cannot expect g(ww') = g(w)g(w') since the m.2.s. decomposition for ww' is not simply the concatenation of those of w and a'. For example, let =G {= at.tsR,aeR} and let g:%G + QG be defined for some a,b,ceR where b # c by g(at) =.bt for t ~ [0,1] ct for t > 1 Then g(a,a 6) = g(a = g(a1.1 while g(a 5)g(a.6) = g(a )g(a6) = bb6 bl 5.0.1 Proposition: g:(Q' QG is a homomorphism <=> g(WW') = g(m)g(m') G - G for all w,w' E (s ) such that ww' e ~. Proof: Entirely analagous to that of Theorem 4.4.2. 5.0.1 Corollary: If Prefix Property holds for QG, g is a homomorphism. 5.0.2 Corollary: If the right and left segmentation closure holds then g is a homomorphism <=> g(ww') = g(w)g(w') for all w,w' ~ QG such that We shall now give evidence of the applicability of these concepts by considering some illustrative problems arising in modeling and siulation.

35 5. 1 Time and Amplitude Scaling for Continuous Time Systems a) Time scale change Let G = <>G,Q,6G> be specified as follows: G = {WjW is a real valued continuous function defined on a finite closed interval} 6G:Q x SG + Q is given by G (q' T]) =,(qa) (T) for all U] ~ QG. Here q )((0) = q and d and dt,t) = f((q) (t),w(t)) for t e dom w. The underlying DESS, D = (fG,Q,f) is assumed to have unique solutions. Since QG is closed under right segmentation C.1 and C.2 are satisfied. Also, since the underlying DE'SS has unique solutions we have C.3 satisfied (see the Remark following Proposition 4.4.1) thus G is a constructive specification. Let G' = <Q,Q,61> be specified by Q' =R 6':Q' x R + Q' is given by 6G(q, =] ) (q,w) (T) for all ~ ~ G.

36 Here '4(q (0) = q and ld d )(t) = f(CO(q)(t),(t)) for t E [0,T]. dt '(q,w); (t w) By the same argument, SG, is a system. Its rate of operation, however, is a times that of SG where a is a positive real number. 5.1.1 Theorem: (g,h) is a time local function morphism from G to G' where h:Q + Q' is the identity map and g 'G 'G is given by 'g C[O, ']') [O,CT] where a[o T](t) = W0[,T (t/a) for t e [O,aT] Proof: Since in this case Q = Q it is closed under g(CS). And since h is the identity map we need only show that for all q e Q, w[Ol] ~ fG. 6(q,g(w[O,T])) = 6'(q, [O,T]) Equivalently for-all T ~ R, s qU[oaT]) =,q,' [o, ] [O'a = 6' 0,T i.e., (q, t) = ' (q,w) (T).e., 4-T = 4' where T (t) = at for all t C R and ( q, 4, 4' = I' (qsw) t(qw) To show this we prove that b.Ta satisfies the differential equation for 4'.

37 1 d 1 d d(at) a dt ((Tt)(t) a d(t)b(at) dt Integrating the differential equation satisfied by 4: yields (t) =q + f (D (t'),(t'))dt' Thus dq, (st) d d(ot) = -d-~-~~~~:~`,,J(q f(*(t'),0(t')]dt'I = f(a(at),(act)) = f (.T (t) (t)) so ld dt (-OT )(t) = f&-Ta (t),w(t)). Also, O-T (0) = (0O) = q so A"T = ' by uniqueness of solutions. Finally, since SG is closed under right and left segmentation it is enough to show that g(ww') = g(w)g(w') for all w,w' C G such that ww' QG. But it is easily seen that ww' = w w' as required. b) Amplitude Scale Change 5.1.2 Theorem: Let G, G' above be such that f' (q,x) - af2(q/a,b) for fixed a,b E R. Then (g,h) is a time local function morphism from G to G' where h:Q + Q' and g: + G are given by h(q) = aq g (W) '; /1) where w/b(t) = w(t)/b for all t ~ dom w. Proof: An exercize for the reader. 5.2 Simulation of Continuous Time Systems by Discrete Time Systems Let G = <QG,Q,6^>, G' = <nQ,6Q> be discrete and continuous time

38 constructive specifications respectively. Let (g,h) be a function morphism from G to G'. Then g:-' -Q G G G Thus g is a mapping from functions with real domains into functions with integer domains; i.e., g must encode a continuous wave into a discrete one. Let nQ = {W' 1'. [O,T] - R}; then in general QG must have the cardinalitility of SI if a function preserving relation is to hold. Clearly this is impractical and it is interesting to examine cases where QG need be no more numerous than the real numbers. Example 1: Sampled Equispaced Step Functions (Figure 5.3.1) Of = {ahla s R} G = {aja e R} g:' + SG given by g(ah) = a Example 2: Sampled Arbitrarily Spaced Step Functions (Figure 5.3.2) '' = {at t ~ R,a e R} QG = {(a,t)Jt ~ R,a E R} g:~Q' + G given by g(at) = (a,t) Example 3: Band and.Time Limited Waves Let {ei i=1,2,...,n} be a finite set of functions e. i:T + R. For example {ei} might be a truncated Fourier series, Tchebychev polynomials, etc. Then, n G- {wl{ = Z c.e. for some c. E R, i=1,2,...,n} i=l i = R and g:'G '+ g is given by -~ n g(w) = clc2..Cn if w = Z c.e. -1l

suo!:oun, da:S pooz dsTnbg PoadureS I'~'S eanfT aipiJ 1 I i ~e...... 'J[ 7 a

suo~otun5dl doES pe3dS o~ qtraA poidutS Z'~u'S ao ni l '1: —. i1 1 I. V~~~~~~~~~~~~ (4:. X # 8$q) i

39 This describes a common situation in speech generation where discrete sequences of parameters characterizing a speech wave form are fed to a speech production device. 5.4 Realization of Discrete Time Systems by Continuous Time Systems With the formalism developed it is possible to characterize explicitly and simply the realization of discrete time systems by continuous time systems. The following shows how a two-state, two-input sequential machine may be realized by a set-reset flipflop with instantaneous feedback. The example may be readily extended to arbitrary finite state sequential machines and is presented as only one possible model for such realizations. The flipflop will be modelled as a DESS D = [(,Q,f) where Q = {atla C R,t e RI} Q=RxR and f:Q x R Q is given by f( ql,x) =-1ql-sgn( q2)+Z(sgn(ql),x) f(,x) ). l T [-q2-sgn(qi)-Z(sgnn(ql) X)J Here sgn(q) = 1 if q 2 0 = -1 if q < 0 and Z:{1,-1l} x R + {1,-1,0} is such that Z(x,O) = 0 for x c {1,-1}. Figure 5.4.1 displays an analog model of this network. It can be readily shown that D has unique solutions. Moreover, there are positive numbers a and p (related to the system time constant T) such that for any input of the form xOp,

Lii:6 j Figure 5.4.1 A set-reset..umip flop realization of a two-sat c;;.,e. -~~~~~~~~ of a two-$~at~ "~.;~;.'.c!~ino.j

40 6(q1q2 Xa0op ) ( qlq2,x0p) (o+P) = (Z(sgn(ql).,x),-Z(sgn(q1),x) Here x C {1,-l}. In other words, the final state of the flipflop after a pulse of width a followed by a p-length quiescence is completely determined by the polarities of the initial state and pulse. 5.4.1 Theorem: Let G' = <{l,-l},{l,-l},6'> be a discrete time sequential machine. There is a continuous time constructive specification G such that G' is a time local function morphic image of G (i.e., G realizes G'). Proof: Let G = <>,Q,6 > be obtained by extraction from the flipflop DESS above. Specifically, let = (1 0 -1 0 1 G a p' a p Q = Rx R and let 6G:Q x fG +Q be defined by 6G((qlq92),xo0) = (Z(sgn(ql),x),-Z(sgn(ql),x)) where Z(y,x = '(y,x) for all y,x ~ {1,-1}. Since EG has the prefix property C.1 and C.2 are satisfied and C.3 is vacuously satisfied. For the function morphism (g,h) from G to G' let g:{l,-l} -+ {l 0 -1 0} be given by g(x) =x 0 op' p op Let Q1 = {(l,-1),(-1,1)} R x R and define h:Q1 +-Q' by h(y,-y) = y for y s {l,-l}. The reader may verify that Q1 is closed under {l(Op,-1 0p}.

41 Next for (y,-y) E Q1 h(6G((y,-y),g(x))) = h(G ((y,-y),x O0)) =h (Z (sgn (y), x),-Z (sgn (y),x)) =z (y,x) = 6' (y,x) = 6'(h(y,-y),x). Finally, since G' is a discrete time system g is extendable to a semigroup homomorphism of {1,-1}+ to {l Op,-lo 0p Remark: By expanding nG to the set =G {X 0 Tx e {1l,-l},1t,, RI G ti t2-tl2.'' one can study the degradation of the sequential machine realization when badly timed pulses are used.

42 REFER IENCES 1. Mesarovic, M. (1968) "Auxiliary Functions and Constructive Snecification of General Systems," Math. Systems Theory, 2, 203-222. 2. Windeknecht, T.G. (1967) "Mathematical Systems Theory: Causality," Math. Systems Theory, 1, No. 4. 3. Zadeh, L.A. and Desoer, C.A. (1963) "Linear Systems Theory," McGraw-Hill. 4. Kalman, R.E.; Falb, P.L.; Arbib, M.A. (1969) Topics in Mathematical Systems Theory, McGraw-Hill. 5. Wymore, A.W. (1969) "Discrete Systems and Continuous Systems," in Advances in Math. Systems. Theory, P. Hammer, Editor. 6. Zeigler, B.P. and Weinberg, R. (1970) "System Theoretic Analysis of Models: Computer Simulation of a Living Cell," J. Theoret. BioZ., 29, 35-56. 7. Zeigler, B.P. (1970) "Towards a Formal Theory of Modeling and Simulation. I," University of Michigan Technical Report 03296-5-T. Submitted to J.A. C.M. 8. Ura, T. (1968) "Local Isomorphisms and Local Parallizability in Dynamical Systems Theory," Math. Systems Theory, 3, No. 1.

3 90111111111 03II27 6024 3 9015 03527 6024