THE U N I V E R S I T O F M I C H I G A N COLLEGE OF LITERATURE, SCIENCE, AND THE ARTS Computer and Communication Sciences Department SYSTEMS SIMULATEABLE BY THE DIGITAL COMPUTIjER Part 1: Discrete Event Representable Models Bernard P. Zeigler The Logic of Computers Group and Department of Applied Mathematics The Weizmann Institute of Science Rehovot, Israel April 1977 Technical Report No. 199 with assistance from: National Science Foundation Grant No. DCR71-01997 Washington, D.C.

SYSTEMS SIMULATEABLE BY THE DIGITAL COMPUTER Part 1: Discrete Event Representable Models* by Bernard P. Zeigler Department of Applied Mathematics Weizmann Institute of Science Rehovot, Israel This work was partially supported by NSF Grant No. DCR71-01997.

SYSTEMS SIMULATEABLE BY THE DIGITAL COMPUTER Part 1: Discrete Event Representable Models Contents Page Abstract Introduction 1 Useful Admissibly Generated Sets 5 DEVS Encodability of Segments 8 System Simulation By Discrete Event Models 13 Realistic DEVS Simulation 22 Example: A DEVS Simulation 31 Appendix 1: Review of Input Set Related Concepts 36 Appendix 2: Relation Between Homorphisms and Simplicity 41 Appendix 3: The Event Relation 43 Appendix 4: Review of System Specifications and Morphisms 45 Appendix 5: Equivalence of DEVS System and Specification Morphisms 47 Appendix 6: Finite DEVS Limitations 48 References 51

ii Abstract. Discrete Event System Specifications (DEVS) formalize the concepts underlying discrete event simulation languages. More broadly, they embody the fundamental constraint of digital computer simulation that a model state can be updated only a finite number of times in a finite interval of time. This constraint, together with the fact that in the cases of paramount interest, the computer is given a network, rather than a global, system specification, limits the class of systems which can be faithfully simulated by a digital computer. In this paper, we formulate a notion of DEVS simulation and characterize the class of systems simulateable in this manner. In a subsequent continuation study, we shall show how the present formulation embodies both the above mentioned constraints and leads to a network level characterization of digital simulateability. The given characterization provides a canonical means of discrete event model construction and an example, drawn from a large scale simulation study is given to illustrate its applicability.

SYSTEMS SIMULATEABLE BY THE DIGITAL COMPUTER: Part 1: Discrete Event Representable Models Introduction. A fundamental constraint on digital computer simulation is that the sequentially acting computer can update a model state only a finite number of times in a finite interval of model time. Discrete'time, including automaton, formalisms embody this. constraint in the form of an assumed underlying fixed time step. Asynchronous model formalisms relax the latter constraint, but do not explicitly represent the computer's ability to control the time step size. Discrete event formalisms (Zeigler, 1976) however, embody a continuous time base and formalize the scheduling of model updates realizable by discrete event simulation languages such as SIMSCRIPT, SIMULA, etc. The advantages of such formalisms in terms of conceptual expression and computational efficiency have been previously noted (Zeigler and Barto, 1977; Hogeweg, 1975; Babich et al, 1975). In this paper, we initiate the characterization of systems simulateable by discrete event models, which we take to represent the maximum capability of digital simulation. To do this, we must recognize that in the cases of paramount interest, the computer is given only local descriptions and composes these to generate global behavior. It is the combination of the finite update and local description constraints that limits the class of systems faithfully simulategjle by digital computer (Zeigler, 1976, Chapter 5). In the (present) first part of this work, we formulate discrete event simulateability from a local point

of view in such a way as to facilitate the more general network characteriz&ation: to. be given: in Part 2. We. Wr.efy:pon system theoretic conepts previo;u.s.ly developed (Zeigle-r:, 1976, Chapters 9 & 10).' Fore convenience, these are briefly outlined in Appendices 1 and 3.. In particular, the notion of iterative system specifi4catio.n has been defined in order. to characterize 'thee computer'.s ability to 'ite-ratively generate a model's -state. and output traj. ectori.es, given a deq.ompositio..n of its received input segment into a sequence of finite length generators. The disc-rete event system specification (DEVS) was. developedL as a special case of the iterative.speciffication concept.. Rougqhly:, in a EEVS., external events arrive according to the finite number per finite interval rule. These cause the sc-heduling and res:cheduling of internal eventis which effectuate jump-like state transitions-. Between succ-essiv ive events.,..o activity tak:es place. Thus the natural DEVS i.nput generators are finite length segments. consisting either of no events, or of one event arriving at the beginning. of the segment. In this paper, we show that under a realistic encod.ing.:tion, the DEVS gen.erator sets canonically represent the fl1 class of: a*sslhle generating sets for iterative specification. The encodding:o!f input time functions into DEVS segments thus involves identifying exvent t.imes (s.egmentation points) and event names (characteristics of the enclo.s'ed segments). Moareover, the fact that admissibility is also shown to be necessary for:DEVS encodability, reduces the study of DEVS simulation of arbitrary systems to that of DEVS simulation of itteratively specifiable $ystems.

We then proceed to define an appropriate morphism for DEVS simulation and characterize the class of iterative specifications simulateable in this way. Besides giving the necessary and sufficient conditions for DEVS simulateability, this characterization has as a practical side effect, a canonical procedure for constructing discrete event models for systems satisfying the prerequisite conditions. The efficacy of this approach was demonstrated in the design of a spatially structured ecosystem model (Zeigler, 1977) whose running time efficiency brought the study of such systems well within feasible limits (this feasibility contrasts strongly with the simulation time requirements of the original system of differential equations). An example drawn from this simulation model is given here. The DEVS simulator keeps track of a model's state, but can update it at only external and internal event times. Internal events are scheduled according to predicted boundary crossing of model state trajectories. Necssary conditions for DEVS simulateability are thus shown to require autonomous operation of the model between successive external events and the existence of a partitioning of its state space which enables admissible segmentation of the state trajectories. Realistic restrictions on DEVS simulation over and above the essential finite update constraint, are paralleled in corresponding restrictions on the DEVS simulateable systems. But the basic principles for converting models to DEVS form are shown to remain unchanged. It is of theoretical interest to point out non DEVS simulateable systems since these establish inherent limitations on digital simulation. While we have not been able to construct such counter-examples in the

4, unrestricted case, we do show here that the integrator (perhaps the most si.rp.e c-ontin.ous system) is not s.uim.teable by finite dimensional discrete event systems. This is a satisfying result in not contradicting the basic presupposition underlying all numxneical tnethods of differential equation solution, but the inability to extend this result to the unrestricted DBVS case remains a puzzle. It should be noted that non-DEVS simulateability of the integrator dQe-s not imply the same is true for differential equation systems, which are integrators connected by in s tantaaeo.us -;f unctions. As indicated, the present treatment deals with DEVS simulation at the system level. The internal-external event distinction which we make here is however, crucial to the characterization of DEVS simulation at the network level. At this level, the constraint on local description of models for computer simulation may be formulated, as will be shown in Part 2, (Zeigler, In Preparation).

5. USEFUL ADMISSIBLY GENERATED SETS We develop examples of admissibly generated sets which will be useful in the sequel. 1. Discrete Event Segments DEVS See Appendix 1. 2. Cover Generated Segments Let Q c (X,T) be a semigroup closed under right and left segmentation. A cover of X is a family T of blocks (subsets) whose union is X; is a finite intersection cover if every subset of every block of 7T is contained in at most a finite number of blocks of f. By range (w) we shall mean the set {w(t)/O <t < (w)). For each subset B of X, define B { w/w C, range (w) c B) i.e., rB is the set of segments w of Q, whose values at points in the interior of dom(w) lie in B. Let I be the union of the FB, B E X Proposition 1. r admissibly generates r Proof. Let ww=1,w 2.. w each w. E rP. Then range (W1) is included in at least one B in T. By the finite intersection property range (w) is included in at most a finite number of sets B1,...,B in. For each m i= l,...,m, we claim t*(Bi) =max{t/range (Wt>) c Bi} exists. To see this let s1 s2'< s3.. be a sequence with s = P(c1) such that either a) for some j, sj = sj+ = sj+2=... and for no t > s. does range (Wt>) C Bi, or b) for all j, s >sj, and range (w ) c B. j+l J 41> 1

6. If a) holds, then s = t*(Bi) Otherwise b) holds and we have a strictly increasing sequence in a fini-te interval, dornm-(f),which must accumulate to some s from below. We claim s= Z.u.b.{t/range (wt>) c Bi.} since for t > s, range (t>) ~ Bi [s is an upper bound on the sequence in b)] and for t< s, there is some.- tk>t in the sequence, so that range (Wtt) C range (wt> ) B. Now if range (W>) Bi then there is k1 some t, O< t<s, such that w(t) ~ B.. But then there is a t' t< t'< s, such that range (wt,>) P Bi, a contradiction. Thus t*(Bi) =s. Now it is-easy to show that max{t/wt> E P }= max {t*(Bi)}. More — i=l,...,m over, r is closed under right segmentation, so the conditions of: Theorem 1, Appendix 1, sufficient for admissibility, are satisfied. Denote Q =-r. Then Q = {w E al there exists a finite set {tlt n ' 1 t2 tn_l<t t= Z(W), such that for i=l,...,n there is a B. eC for which w(t) E B. for t < t t2 Segments in Q are said to be re-generated. These trajectories have the property that they remain in blocks of 7T for non zero durations. A non rr-generated segment, on the other hand, is infinitely oscillating with respect to Xf in the sense that for each B C it there is a convergent sequence tlt,t I3,.. such that- w(ti) is not in B for all i, Or W (ti) is alternately in B and not in B Example. Let (X,T) be (R,R) (R denotes the reals). Let..b 2< b_- < b0< bl< b.. be a countable sequence of "threshold"' or 2 l 0 1 2 "quantization" levels. Let if be the cover whose blockS are B = [b,bil (where if the series terminates on the left at bg then Bg1_= ('b,] b and similarly, for the right). Let f2 be the piecewise continuous bounded

7. segments which are finitely oscillating in the sense that for each -1 x E range (w), w (x) consists of a finite number of isolated points and/or intervals. Then Q =- Q Note that F has been defined in reference to a semigroup Q. If 7T we denote this situation by r (Q), then I' (S) = F (X,T) n Q. 3. Polynomial and Analytic Generated Segments For (X,T) = (R,R), let F be the set of all finite degree polynomials. Then r are the piecewise polynomial segments. Let C be the segments m which are differentiable at least to order m, and let r =C NF rC Then r D r D F1lD r2...F rF = F is a strictly decreasing chain of admissible generating set for r. Break points in a mks decomposition by r are m points at which polynomial segments of finite degree are patched together, so that at most the first m-l derivatives agree. Thus "events" for decomposition by Fr are jumps in the function value; by Pl these are jumps in either function value or in derivative, etc. Now let r be the set of segments analytic on their domains. Then r is the set of piecewise analytic segments; w, i and wi E r implies that p is the unique extension of m to <Z(w),R(w)+Z(p)> and the breakpoints of a decomposition by F are points at which analytic continuation is impossible. (See Veech, 1967, Chapter 1.)

DEVS EN:CODABIILITY OF SEGMENTS From.now on., all segment sets will.be:a-.ass-umed to be.closed under (rigiht and left) segmen.tation.. Let g.:Q' -S. be, an encoding.. To avoi.d tr.ivi:ality, we will require that g- be O.nto in what.follows. Let QG admis-sibly genera~te Q. We say that g preserves right segmentation at..breakpoints:sif wheneve;r s is the. first breakpoint in the mls de.composition of g (w); then g(w <MATCH ) = g(w) By induction..on:the size.of g(w), i.t can be.seen that the above property holds for all breakpoints of- g.(w). if it holds for the first. We say the g is simple if 'it is invertable and preserves right segmentation a.t breakpoints. In Appendix 2 we show. 'that under reasonable conditions, invertability and homomorphism. implies' simplicity, but the conversse is.not true. This is important to note since-most of the useful encoldings are not homomorphisms but yet ta):e the weaker form of simplicity. The fo.lowing proposition shows that for a segment set to be simply encodable by an admissib.ly 'generated set, ft:must.itself be admissibly generated. Proposition 2. Let. g.:Q' siP> 2 and let QG admissibly generate e:. Then -1 r g (QG) admissibly generates Q'. Moreover, if G is a nontrivial G G generating set, so is P Proof: Let w E Q' and g(w) E Q. Let the breakapoints of the mls decompositic

9 of g(w) be {tl t2.. t }. If this set is empty then g(w) E QG so w E r ~ So assume it is not empty. We show that the set -1 -1 {MATCH (t),...,MATCH (t )} forms the breakpoints for a mls decomposition 1 ' n of w by '. First, w MATCH ( E Q' by left segmentation closure. WMATCH-l t )>' By Lemma A.2, g(MATCH- g(t). Since tl is an mls MATCH lCtl)> tl> breakpoint, g(t) E Q and so 1 E o For t > MATCH (t!) t> G MATCH (tl)> MATCH(t) > t (monotonic property) and since wMATCH-l(tl)> is a left 1s a lefMATCH (t )> segment of wt>, we have g(w) is a left segment of g(t)> (Lemma A.2). If to E r,then g()MAC(t)> and t is not an mls breakpoint as assumed. Thus MATCH (tl) willbe the first mls breakpoint in the decomposition of t by F provided we can show that such a -1 decomposition exists. (Note that tl < z(g(o)) so MATCH (tl) < () and toMATCH -l~ ) is a proper left segment of w, thus F is nontrivial if MATCH (tl )> QG is nontrivial and g is onto.) But w -l E Q' by right G <MATCH (t segmentation closure, and g(w -1 ) = g(t) since g is simple. < MATCH (t ) We continue the induction for i =2,..,n-1, in this way, substituting o<MATC-1l(t ) and g(w)<t for t and g(t) respectively, thus obtaiping D< MATCH-(t.) <t -1 i 1 MATCH {t,...,t } as breakpoints in the mis decomposition of o by F Q.E.D. Applying this result to the case of DEVS segments yields Theorem 3. -! Let g:Q' QDEVS be a simple encoding. Then r = g (rDEVS) nonDEVS DEVS trivially admissbly generates Q' O and w E rC Fg() = x where x g(a t>)(0) for all t E (O0,(t)) and T = MATCH(Z(a)) Proof. -1 Since F admissibly generates,2 we have that F = g (F DXEVS "DVS

admissibly generates 2' by Proposition 2. 10 Now for w E r, g(w) = x rX U. Since g is invertable T X T = MATCH(Z(w)), and also g(w ) = ()MAT t)> (x) (t t:> MATCH(t)> T MATCH(t)> xC(t Q.E.D. The theorem indicates that in a simple encoding into DEVS segments, the code of a generator w is determined by its initial portion no matter how small we take that portion to be. This leads us to define the relation on Q', where - w' ~= (3 t > 0) (W = t> o t> t> which turns out to be an equivalence relation. (Reflexivity and symmetry are obvious. For transitivity, note that wt = and t' = a" t> t> T> T> implies w W=' where a min{t,T}.) {j> Cy> Called the initial segment relation, = partitions segments into equival, 0 classes, each sharing a common initial segment in the limit of small t In Appendix 3, we consider the characterization of this fundamental relation for interesting segment sets and note the striking connection to analytic functions. The- degree of coarseness which imposes on a set of generators r 0 determines a lower bound of information which must be lost in encoding r into DEVS segments. This is evident in the following corollary of Theorem 3. Corollary 4. Let g:Q sim QDEVS Define - on Q, by w = wo' g(M) =g(w') DE~VS. g g Define on Q by tw I'v (3 t>O)(g(t )(0) (0) 0~g o,g '>~t> -1 a. ' O4* X _ and Q((o) -_ 9(w') mg 0,g b. t: -( - W W 0,g -1 c. --, - and ' are equivwlenice relations on g (I'DEVS) g 1,g (.) DEVS

11. Proof. Directly from Theorem 3. QE.D. The equivalence relation - partitions the generators of 2 O0g into classes of segments which are assigned to the same event, so call it the event relation. The corollary states that E refines -, i.e., 0 0,g all segments in a block of the initial segment partition are coded as the same event. We now show that this refinement is also sufficient for encodability. Theorem 5. Let 0 be admissibly generated by F. Let E be an equivalence relation on F refined by - Then there is a simple encoding g:Q QDE (X) where X = r/-, and g is the extension to Q of f:'? ~DEVS(X) where O(w) x and x = [w] and T = Q(w). Call this the standard encoding Proof. That 4 preserves left segmentation is shown by noting that if w is a left segment of w',then w w' and so by hypothesis W = w' ie., 0 [wI = [(']. Since also Z(w) < M(w') we have /(w) is a left segment of O(w'). Preservation of left segmentation by 4 extends to that 9f g by induction on the size of w Invertability of g then follows readily from the fact that 2(g(w)) = 2(w). To show that g preserves right segmentation at breakpoints, note that for g(w) = g(w1)...g(w) we have that (w~)..(w ) is the mls decomposition

12., of g(w) (since the range of. does not include r ). Thus 4g(Wl) =2: wl)) )is the first breakpoint and g(w)<Q( ) = (2)...4:w ) = g(W2' '.)= g (W< Q.E:ib. Combining- Theorems 3 and 5 gives Theorem 6 (Characterization of Simple DEVS Encodability) A segment set is simply encodable onto DEVS segments if, and only if, it has a nontrirvial admissible generating set. Proof To encode we may always-use the inital segment equivalence relation as in Theorem 5. Q.E.D. We interpret the above results intuitively as follows: Let Q be the input segment set for a systems We wish to decompose any given w E Q into segments wl,w2,...,w such that the switching from. w. to Wi+l represents as "event". The criterion for segmentation. is that of obtaining maximal length segments relative to some generator. set- r. This determines the event times (breakpoints"..of the ml.s decomposition). The, -event names are — determined by the initial segments just following each event. time.. Subject to certai.n constraints. (r must be-:.a.dmissible, and the...e.vent naming relation. - must be:.ref..ined by the. initial.segment relation = on.-)", we have freedom' of choice. in the parameters, r and -, of the event identific4 process.

13. SYSTEM STIMULATION BY DISCRETE EVENT MODELS We wish to characterize the class of systems simulateable by discrete event systems. We start at the system level, and in Part 2, will apply the results to the network level formulation of the problem. In Appendix 4, we show that it is enough to consider the simulation of iterative specifications by discrete event specifications. We modify slightly the notion of iterative specification given by Zeigler (1976), (Appendix 3),by replacing the output set and function by the more general notion of finite intersection cover of Q. This will enable us to more easily deal later with the network case. An iterative specification G = <T,X,Q,Q,Y,6,i> is DEVS-like G if the following hold: 1. Autonomy between external events: For all w, C QG, q C Q w - 6(q,w ) = 6(q,t ) for all t<min{2(w),Q(ip)} 2. State trajectories are -qgenerated. For all w E Q, q E Q STRAJ e rq, 7I where' = r (Q,T ). Condition 1) requires that the system respond indifferently to generators belonging to the same event class. Roughly, between external events, the system is insensitive to its input, i.e., functions autonomously, conditioned only by the nature of the last external event. Thus we shall also refer to a class [W] of QG/=- as an input regime. 0 Condition 2) requires that state trajectories be mls decomposable into generators determined by ir. This requires a finite number of events -

14. roughly crossings of rr block boundaries - be identifiable in a finite length state trajectory'. Remark. Let the iterative specification- induced by DEVS M= XMS, > be (M) = <TXDEV(X) Q,6, > where T,X,QDEVS(X'QM t6 are defined as in Appendix 3, and TrM is the partition defined by (s,e) 7M (s',e' s - st for all (s,e),(s,e') E Q M It is readily checked that G(M) is DEVS-like. Let G be an iterative specification and M a DEVS. A pair (q,h) is a DEVS morphism from G(M) to G if a) ~ extends to a simple encoding of Q, to.2 G DEVS(X) b) (g,h) is, a specification morphism from G(M) to G; (See Appendix 3) c) States of M represent block of Trr For every s E S there is a B E ir such that h(s,e) E B for s S O < e( (s.) We say that an:: iterative specification. G is DEVS simulat:eablae. if there is a DEVS M and a DEVS morphism::from:.. G(M)' to G We shall prove that the class of DEVS sirmulateable systems is- precisely the class. of DEVS-like systems.. To do" so we shall show how- to construct a DEVS simulation, for an:-iterative specification with DEVS-like properties. In what follows-, we. shall assume that there is 'no upper bound on thelengths of segments any class [w]i of - Q'/. The case where this is not true involves no new principles but is notationally messy. More specifically, we define for each class: [w] a representatijve w with domain T such that

15. for each t w E [w] and assume w is well defined. Given a DEVS-like specification construct a DEVS M called the standard simulator of G as follows: M = <X,S,j,4>.. 1) where X = QG/, S = Q x...2) 4:S+ R is defined for (q, [w]) E S by (q, [w]) = max{tI6 (qt,) E }.3) (the first breakpoint in the mls decomposition of STRAJq,~ X:QM x (X U {Q))-+S is defined for (q, [w) E S by 6 (q,[w]) = (6(qw (q ) [w ][)... 4) and for (q,[w],e) e QM and [I] C X by (q, [X],e, []) = (6(q,w e), [])...5) Let us interpret the elements of the standard simulator. The external event set X is the set of "events" determined by the initial segment relation; a typical "event" is an equivalence class (or its name) [w] E Q G/ (line 1 ) G0 The sequential state set S consists of all pairs (q, [wl) where q is a state of G the simulated model G and [w] is an external event. The pair (q,[w]) will be employed by the standard simulator to keep track of the state of G, q at the time of the last change in regime and the current regime [W) (line 2 ). Thus M "knows" the state of G and its

input regime at all times. The time advan-ce function determines.. for each- sequentia.l state (q, [w]) the time until the next internal event; -t(q, [w]) is the time it would take the system G to reach a e block boundary from state q operating under input regime [w] (line 3 ). The internal event transition function determines for each sequential state (q, [w]) the sequential state pertaining just after the next internal event: the new remembered is the state (on a I block boundary) G would have reached from state q in time -(q,1[w]) under input regime [wI, the new remembered regime is thalt which would be seen by G when reaching this boundary (line 4 ). The external event' transition function determines for each sequential state (q, [w]) and elapsed time e, O <e< t(q, [w]), the sequential state pertaining just after a change in regimes to [p] occurs after having been in regime [wI a time e: the new remembered state is the state G would have reached in these circumstances and the new remembered event is just [IlJ] We shall now show that the standard simulator is well defined and simulates G Proposition 7. The standard simulation M of a DEVS-like specificationr G is a legitimate DEVS. Moreover, there is DEVS morphism from G (M) to G Proof Define STRAJ - also denoted 6(q,w) with domain T by q,w 0 STRAJ -(t) = 6 (q,w) (t) = q t =' O"

17. Then STRAJ - represents the state trajectory associated with state q,w q E Q under input regime [w]. This is so, since for any t> 0 and any w' E [w] of length greater or equal to t, we have w Wt> and by autonomy (condition 1)) 6 (q,wt>) 6 (q,wt>) Since state trajectories are rr-generated (condition 2)), STRAJ q,w has a mls decomposition by r (Proposition 1) and its first breakpoint is thus well defined and identical to the definition of t(q, [w];6 is now easily seen to be well defined. Now define a mapping h:Q +Q by q if e = 0 h(q,[w],e) = 6 (q,w ) otherwise e> for all (q,[w],e) E QM ' We shall presently employ h as the state mapping in the DEVS simulation of G. For this we require the following Lemma 7 The standard simulator M is legitimate. Moreover, for w E G, q E Q h(6G (q, [w],O, w) = (q,w) where 6G:QM x QDEVS(X)+Q M is the single segment transition function belonging to the iterative specification G(M) Proof The proof proceeds by induction on the length of the mis decomposition of state trajectories by r. The proposition for interger n is P(n) E [(Vq E Q)(Vw E QG) (the mls decomposition of STRAJ by r has length n ~ m [ n and hl(6 (q, [w] ()l ) - I (q ) 1

18. Here mq,[w],O,(w) is the step counting function' (Appendix 3). Showing that P(n) is true. for all n amounts- ta..:-proving the lemma., The proof of P(O) and P(n) *- P(n+'l) is a straightforward use of the explicit definition of 6G (ibid) and the fact that if l ''n+l is an mls decomposition of length n+l, then 2,... is. an mls decomposition of length n Q.E. D. Now define, a. candidate morphism (, h) from G(M) to G where h, is as just defined. and 4 is standard encoding of.QG to r given G DEVS(X) by 4(w) = x where x [w] and T = -Z(w) Then by. Theorem 5, 4 extends to a simple encoding of Q to + G: DEVS(.X) Thus condition; a) of the: requiremen.t for DEVS morphism-.is satisfied. For the specification morph:ism of condition b), we have for (q,.u].,e) E QM ' and w E QG h(6 (q,[u],e,4(w)) h(6G (q,[u],e, [w] ))) (definition of ) = h(6 (&(q, [u],e, [w],0,g(.))) ) (definition of 6G ) h(6G(6 (6 q,u. e>).[wl.o, )) (definition of 6 ) G e> (W), = 6(6(q, u),w) (lemma. 7)' 6 (h(q, [u,e),w:) (definition. of h as required for specification. morphism. FoQ. condition c) requiring states of M to represent blocks of T, we have that for every (q,[w]') E S and O<e<t(q,.[w]) h(q,[w],e) = 6(q,we>) But by definition of -;(q, [u]), there is: a: block B otf" T such that

19. 6 (q,w ) B for O< e < t(q, [w]) (by definition of mls decomposition by rF, (q [w]) is the maximum T for which there is a block B such that STRAJ - is in B during (O,T) ). q,w Thus (g,h) is a DEVS morphism from the legitimate simulator M to G as claimed in the theorem. Q.E.D. We now show that the necessary condition for DEVS simulateability is DEVS-likeness. Proposition 8 Let (#,h) be a DEVS morphism from a DEVS specification G(M) to an iterative specification G. Then G is DEVS-like. Proof We shall need the following more general observation: Lemma 9 Let (0,h) be a specification morphism from G to G Then for all w,p E w - p 6(q,w) = 6(q,p) for all q e Q Proof Let w _ (i.e., #(w) = (). Since h is onto, for each q e Q, there is a q e Q such that h(q) =q. Then 6(h(q),w) =h(6(q,(w)) h(6(q, (w)) = 6(h(q),) Q.E.D.

20. Since 4 of a DEVS morphism extends to a simple encoding, we have from Corollary 4 that w i w E - and.(.w) ) and 0,g w u= - E. Thus we have from the lemma 7 w -- and 9 (w) = i'(1) ' 6.(q,w) 6 (q,U ) 0 or equivalently to 6 6F(qL.t>) = i(q,t' ) for t < min{(wto),k(v) } 0 t> (.W-. w Eli; (.w )=Z(V )) 0 t> C) t> Wt> t> Thus the autonomy condition (1) of DEVS-likeness is satisfied. Since h is onto, for any q E Q, there is (s,e) E QM such that h(s,e) = q. Since the DEVS M is DEVS-like, any state trajectory STRAJ is srf -generated (by the Rema&rk following the DEVS-like s,e,4(.) M definition). STRAJ is thus a composition of finite number of segments s,e,4 (me) such that each segment is characterized by a constant s and e 0 < e< (s). Since by conditions a) and b) of the DEVS morphism, d is an invertable, it is readily shown that ST-RAJ h( is a composition of a finite number.of segments, each being pointwise mappings under h of the consitant s segments (domains being matched up by the MATCH function induced by 4 ). (Appendix 3). By condition c) of DEVS morphism, each such segment maps to a generator in. Thus STRAJ is composed of 7r h(s,e),w a finite number of segmtents from I, i.e., is -r-generated. Since this is true for all possible pairs q E Q, X E QG, condition 2) for the DEVSlikeness is established. 9. B.D.

21. Summarizing Propositions 6 and 8. Theorem 9 (Characterization of DEVS simulateable systems) An iterative specification G is DEVS simulateable if, and only if, it is DEVS-like.

22. REALISTIC DEVS SIMULATION Until now, our characterization of computer simulateability has only encorporated the "finite number of computation instants in a finite interval" constraint. This is because the DEVS concept formalizes precisely this, and only this, notion. Various constraints c(an be imposed on the DEVS structure and on the DEVS morphism which reflect further "realistic" limitations on computer simulation. We shall discuss two possibilites involving finite dimensional and finite state constraints. The finite dimension restriction requires that all spaces employed in the simulation be finite dimensional. Many simulation models constructed independently of discrete event theory satisfy this restriction and their representation by DEVS would also be finite dimensional. The finite state constraint requires that all spaces, except that of the clock, be finite. This can be viewed as a further restriction on the finite dimensional class. The effect of these constraints is to narrow the class of simulateable systems in an easily understood manner. In fact, we can modify the definition of DEVS-like systems accordingly and maintain the equivalence of the two concepts. We shall be able to point out limitations in DEVS simulateability when the above finiteness conditions are applied. In contrast, in the unrestricted case, we have not been able to construct examples of non-simlulateable systems.

23. FINITE DIMENSION DEVS SIMULATION A DEVS M = <X,S,4,&> is finite dimensional if the external event set X and sequential state set S are finite dimensional linear spaces. We convert QDEVS(X) into a linear space by pointwise addition, treating as zero in the obvious way. An iterative specification G is finite dimension DEVS simulateable if there is a finite dimensional DEVS M and a DEVS morphism (0,h) from G(M) to G for which ~ is a linear map (this presumes 2 is a linear G space). An iterative specification G = <T,X,QG,Q,6,> is finite dimension DEVS-like if: 1. Autonomy with respect to an equivalence on Q2 - — ~~~~~ - G There is a finite dimensional linear equivalence = on QG (i.e., G QG/- is a finite dimensional linear space) such that for all w,p E Q qe Q o w (q,w ) = 6(q,vi ) for all t min{Z(w),Z(pi)} 0 t> (In particular, O refines - and QG/B is a factor space of QG/o ). and 2. State trajectories are 1r-generated (unchanged from DEVS-like definition). Theorem 10 (Characterization of finite dimension DEVS simulateability). An iterative specification is finite dimension DEVS simulateable if, and only if, it is finite dimension DEVS-like. Proof ( ) Let (4,h) be a DEVS morphism from M <X,S,&,;> to G. As in

24,,. Proposition 8, we find that for all w:,p-E Q G,g. t t> t>) = (q for all t, min{-:(u).(wi)} and q E Q and- also since- is linear, so is-. Thus the autonomy condition 1 is satisfied with E taken to be, noting that QG/0,I is isomorphic to X Let G bet finite di-mension DEVS-like. We construct the standard simulator' Mi employing E instead of. Thus X Q= G/ is finite 0 G dimensional and. S =-Q x X is finite dimensional, as required. We define a candidate morphism (4.,h) as in Proposition 6-, except that 4 is defined usin.g E rather than. Since - is linear., it is easily 0 shown that 4 is- linear. All other aspects of the proof that (,h) a DEVS-morph:ism remain unchanged.. Q.E.DE We can demonstrate-that there are systems which are not finite: dimensional DEVS simulateable although the same question for- unrestricted DEVS simulateability remains: open. Say that a. system S = <T,X,2,Q:,6,mr> is.- (finite dimension. ) simulateable if there is a (finite dimensional) DEVS M and. a. system morphism (g,h) from SG(M) to. S such that g is a simple, (linear) encoding. Theorem: 1 There are systems which are not finite dimension DEVS simulateable. In particular, the integrator is not finite dimension DEVS simulateable. Proof Let S be finite dimension simulateable via morphism (g,h). Then there is an iterative specification G of S is DEVS simulateable (TheOrem?..q

25. Appendix 4). The generator set 2 = g (rDEVS) is a linear subspace of Q (since F is a linear subspace of DE amd g is linear). Moreover, the DEVS DEVS restriction 4 = g/QG is linear. Thus if S is finite dimension DEVS simulateable, so is G finite dimensional DEVS simulateable. By Theorem 10, there is a finite dimensional equivalence - on Q which is refined G by -. In particular, if Q is the set of piecewise analytic segments, then by Theorem A.5 of Appendix 5, is infinite dimensional on Q 0 G ' so - strictly refines -. Thus there is an w e Q2 such that w is o G analytic and not identically zero, i.e. f O0, for which w = O. By 0 autonomy it is also necessary that for all q e Q, 6(q,w ) = 5(q,Ot>) for all tS Q(W). In particular, if S represents an integrator, then t 6(q,wt ) = q + fw(t')dt'. If w is analytic and not identically zero, then 0 t 6(0,wt>) = Sf(t')dt' is also no zero for all t dom(w). But 6(0,0t>) is clearly always zero, thus yielding a contradiction. Since piecewise analytic implies piecewise continuous, the same conclusion applies in the case that Q is pieqewise continuous. Q.E.D. Remark The integrator is unrestricted DEVS simulateable for the choice Q = the piecewise (finite degree) polynomial segments, and 'r = any quantization cover (Example 1). To see this take as admissible generator set, the polynomial segments, on which 0 is the identity. The autonomy condition for DEVS-likeness is thus easily satisfied. Moreover, the finite degree polynomial segments and their integrals are finitely oscillatory, so t-generability of the integrator's state trajectories is also satisfied (Example, Section 2).

More surprising, perhaps, is that the integrator with piecewise continuous segments as input may be ":arbitrarily closely simulated" by a DEVS. By the Weierstrass Approximation Theorem, every continuous function on a finite interval can be approximated arbitrarily closely, by a finite degree polynomial. Choose.as admissible generators the continuous segments, and let g(w) = x( ) where x = [approx (int(wo)]I where int(w)(t) = w(t')dt' and approx (X) is a polynomial 0 approximating o with maximum error e. The DEVS in this, case updates its memory of the integrator state by evaluating the polynomial named by x (a finite list of coefficients) at external event times, and internal event times (state trajectory boundary crossings predeterminable in principle as a z crossing problem). The error in state trajectory simulation is at most nc where n is the number of discontinuities in the input segment. The reader is invited to provide the details of simulation.

27. FINITE STATE DEVS SIMULATION An obvious finiteness restriction on a DEVS M = <X,S,t,&> is to require that the sets X and S be finite. This turns out not to be "architecturally" satisfying since it forces quantization of the elapsed time clock (see Appendix 5). We shall work with a weaker and useful restriction based on the possibility of adjoining a "time-left" component to a finite state space. A DEVS M is explicit form (Zeigler, 1976, p.245), if there is a set S and a function T:S+ R such that 00 S = { (s,)s E S, O <aG T(s)} and such that t(s,o) = a for all (s,a) E S The situation (s,a) can be interpreted as indicating that there is a time a left for the system to remain in state s. T(s) is the maximum such time such time (T(s) =Xo will cause the system to wait until an external event occurs before leaving state s A DEVS in explicit form is finite if the sets X and S are finite. Every DEVS can be DEVS simulated by an explicit form equivalent (obvious). This holds for finite DEVS and finite explicit form DEVS as well. But the state spaceof a (nontrivial) finite explicit form DEVS is infinite, in contrast to that of a finite DEVS, and thus adds extra power (Appendix 5). In terms of simulation language concepts, the finite explicit form DEVS assumes an infintely exact clock but otherwise cinite memory and finite events. An iterative specification G is finite exnlicit DEVS simulateable

if there is a finite explicit form DEVS M and a DEVS morphism (sh) from G(M) to G for which h -satisfies *) h-(s,o,e) = h(sa-e,O) for. all (s,c) E S.and O-e < a. Thisrestriction on the state decoding h ensures. that' the a component truly plays the role of a time left indicator. An iterative specification G = <T,X,G,Q,6,T > is finite explicit DEVS-like if: l. Autonomy with respect.to a finite eauivalence of QG (Same as finite dimension case, except that = is finite, i.e., QG/_ is finite) G 2. State trajector-ies are finitely 7fT-generated. There is a finite subcover f of of -and a finite -subset r of f(Q,T) sulch that for all q E Q, w E G2 S:TRAJ E right.,seg(P) seg(r) q,w where right.seg(r) is the closure of r under right segmentation and seg( ) is the; closure under both right and left segmentation. We note that right.seg(r) c F.-(Q,T) so that PF-(right.seg(r) ) = right.seg(r). Thus condition 2) requires that each state trajectory be decomposable into mls segments wl,...w such that each w., n 1 i = l,..,n-l is a right segment of some segment in r (Proposition 1) and w is subsegment of some segnent in r n Theorem 12 (Characterization of finite explicit DEVS simulateability). An iterative specification G is finite:implicit DEVS simulateable,

29. if, and only if, it is finite implicit DEVS-like. Proof (= ) Let M be a finite implicit form DEVS which simulates G using (~,h). Consider the segments {rl- Is E S } where — (t) h(s,t,0) for 0< t. T(s) s Since each (s,a) represents a block of 7r we have h(s,a,e) E BS,ca for 0O e <. But since also h(s,a,e) = h(s,a-e,O) we have {h(s,a,e) I 0. ea< } c B- - Since h is onto, Tr= {B- - s E S} s,T(s) s,T (s) is a finite subcover of w and r B- E B- - for each s E S s s,T(s) As in Proposition 6, it is easy to show that for each q E Q, w E Q, STRAJ has decomposition consisting of a finite number of right segments of elements in {n-} followed by a subsegment of some n - Thus we may 5 5 set r = {n } Let G be finite implicit DEVS-like. Construct a DEVS similar to the standard simulator of Proposition 6 as follows: X = G s = {(n,[w],a) 1n E r-, [w ] x, a E[,zT(n)]} t:S -R is defined by -t(n [j],,) = a co (:S-S is defined by 6 (n, [(],a) = (n ',[w ],a') where n' E r is such that nr_ (STRAJ - and a' is the <a first breakpoint in the mls decomposition of STRAJ by r 6:QM x X-+S is defined by &(n,[w],a,e,[u]) = (n', [],a') where l' E r is such that n< _, (STRAJ -) and a' -a~C

is the first breakpoint in the mls decomposition of STRAJ - by r n (e),~ We interpret -a as the point which is a units to the l.eft of the right end of rl Thus =- i=f (fT) is finite. If Z (n) = en f.Th<_ (rl)-c' we assume that ln has domain (-w,0] and < C <- r o,0> The candidate morphism (4,h) has d defined as in Theorem 10, and h defined by il(n(r])) if a = e=0 h (Tl [ ],,e) = rl< ()(e) for 0 < e < ' otherwise Clearly n< (l)- (_(e0) = <e)( = ((n)-+e), so h satisfies condit: The state (n, [w),o) represents the situation in G where operating in regime [U], time a is left to the 'end of the generator state trajectory If no external event occurs in the meantime, the DEVS selects the next generator and the appropriate point -from its.right end at which to start. If a change in regimes occurs after elapsed time e, the DEVS determines the current state of G, viz. n< ()_e), and from this determines the new, appropriate right segment of a generator under the new input regime. We omit the proof, which follows the 'lines of Theorem 10. Q.E.D.

31. EXAMPLE_ A DE=VSI u LATION We provide an example of a DEVS simulateable system drawn from a much larger simulation model built on the principles of this paper (for further information see Zeigler, 1977, ). Consider a "patch" in which may live a prey population feeding on resources in the patch. Let p(t) and r(t) denote the population size, and resource amount available at time t, respectively. Initially there are no prey and some resources. This state persists until some prey immigrate into the patch. The resources are then consumed to exhaustion (without replenishment) at which time some prey emigrate from the patch, while the remainder die out. The state space of the system is Q = ((r,p) r > 0, p >0} the first quadrant in the p,r plane. The dynamics not including migration are given by: dt =(b pos(r) - d)p dt dr d -u pos(r)p where pos(r) = 1 if r> 0 and pos(0) = 0. The parameters b, d and u give the birth rate (when there is food), death rate and resource consumption rate respectively. The input set X is the set { x / x a 0 } and the input segment set Q consists of all finite segments w E (X,R) such that )(t) >0 for only a finite number of points t in its domain; w(t) =x means that x prey arrive at the patch at time t. Q is isomorphic to the DEVS segments %PEVS(X) 50 that we may take raDEVS(X) as an admissible set of generators fox it (identifying ~ with O ) The system is autonomous with respect to, since for ~EX' DEVS (X) f - - fiA -k r

.3 2 w = i w (O) = 11(0) 1(O [W is a. left segment of i1 or conversely]. 0O Thus the regime [w] consists of essentially one segment and. represents the arrival of w(O) prey followed by an arbitrarily long period. of no immigratiorn during which the system evolves independently of its environment. Q is divided by a partition = {B1,B2,B3 where B1- -(0,oo) B { (r,p) / r> 0, p > 0, and B3 = (o,0] (Figure 1 ). 2 3 State trajectories are n-generated as we see as follows: For w E r w(0) =0 and DEVS (X) a) for (r,0) C B1 STRAJ (t) (r,O) E B t t> 0 (r,0), [0] 1 b) for (O,p) E B 3 -dt STRAJ(0,p), [0] (t) (0, pe ) B3, t. 0 c) for (r,p) E B2 STRAJ (t) (r-u E at at (re- [e -1], pe ) E l2 (r,p),[0] a 2 for 0 < t< T(r,p) = n - — + 1] where a=b -d and' a up STRJ p 0](t) = (, fp(T)e ) E B (r,p),[O] 3 a-r for t > = T(r,p), where p(T) = + U and f is the fraction remaining after ermmigration at ti.m e %'..For w E r w(0) 0), we define DEVS 6(r,,w)j =6(r, p+w(O), 0g(w)) for all (rp) Q EQ i.e., we specify that the effect of immigration is to add the incoming prey instantaneously to thle current population. T'hlus STRAJ = STRAJ (r,.p), [w (r, p +.o(0)), [0(']

p B3 B2 STRAJ(r,p), ro] STRAJ (o, (rp),toI / (r,o) r STRAJ (r,o), I oJ Fig. I

33. and it is clear that every state trajectory consists of a finite number of segments lying total within B1, B2 or B3, i.e., is Tr-generated. Thus the constructed system S is DEVS-like. The standard DEVS simulator has input event set r ) isomorphic DEVS.(X) o with X, sequential states S QxX= { (r,p, w) }, with -r(r,p+w(O)) if (r,p+w(O)) C B2 00 otherwise...1) 6 (r,p,[w]) = (O,f(p+w(O)+-), [O]) if (r,p+w(O)) E B2 (since t=oo on B U B2 6 need not be defined there) 1 2.2) and (r,p, [w],e, [u]) = (6(r,p,w ), [u]) e> - (6(r,p+w(O),O ),[u])~ e (r,p+w(O), [u]) if (r,p+w(O)) E B1 u(+w(O) ae ae (r- [e.-1, (p+w(0))e, [u]) a if (r,p+w(O)) E B2 -de (r, (p+w(O))e,[u]) if (r,p+w(O)) E B3...3) An output event occuring in the ctossing from B to B (prey 2 B 3 emigration) can be defined by adding an output Set Y= {y/y > 0} and an output function (1-f) (p+w(O)+ a- ) if e = T(r,p+w(O)) X(r,p,[w],e) = u 0 otherwise The simulator is in fact a finite dimension DEVS. Realized by a discrete event simulation language such as SIMULA, it requires memory for three real variables r,p, and [w] (actually, in this case [w] can

34. be dispensed with), one internal process for the B2 phase (prey growth and emigration) and one external process (for the prey arrival). Thus it is realizable exactly to the precision with which real numbers are represented on the particular computer. Supposing that the model always starts with r food supply and no prey, the following sketches a simulation program realization: Internal Process state variables are: r, p, last.time B1 Set r = r ' P = 0 Wait B2 Hold for a time T(r,p) ar Cause emigration of (-f) (p + —) prey u ar Set r = 0, p = f (p + ----), last.time = time.now u B Wait External Process 1 Cause immigration of x prey If Internal Process is in B1, Set p x, last.time = tirqe.now Start Internal Process from B2 2 If Internal Process is in B, Set e = time.now - last.time ae ae Set r = r - [e-1], p pe +x, last.time = time.now a Start Internal Process from B2 if Internal Process is in B3, Set e = time.now - last.time -de Set p = pe + x Start Internal Process from B1 Hold for interarrival time go to 1.

35. Finite Explicit DEVS Simulatior n We shall give an example of a finite explicit form DEVS approximation -to the model just developed. Let us start by noting that because of the exponential prey growth and limited resources, the effect of the actual number of prey in migrating is small. This is seen in lines 1) and 2) with 1 large compared to w(O). For the same reason, subsequent prey invasions have little effect once a colony has been established. This is seen in lines 1) and 2) with p (the population size at a subsequence prey invasion) large compared to w(O). Thus our first simplification is to reduce the input event set to a single event indicating that at least one prey is arriving. Formally, we are assuming that the system is autonomous with respect to the equivalence -, where Q- consists of two classes [0] = {w/w(O) = 0) and [1] = {w/w(o) C 1} Note that the autonomy condition for generat6rs in [,1:] is precisely a statement of the fact that the system is sensitive at most to the arrival of prey and never -to the exact number arriving. Now let us (reasonably) suppose that there is an upper bound on the resources available; set it equal to 1 by normalization. To make things more interesting we shall allow the resources to grow to the maximum in dr logistic.fashion: -=gr(l-r) in the absence of prey. Let us recognize dt 3 intervals of resources: low, medium and high (Figure. ). Placing rlow' rmed and rhi. at the center of the respective intervals,. we shall assume that the:;tAl.e trajector'y hRAJ (i E {low, med, 'higll}) adequately approximates the state trajectories STRAJ( [0 from interval i

36. Thus our model has 5 generator trajectories as follows: n - STRAJ( 0jQO) [Q3 (resource growth in the absence of prey, assuming an initial value.01 in By) r) = R riAlJ tO] i E {low, med. highi (restricted to B2) 3 a n = STRAJ (prey decay from a maximun p) = —+l in B3) (Op ),[oI max u 3 max All state trajectories associated with input generators are mas decomposable into a number n> 0 of right segments of the generators 1 low med high 3 ra= l, Plow, I med, Thih, ri } followed by a subsegment of one of them. For example, for (O,r) e B1, STRAJ( [0] is of the form nt; ipd i i3 i3 STRAJ is of the form rt or i) or i 3t where i depends r)[]t>,o < t> t on r and o depends on i (Figure 2). Thus the state trajectories are finritely i-generable and the system is finite explicit DEVS-like. The standard simulator has five finite states with associated maximum times as follows: s T(s) 1 co low low Ilow (time to reach B3 along 1row) med T (similar) med high T (similar) high 3 a (time to reach p 1 starting from p max max Then, referring to Figure 2, 6 is defined by (i,a) = (3ai) for i C {low, med, high) and 6 (3,o): (l,rn) and 6 is defined by 6(1,,e,.) = (i(e),Ti ) i(e)

o0' i P 0:high Phigh Pm ined-ae 0Iow* Piw 0O 0 rlow rmed rhigh l r e low high 3 e~ X high t) 1i s1.> 1' o..17.rhigh \:.3 ' b) Fig. 2

37. and 6(i,0,e,1) = (i,o-e) in all other cases (invading prey ignored) As a simulation program this takes the form: 1. Wait until a prey invades 2. Obtain elapsed time e Hold for time Ti i(e) Cause emigration of f~- prey 3. Hold for time ai(e) 4. Go to 1

38. APPENDIX 1 REVIEW OF INPUT SET RELATED CONCEPTS (Z,T), where Z is a set and T is a time base (reals or integrals), denotes the set of all segments w:<O,T >-+Z where T > O'. The angular brackets represent a fixed choice from the set {( ], [ ), [ ]} (Z,T) is a semigroup under composition; - w' is the segment obtained by translating w.' so that as to be contiguous with w.. and concaatenating. For W:<O,T>-+Z, dom(w) = <O,T>, (W) =T; W w<0O,t> and = WjtT> are left and rightsgmnts of w at t respectively. ADMISSIBLE GENERATING SETS For a subset r c (Z,T), the semigroup generated by r is denoted r+.A decomposition w1 2 w...,w of w by IF is a maximal length segment (mls) decomposition, if each wi is the longest generator in r which is a left segment of w....W The points 1 n n-i {z(w1),(w9)+1(w,)..., Z(Wi) } are called the breakpoints of the i=l decomposition w1 w2,..., w. The length of this decomposition is n P generates Q if r += and admissibly generates Q if moreover each w EC&S2 has an mls decomposition by F (it is unique if it exists). A semigroup Q is adrcissibly generated by itself. r non trivially admissibly generates Q if r is a proper subset of Q which admissibly generates it. Sufficient, but not necessary conditions, for admissibility are:

39. Theorem A.1 (P. 220, [Zeigler, 1976]). r admissibly generates F + if a) w e rF+ max{tjI) E rF} exists b) w E Fr w<t e r for all T >0 in dom(w) [Zeigler, 1976], P.220 gives an example where b) fails. An example where a) fails is the following: Let r = {atlt e irrationals; here at denotes the segment of length t and constant value a. Then r = {att e reals}. F does not admissibly generate Fr since for integer T, the set {tIt is irrational <T} has no maximum. DISCRETE EVENT SEGMENTS Let X be a set of "events" and T be the reals. FDEVS(X) = U 2X where Q is the set of no event segments {IT > 0} where 4T (t) = for all t C <O,T> and QX is the set of one event segments {x IT> 01, where x (t) =c for 0 < t < T and x (0)=x. Here < > is fixed to be [ ) rDEVS(X) and QDEVS(X) = rDEVS(X) are called discrete event generators and segment sets, respectively. r admissibly generates DEV() DEVS(X) DEVS (X) (Pa 238, [Zeigler, 19761).

ENCODINGS Let p c (X,T) and ' c (X',T ') be;emicjrotlps. A mai-:ping g:Q '-'p is called an encoding of Q' by Q An encoding g:P2 '+Q is invertable if 1. g p.reserves left segmentation W a left segment of w implies g(w') is a left segment of g(w ) 2. g is one-one on lengths: (W) -z (')*' (g(w)) =Z(g(m)) Lemma A.2 (P. 271, [Zeigler, 1976]). g is invertable * —* there is a one-to-one function MATCH such that MATCH( (w)) = Z(g(w)) g ( t>) g (w)MATCH (t)> Let Q and Q' be closed under right and left segmentation. -l Then MATCH is a monotonically increasing function with inverse MATCH defined for all positive values of T An encoding g i-s a homomorphism if g ( w') = g(w)g(w') for all,IW' E '. Let r admissibly generate Q-' and:-+ Q. Then g is the unique extension of ~ to )' where g(w) = -(W1)... (w) and W...w is the mls decomposition of w by r

41. APPENDIX 2 RELATION BETWEEN HOMOMORPHISM AND SIMPLICITY We remark that the properties of invertability and homomorphism are completely independent. For example, the map g is invertable, but not t a homomorphism, where g(w) (t)=f w(t')dt', and the map g is 0 homomorphism but not invertable,where Q' = {piecewise constant segments} and g is the unique extension to 2' of 4:{constant segments}-*Q, where a if a>0 4(a ) = a2 otherwise We say that g is a homomorf hic invertable encoding if it is both invertable and a homomorphism. A homomorphic invertable encoding allows only length dependent time scale change (the function MATCH), and memoryless segment by segment mapping. A class of examples of homomorphic invertable encodings is given by the point-by-point, uniform dilation encoding g, where g(w) (t) O(W(t/r)) where 4:X' +X and T are arbitrary. Q is left cancellable if w = n X =W<Z The choice < > = [ ) with the natural composition, render Q left cancellable. So does the choice [ ] with right segment's endpoint, determining the value at the joint. Assertion A. 3 Let Q be left cancellable. If g is a homomorphic invertable encoding into i2 then g is a simple encoding. Proof If it is readily shown that g preserves both left and right

4'2. segmentation at all points, including breakpoints, i.e., (wt> g( MATHt) and g(w ) = g(w) g > )MAT= gtw t <MATCH (t) Q.E.D. It is important to note that a simple encoding need not be a homomorphism. For example, let ~2' = Q of Example, Section 2, and let DES = Let g:r+ rD be defined by 0(w) =x where x= w(O) DEVS L7T DEVS and T = (). Let g:Q- + DEVS be the unique extension of ~ defined by g(w) =:(W1)...'(wn) where.1''''' is the mls decomposition of o It is readily shown that g is invertable and preserves right segmentation at breakpoints, but is not a homomorphism since if w,P C r B then wB E rF and g(wji) = B(O)u()+,(uI. But g(W)g(}j) (o) PO)= (0 Band g(~)w(Q(3)) = ~(0) =g()g(W) (P(I) ). and g (wvi) (k (w) 34 $ iiiO) = g(w)g( )(Z(w))

43. APPENDIX 3 THE EVENT RELATION Consider the sets r ={finite degree polynomial' and Fr (piecewise m finite degree polynomial having derivatives at leat to order ml. Then for w,T E, W( -= 4 w is a left segment of 1j or conversely 0 (polynomials which agree on a non zero interval are identical; Levi, 1968), and for w,1 E r m w - O w and ' start with the same polynomial segment. 0 Thus r /E is an infinite dimensional vector space isomorphic to m 0 r. We can show this is true for any subvector space of ' which generates it. Proposition A. 4 Let QG be a subvector space of I' which generates r. Then G G / k is an infinite dimensional vector space isomorphic to r G 0 Proof It is readily shown that Q / is a vector space. Since Q c r 0 for every w C QG there is a T such that w E F. Moreover, G T> w = o3. Thus there is a linear transformation taking Q /o into F O > G (or better its representation) given by mapping [w]0 onto the sequence off derivatives (w(O), w'(O), w"(O),...) Conversely, since r c G, for every w E r, there is a T such that w E 0 o Again, since w - w there is a linear transformation T> G 0 T> mapping r into 2G/ o given by mapping 1 into [w(. Thus 0G/7 and P are isomorphic as vector spaces. Q.E.. -. ~~~~~~~~~~Q.E.D~.

44. Theorem A.5 Let 52 be the piecewise analytic segments or the piecewise continuous segments. Then for any vector space generator set Q2 G of Q, QG/- is infinite dimensional. Pr~oof P c Q in both cases. Q I' and in fact it is easy to show CG - that P2 n r generates I'. Since P n I is infinite dimensional, G G so is Q G

45. REVIEW OF SYSTEM SPECIFICATIONS AND MORPHISMS G = <T,X,GQ,6 G,r> is an iterative specification if QG C (X,T) is ar admissible generating set, and 6:0 x 2G Q extends uniquely to a transition function 6:QxQG-+Q having the composition property. We have modified the definition of Zeigler 1976, P. 223, by omitting Y and X and requiring instead the specification of a finite intersection cover of Q DISCRETE EVENT SPECIFICATION A DEVS M = <XM,S,&,t> where XM and S are sets (external events and sequential states, respectively); -:S-+ R = [O,] is the time advance function; and 6:QM x (XM U {4}) *S where QM { (s,e) s E S O e< t(s)} and 6(s,e,4) A= (s) where 6:S- S is called the internal event transition function. A DEVS M is legitimate if for each (s,e) E QM and T > 0, the M number of transitions in the interval (0,r), made starting form (s,e) m is finite. (See Zeigler, 1976, P.237 for formal definition.) s,e,-t Theorem A.6 (Zeiqler, 1976, P. 238) A legitimate DEVS M induces an iterative specification G(M) = <T,X,r Q, > where T = R, X = X U f} and DEVS(X) M G M 6G:QE xf ~is given by G:QM FDEVS(X) QM =f (s,e-r) if e+T < t (s) 6G (s,',e ' ) - TG (64 (s),0,~+4)_-(S) else

46. and 6G(s,e,x ) 6- (E(t.,ex),0, ) G T ) SYSTEM A sjsterm S - <T,X,S,),6> where T is th-)e time base (R or I) X is the input value set, Q c (X,T) is the inuent s nt set, O the state set and 6:Q X Q+Q, the tranciticn function. We require that Q is a semigroup under composition and 6 has the composition property 6 (q,cw') = (6 (q,w),c An iterative specificatior G specifies a system SG wlere G S2 = QG and = 6=G MORPHISMS A system morphism from S to S' is a pair (g,h) where - onto g.L' — rS; and h:Qj -- Q' where Q C Q such that for all q. Q,, C 2E', h (6 (q,g(w)) =6 ' (h (q)) ) A peci f ication morh_.srm from G to G' is a pair (4,h) where,:S2G-i+G, h is as in the system morphism, and the commutative relation is required to hold only for c. E Q. Theorem A.7 (Zeiqler, 1976, P. 2'71, 274) A specification morphism (i4,h) from G -to G' induces a system morphism (g,h) from SG to S where g is the extension of G G' to I'. If moreover, q is invertable, STRALJ (t) = h(STAJ 'MATCH(t)) for all q E Q, f 0'. (q),u qq).'G'C

47. APPENDIX 5 EQUIVALENCE OF DEVS SYSTEM AND SPECIFICATION MORPHISMS Theorem A. 8 Let M be a DEVS, S a system and (g,h) a system morphism from SG(M) to S. If g is a simple encoding, then (g,h) is induced by a specification morphism (0,h) form G(M) to G where S =S Proof -l Since g is simple, by Proposition 2, F = g (DEVS) admissibly DEVS generates Q Let G have the same objects as S except that G =1' and 6G = 611'. It is easily shown that G is an iterative specification and SG= S. Also (4,h) is a specification morphism from G(M) to G,where gjr which induces the morphism (g,h) from S to S G(M) Q.E.D. Since every specification morphism (4,h) from G(M) to G induces a system morphism (g,h) from S to S, we have G(M) G Corollary A.9 A system S is DEVS simulateable if, and only if, it has an interative specification which is DEVS simulateable. (By a system S being DEVS simulateable, we mean that there is a system morphism (g,h) from some SG(M) to S such that g is simple and states of M represent blocks of Tf as in the DEVS morphism definition.)

48. APP5ENDIX 6 FINITE DEVS LIMITATIONS Theorem A.10 For a finite DEVS M let the set E = {el&(s,x,e) = s'} be a union of a finite number of intervals for each s,x,s' for which E, is not empty. Then M is DEVS simulateable by a finite DEVS M for which &(s,e,x) is independent of e for all s E S, x E X Proof The union of E over all x C X and s' E S is just [O,t(s)]. Since each E is a finite union of intervals and there are finitely many pairs (x s), the intersection all these sets finitely partitions [Ot(s)] and refines every E Let O< t< t2... < t t(s) be this partition. In M, replace s by states (s,1),...,(s,n) such that 6 (si) = (s,i+l) for i= l,...,n-l, and 6 (s,n) (6 (s),1); t(s,i) t ti; and 6((s,i),e,x) - 6(s,t,x). Clearly, '((s,i),e,x) = ((s,i),e',x) for all e,e' E [O,t(s,i)] as clainmed. It is easy to show that.;M DEVS simulates M Q.E.D. The theorem indicates that a finite DEVS with a reasonable clock dependence, can ble only finitely sensitive to the arrival time of an external event. Any timing of arrivals that such a device can do, can also be done by a succession of a finite number of states in which the el apsed time within a state plays no role ir determining the next state. In effect, the simulation clock has been replaced by a finite counter. Note that the proof depends on the finite number of sets EB Sx,XS

49. so would not go through for a finite explicit form DEVS which may have an infinity of sets E (s J) (,') While the foregoing indicates the "architectural" weakness of finite DEVS systems, it does not establish that there are 1-0 behaviors "tuned" to this weakness. We now provide an example of an I-O behavior not finite DEVS realizable, but finite explicit form DEVS realizable. Theorem A.11 There are I-O function behaviors of finite explicit form DEVS systems which are not realizable by any finite DEVS system. Proof Consider a finite explicit form DEVS M = <X,S,Y,6,X, > where X {1} = Y, S = {ref,act}, T(ref)= T > 0, T(act) = Y and.ref 6 (ref,o) - (act,-),(ref,o,e,l) = (ref, (- e) &(act,-),e,l) - (ref,T.........ref 1 if s ref and o = e X(s,(a,e) f otherwise The I-O behavior of this M is characterized by the fact that in state act (active) it waits until receiving an input pulse, whence it switches to state ref (refractory). It remains in state ref for a finite refractory period T, during which all input pulses are ignored, and then ref reverts to state act while siqnaling this eve:nt by an output pulse ((f,.), - Now let M be a finite DEVNS whi.c:h real izes that beh-avior of M at thle I-O function level (Zeiger,:1e)76, P. 2()5) TrIn particular, let (s,e)

I / Tref outpu t pulse pulse Fig.3

50. realize the input segment to output segment mapping from state (ref,T,0) re f in SG(M). Since M has a finite set S, min{t(s)Is E S} exists and is not zero, (assume M has no transitory states, without loss of generality, Zeigler, 1976, p.24). Let = % min{t(s)} and apply any segment t 1 for 0< < T rf- to (s,e). By the DEVS operation the state at the end of this segment is of the form (s,C) (the pulse at time T causes an immediate transition to some "unseen" state (s,O) and since c < t(s), we are in state (s,C), c seconds later). Since S is finite, there are T1 0 <,T2,2 T suc< sch -that S is in 2f 1 2 ref -c G(M) the same state (s,~) at both T1 and ~12 The behavior from this state cannot be different in both cases. But as can be seen by applying a segment 'T -T, this contradicts the behavior of S ref 2 Q.E.D.

UNIVERSITY OF MICHIGAN 3 9015 03527 5281 RtE IEl; RENC E C Bablich, A. F, J. Grason and D. Parnas (1) / J 3 i.) i a..i l.. Simu:Lati.n, C. M., 18:323-329. fHogewe., P. (1975) "Concepts For Sirrulat-ioll, 'A Co mpar:. on a.:-eii on Simullation Langcuages'", Tn: Systeemleer, Oui anrd uf:to-t (Lo Ic Stenford Kroese, Leiden. Levi, H. (19693) Poly].omia:.s, TPower Series and Ca.cu]1.u.,, D. Van Nostr.and, Princetor, N. Y. Veech, W.A. (1]967) A Second Course in Complex Anajljsi:-.;, W.A. BTnjamin,. New York. Zeigler, B.P. (1.9'76) Ttheor.of MOdellinJ and Simiulation, Wiley & Sons, N.Y. Zeigler, B.P. (In Preparation) "Systems Simulat:eabl.e by the Digital Computer, Part 2: Discrete Event Netwo)rk Models"4 Zeigler, B.P. and A. Barto (1.977) "Al.ternative Formalisms for Bio- and Eco-Systems Modelling", Simulation (Th Press). Zeigler, B.P. (1977) "Multi-Level, Multi-Formalism Modelling: An Ecosystem Exanple", Proc. First Int. Conf. on Math. Modelling,, St. Louis, Mo.