DEVS

DEVS, abbreviating discrete event system specification, is a modular and hierarchical formalism for modeling and analyzing general systems that can be discrete event systems which might be described by state transition tables, and continuous state systems which might be described by differential equations, and hybrid continuous state and discrete event systems. DEVS is a timed event system.

DEVS, abbreviating discrete event system specification, is a modular and hierarchical formalism for modeling and analyzing general systems that can be discrete event systems which might be described by state transition tables, and continuous state systems which might be described by differential equations, and hybrid continuous state and discrete event systems. DEVS is a timed event system. ==History== DEVS is a formalism for modeling and analysis of discrete event systems (DESs). The DEVS formalism was invented by Bernard P. Zeigler, who is emeritus professor at the University of Arizona. DEVS was introduced to the public in Zeigler's first book, Theory of Modeling and Simulation in 1976, while Zeigler was an associate professor at University of Michigan. DEVS can be seen as an extension of the Moore machine formalism, which is a finite state automaton where the outputs are determined by the current state alone (and do not depend directly on the input). The extension was done by associating a lifespan with each state, providing a hierarchical concept with an operation, called coupling, Since the lifespan of each state is a real number (more precisely, non-negative real) or infinity, it is distinguished from discrete time systems, sequential machines, and Moore machines, in which time is determined by a tick time multiplied by non-negative integers. Moreover, the lifespan can be a random variable; for example the lifespan of a given state can be distributed exponentially or uniformly. The state transition and output functions of DEVS can also be stochastic. Zeigler proposed a hierarchical algorithm for DEVS model simulation in 1984 which was published in Simulation journal in 1987¹. Since then, many extended formalism from DEVS have been introduced with their own purposes: DESS/DEVS for combined continuous and discrete event systems, P-DEVS for parallel DESs, G-DEVS for piecewise continuous state trajectory modeling of DESs, RT-DEVS for realtime DESs, cell-DEVS for cellular DESs, fuzzy-DEVS for fuzzy DESs, dynamic structuring DEVS for DESs changing their coupling structures dynamically, and so on. In addition to its extensions, there are some subclasses such as SP-DEVS and FD-DEVS have been researched for achieving decidability of system properties. Due to the modular and hierarchical modeling views, as well as its simulation-based analysis capability, the DEVS formalism and its variations have been used in many application of engineering (such as hardware design, hardware/software codesign, communications systems, manufacturing systems) and science (such as biology, and sociology) ==Formalism== The following formal definition is for classic DEVS. In this article, we will use the time base, \mathbb{T}=[0,\infty) that is the set of non-negative real numbers; the extended time base, \mathbb{T}^\infty=[0,\infty] that is the set of non-negative real numbers plus infinity. t_4] , and implies t_2 = t_3 . An event trajectory (t_1,z_1)(t_2,z_2) \cdots (t_n,z_n) over an event set Z and a time interval [t_l, t_u] \subset \mathbb{T} is concatenation of unit event segments \epsilon_{[t_l,t_1]},(t_1,z_1), \epsilon_{[t_1,t_2]},(t_2,z_2),\ldots, (t_n,z_n), and \epsilon_{[t_n,t_u]} where t_l\le t_1 \le t_2 \le \cdots \le t_{n-1} \le t_n \le t_u . Mathematically, an event trajectory is a mapping \omega a time period [t_l,t_u] \subseteq \mathbb{T} to an event set Z . So we can write it in a function form : ===Atomic DEVS=== An atomic DEVS model is defined as a 7-tuple where X is the set of input events; Y is the set of output events; S is the set of sequential states (or also called the set of partial states); s_0\in S is the initial state; ta:S \rightarrow \mathbb{T}^\infty is the time advance function which is used to determine the lifespan of a state; \delta_{ext}:Q \times X \rightarrow S is the external transition function which defines how an input event changes a state of the system, where Q=\{(s,t_e)|s \in S, t_e \in (\mathbb{T} \cap [0, ta(s)])\} is the set of total states, and t_e is the elapsed time since the last event; \delta_{int}:S \rightarrow S is the internal transition function which defines how a state of the system changes internally (when the elapsed time reaches to the lifetime of the state); \lambda:S \rightarrow Y^\phi is the output function where Y^\phi=Y \cup \{\phi\} and \phi \not\in Y is a silent event or an unobserved event. This function defines how a state of the system generates an output event (when the elapsed time reaches to the lifetime of the state); The atomic DEVS model for ping-pong players The atomic DEVS model for player A of Fig. 1 is given player= such that \begin{align} X &= \{?\textit{receive}\}\\ Y &= \{!\textit{send}\}\\ S &= \{(d,\sigma)| d \in \{\textit{Wait},\textit{Send}\}, \sigma \in \mathbb{T}^\infty\}\\ s_0 &= (\textit{Send}, 0.1)\\ ta(s) &=\sigma \text{ for all } s \in S\\ \delta_{ext}(((\textit{Wait},\sigma),t_e),?\textit{receive})&=(\textit{Send},0.1)\\ \delta_{int}(\textit{Send},\sigma)&=(\textit{Wait},\infty)\\ \delta_{int}(\textit{Wait},\sigma)&=(\textit{Send},0.1)\\ \lambda(\textit{Send},\sigma)&=!\textit{send}\\ \lambda(\textit{Wait},\sigma)&=\phi \end{align} Both player A and player B are atomic DEVS models. Simply speaking, there are two cases that an atomic DEVS model M can change its state s \in S : (1) when an external input x \in X comes into the system M ; (2) when the elapsed time t_e reaches the lifespan of s which is defined by ta(s) . At the same time of (2), M generates an output y \in Y which is defined by \lambda(s) . For formal behavior description of given an atomic DEVS model, refer to the section about behavior of atomic DEVS. Computer algorithms to implement the behavior of a given atomic DEVS model are available in the section about simulation algorithms for atomic DEVS. The ping-pong game of Fig. 1 can be modeled as a coupled DEVS model N= where X=\{\} ; Y=\{\} ; D=\{A,B\} ; M_A \text{ and } M_B is described as above; C_{xx}=\{\} ; C_{yx}=\{(A.!send, B.?receive), (B.!send, A.?receive)\} ; and C_{yy}(A.!send)=\phi, C_{yy}(B.!send)=\phi . Simply speaking, like the behavior of the atomic DEVS class, a coupled DEVS model N changes its components' states (1) when an external event x \in X comes into N ; (2) when one of components M_i where i \in D executes its internal state transition and generates its output y_i \in Y_i . In both cases (1) and (2), a triggering event is transmitted to all influences which are defined by coupling sets C_{xx}, C_{yx}, and C_{yy} . For formal definition of behavior of the coupled DEVS, you can refer to the section about behavior of coupled DEVS. Computer algorithms to implement the behavior of a given coupled DEVS mode are available at the section about simulation algorithms for coupled DEVS. ==Analysis methods== ===Simulation for continuous state systems=== By introducing a quantization method which abstracts a continuous segment as a piecewise const segment, DEVS can simulate behaviors of continuous state systems which are described by networks of differential algebraic equations. This research has been initiated by Zeigler in 1990s. Many properties have been clarified by Prof. Kofman in 2000s and Dr. Nutaro. In 2006, Prof. Cellier who is the author of Continuous System Modeling, and Prof. Kofman wrote a text book, Continuous System Simulation, in which chapters 11 and 12 cover how DEVS simulates continuous state systems. Dr. Nutaro's book, covers the discrete event simulation of continuous state systems too. A timed event system is a structure \mathcal{G}= where \,Z is the set of events; \,Q is the set of states; \,Q_0 \subseteq Q is the set of initial states; Q_A \subseteq Q is the set of accepting states; \Delta \subseteq Q \times \Omega_{Z,[t_l,t_u]} \times Q is the set of state trajectories in which (q,\omega,q') \in \Delta indicates that a state q \in Q can change into q' \in Q along with an event segment \omega \in \Omega_{Z,[t_l, t_u]} . If two state trajectories (q_1,\omega_1,q_2) and (q_3, \omega_2, q_4) \in \Delta are called contiguous if q_2 = q_3 , and two event trajectories \omega_1 and \omega_2 are contiguous. Two contiguous state trajectories (q,\omega_1,p) and (p,\omega_2, q') \in \Delta implies (q,\omega_1\omega_2,q') \in \Delta . Given a timed event system \mathcal{G}= , the set of its behaviors is called its language depending on the observation time length. Let t be the observation time length. If 0 \le t , t -length observation language of \mathcal{G} is denoted by L(\mathcal{G}, t) , and defined as L(\mathcal{G},t)=\{\omega \in \Omega_{Z,[0,t]}: \exists (q_0, \omega, q) \in \Delta, q_0 \in Q_0, q \in Q_A\}. We call an event segment \omega \in \Omega_{Z,[0,t]} a t -length behavior of \mathcal{G} , if \omega \in L(\mathcal{G},t) . By sending the observation time length t to infinity, we define infinite length observation language of \mathcal{G} is denoted by L(\mathcal{G}, \infty) , and defined as L(\mathcal{G},\infty)= \{\omega \in \underset{t \rightarrow \infty} \lim \Omega_{Z,[0,t]}: \exists \{q: (q_0, \omega, q) \in \Delta, q_0 \in Q_0 \} \subseteq Q_A \}. We call an event segment \omega \in \underset{t \rightarrow \infty} \lim \Omega_{Z,[0,t]} an infinite-length behavior of \mathcal{G} , if \omega \in L(\mathcal{G},\infty) \omega \in L(\mathcal{G},\infty) . ===Extensions (superclassing)=== Numerous extensions of the classic DEVS formalism have been developed in the last decades. Among them formalisms which allow to have changing model structures while the simulation time evolves. G-DEVS, parallel DEVS, dynamic structuring DEVS, cell-DEVS, dynDEVS, fuzzy-DEVS, GK-DEVS, ml-DEVS, symbolic DEVS, real-time DEVS, rho-DEVS ===Restrictions (subclassing)=== There are some sub-classes known as schedule-preserving DEVS (SP-DEVS) and finite and deterministic DEVS (FD-DEVS) which were designated to support verification analysis. SP-DEVS and FD-DEVS whose expressiveness are E(SP-DEVS) \subset E(FD-DEVS) \subset E(DEVS) where E(formalism) denotes the expressiveness of formalism. === Atomic DEVS === The behavior of a given DEVS model is a set of sequences of timed events including null events, called event segments, which make the model move from one state to another within a set of legal states. To define it this way, the concept of a set of illegal state as well a set of legal states needs to be introduced. In addition, since the behavior of a given DEVS model needs to define how the state transition change both when time is passed by and when an event occurs, it has been described by a much general formalism, called general system. In this article, we use a sub-class of general system formalism, called timed event system instead. Depending on how the total state and the external state transition function of a DEVS model are defined, there are two ways to define the behavior of a DEVS model using timed event system. Since the behavior of a coupled DEVS model is defined as an atomic DEVS model, the behavior of coupled DEVS class is also defined by timed event system. ==== View 1: total states = states * elapsed times ==== Suppose that a DEVS model, \mathcal{M}= has the external state transition \delta_{ext}:Q \times X \rightarrow S . the total state set Q=\{(s,t_e)| s \in S, t_e \in (\mathbb{T} \cap [0, ta(s)])\} where t_e denotes elapsed time since last event and \mathbb{T}=[0,\infty) denotes the set of non-negative real numbers, and Then the DEVS model, \mathcal{M} is a timed event system \mathcal{G}= where The event set Z=X \cup Y^\phi . The state set Q=Q_A \cup Q_N where Q_N=\{\bar{s} \not \in S \} . The set of initial states \,Q_0 = \{(s_0,0)\} . The set of accepting states Q_A = \mathcal{M}.Q. The set of state trajectories \Delta \subseteq Q \times \Omega_{Z,[t_l,t_u]} \times Q is defined for two different cases: q \in Q_N and q \in Q_A . For a non-accepting state q \in Q_N , there is no change together with any even segment \omega \in \Omega_{Z,[t_l,t_u]} so (q,\omega,q) \in \Delta. For a total state q=(s,t_e) \in Q_A at time t \in \mathbb{T} and an event segment \omega \in \Omega_{Z,[t_l,t_u]} as follows. If unit event segment \omega is the null event segment, i.e. \omega=\epsilon_{[t, t+dt]} \, (q, \omega, (s, t_e+dt)) \in \Delta. If unit event segment \omega is a timed event \omega=(x, t) where the event is an input event x \in X , (q, \omega, (\delta_{ext}(q,x), 0)) \in \Delta. If unit event segment \omega is a timed event \omega=(y, t) where the event is an output event or the unobservable event y \in Y^\phi , \begin{cases} (q, \omega,(\delta_{int}(s), 0)) \in \Delta& \textrm{if } ~ t_e = ta(s), y = \lambda(s)\\ (q, \omega, \bar{s}) & \textrm{otherwise}. \end{cases} Computer algorithms to simulate this view of behavior are available at simulation algorithms for atomic DEVS section. ==== View 2: total states = states * lifespans * elapsed times ==== Suppose that a DEVS model, \mathcal{M}= has the total state set Q=\{(s,t_s, t_e)| s \in S, t_s\in \mathbb{T}^\infty, t_e \in (\mathbb{T} \cap [0, t_s])\} where t_s denotes lifespan of state s , t_e denotes elapsed time since last t_s update, and \mathbb{T}^\infty=[0,\infty) \cup \{ \infty \} denotes the set of non-negative real numbers plus infinity, the external state transition is \delta_{ext}:Q \times X \rightarrow S \times \{0,1\} . Then the DEVS Q=\mathcal{D} is a timed event system \mathcal{G}= where The event set Z=X \cup Y^\phi . The state set Q=Q_A \cup Q_N where Q_N=\{ \bar{s} \not \in S \} . The set of initial states \,Q_0 = \{(s_0,ta(s_0),0)\} . The set of acceptance states Q_A = \mathcal{M}.Q . The set of state trajectories \Delta \subseteq Q \times \Omega_{Z,[t_l,t_u]} \times Q is depending on two cases: q \in Q_N and q \in Q_A . For a non-accepting state q \in Q_N , there is no changes together with any segment \omega \in \Omega_{Z,[t_l,t_u]} so (q,\omega,q) \in \Delta. For a total state q=(s,t_s, t_e) \in Q_A at time t \in \mathbb{T} and an event segment \omega \in \Omega_{Z,[t_l,t_u]} as follows. If unit event segment \omega is the null event segment, i.e. \omega=\epsilon_{[t, t+dt]} (q, \omega, (s, t_s, t_e+dt)) \in \Delta. If unit event segment \omega is a timed event \omega=(x, t) where the event is an input event x \in X , \begin{cases} (q, \omega, (s', ta(s'), 0))\in \Delta& \textrm{if } ~\delta_{ext}(s,t_s,t_e,x)=(s',1),\\ (q, \omega, (s', t_s, t_e))\in \Delta& \textrm{otherwise, i.e. } ~\delta_{ext}(s,t_s,t_e,x)=(s',0). \end{cases} If unit event segment \omega is a timed event \omega=(y, t) where the event is an output event or the unobservable event y \in Y^\phi , \begin{cases} (q, \omega, (s', ta(s'),0)) \in \Delta& \textrm{if } ~t_e = t_s, y = \lambda(s), \delta_{int}(s)=s',\\ (q, \omega, \bar{s} )\in \Delta& \textrm{otherwise}. \end{cases} Computer algorithms to simulate this view of behavior are available at simulation algorithms for atomic DEVS section. View1 has been introduced by Zeigler in which given a total state q=(s,t_e) \in Q and \, ta(s)=\sigma where \sigma is the remaining time. In other words, the set of partial states is indeed S=\{(d,\sigma)| d \in S', \sigma \in \mathbb{T}^\infty \} where S' is a state set. When a DEVS model receives an input event x \in X , view1 resets the elapsed time t_e by zero, if the DEVS model needs to ignore x in terms of the lifespan control, modelers have to update the remaining time \, \sigma = \sigma - t_e in the external state transition function \delta_{ext} that is the responsibility of the modelers. Since the number of possible values of \sigma is the same as the number of possible input events coming to the DEVS model, that is unlimited. As a result, the number of states s=(d, \sigma) \in S is also unlimited that is the reason why view2 has been proposed. If we don't care the finite-vertex reachability graph of a DEVS model, view1 has an advantage of simplicity for treating the elapsed time t_e=0 every time any input event arrives into the DEVS model. But disadvantage might be modelers of DEVS should know how to manage \sigma as above, which is not explicitly explained in \delta_{ext} itself but in \Delta . View2 has been introduced by Hwang and Zeigler in which given a total state q=(s, t_s, t_e) \in Q , the remaining time, \sigma is computed as \, \sigma = t_s - t_e. When a DEVS model receives an input event x \in X , view2 resets the elapsed time t_e by zero only if \delta_{ext}(q,x)=(s',1) . If the DEVS model needs to ignore x in terms of the lifespan control, modelers can use \delta_{ext}(q,x)=(s',0) . Unlike view1, since the remaining time \sigma is not component of S in nature, if the number of states, i.e. |S| is finite, we can draw a finite-vertex (as well as edge) state-transition diagram. As a result, we can abstract behavior of such a DEVS-class network, for example SP-DEVS and FD-DEVS, as a finite-vertex graph, called reachability graph. === Coupled DEVS === DEVS is closed under coupling. In other words, given a coupled DEVS model N , its behavior is described as an atomic DEVS model M . For a given coupled DEVS N , once we have an equivalent atomic DEVS M , behavior of M can be referred to behavior of atomic DEVS which is based on timed event system. Similar to behavior of atomic DEVS, behavior of the coupled DEVS class is described depending on definition of the total state set and its handling as follows. ==== View1: Total states = states * elapsed times ==== Given a coupled DEVS model N = , its behavior is described as an atomic DEVS model M = where X and Y are the input event set and the output event set, respectively. S=\underset{i \in D}\times Q_i is the partial state set where Q_i=\{(s_i,t_{ei})| s_i \in S_i, t_{ei} \in (\mathbb{T} \cap [0, ta_i(s_i)])\} is the total state set of component i \in D (Refer to view1 of behavior of DEVS), where \mathbb{T}=[0,\infty) is the set of non-negative real numbers. s_0=\underset{i \in D}\times q_{0i} is the initial state set where q_{0i}=(s_{0i},0) is the total initial state of component i \in D . ta:S \rightarrow \mathbb{T}^\infty is the time advance function, where \mathbb{T}^\infty=[0,\infty] is the set of non-negative real numbers plus infinity. Given s=(\ldots, (s_{i},t_{ei}),\ldots) , ta(s)= \min\{ ta_i(si) - t_{ei}| i \in D\}. \delta_{ext}:Q \times X \rightarrow S is the external state function. Given a total state q=(s,t_e) where s=(\ldots, (s_{i}, t_{ei}),\ldots), t_e \in (\mathbb{T}\cap [0,ta(s)] ) , and input event x \in X , the next state is given by \delta_{ext}(q, x)=s'=(\ldots,(s_i', t_{ei}'), \ldots) where (s_i', t_{ei}')= \begin{cases} (\delta_{ext}(s_i, t_{ei}, x_i),0) & \text{if } (x, x_i) \in C_{xx}\\ (s_i, t_{ei}) & \text{otherwise}. \end{cases} Given the partial state s=(\ldots,(s_i, t_{ei}),\ldots) \in S , let IMM(s)=\{i \in D| ta_i(s_i) = ta(s) \} denote the set of imminent components. The firing component i^* \in D which triggers the internal state transition and an output event is determined by i^* = Select(IMM(s)). \delta_{int}:S \rightarrow S is the internal state function. Given a partial state s=(\ldots, (s_{i}, t_{ei}),\ldots) , the next state is given by \delta_{int}(s)=s'=(\ldots,(s_i', t_{ei}'), \ldots) where (s_i', t_{ei}')= \begin{cases} (\delta_{int}(s_i),0) & \text{if } i = i^*\\ (\delta_{ext}(s_i, t_{ei}, x_i),0) & \text{if } (\lambda_{i^*}(s_{i^*}), x_i) \in C_{yx}\\ (s_i, t_{ei}) & \text{otherwise}. \end{cases} \lambda:S \rightarrow Y^\phi is the output function. Given a partial state s=(\ldots, (s_{i}, t_{ei}),\ldots) , \lambda(s)= \begin{cases} \phi &\text{if } \lambda_{i^*}(s_{i^*})=\phi \\ C_{yy}(\lambda_{i^*}(s_{i^*})) &\text{otherwise}. \end{cases} ==== View2: Total states = states * lifespan * elapsed times ==== Given a coupled DEVS model N = , its behavior is described as an atomic DEVS model M = where X and Y are the input event set and the output event set, respectively. S=\underset{i \in D}\times Q_i is the partial state set where Q_i=\{(s_i,t_{si}, t_{ei})| s_i \in S_i, t_{si} \in \mathbb{T}^\infty, t_{ei} \in (\mathbb{T} \cap [0, t_{si}])\} is the total state set of component i \in D (Refer to view2 of behavior of DEVS section). s_0=\underset{i \in D}\times q_{0i} is the initial state set where q_{0i}=(s_{0i},ta_i(s_{0i}),0) is the total initial state of component i \in D . ta:S \rightarrow \mathbb{T}^\infty is the time advance function. Given s=(\ldots, (s_{i},t_{si},t_{ei}),\ldots) , ta(s)= \min\{ t_{si} - t_{ei}| i \in D\}. \delta_{ext}:Q \times X \rightarrow S \times \{0, 1\} is the external state function. Given a total state q=(s,t_s,t_e) where s=(\ldots, (s_{i}, t_{si},t_{ei}),\ldots), t_s \in \mathbb{T}^\infty, t_e \in (\mathbb{T}\cap [0,t_s] ) , and input event x \in X , the next state is given by \delta_{ext}(q, x)=((\ldots,(s_i', t_{si}', t_{ei}'), \ldots),b) where (s_i', t_{si}', t_{ei}')= \begin{cases} (s_i', ta_i(s_i'), 0) & \text{if } (x, x_i) \in C_{xx},\delta_{ext}(s_i, t_{si}, t_{ei}, x_i)=(s_i',1)\\ (s_i', t_{si}, t_{ei} ) & \text{if } (x, x_i) \in C_{xx},\delta_{ext}(s_i, t_{si}, t_{ei}, x_i)=(s_i',0)\\ (s_i, t_{si}, t_{ei}) & \text{otherwise} \end{cases} and b= \begin{cases} 1 & \text{if } \exists i \in D: (x, x_i) \in C_{xx},\delta_{ext}(s_i, t_{si}, t_{ei}, x_i)=(s_i',1)\\ 0 & \text{otherwise}. \end{cases} Given the partial state s=(\ldots,(s_i, t_{si}, t_{ei}),\ldots) \in S , let IMM(s)=\{i \in D| t_{si} - t_{ei} = ta(s) \} denote the set of imminent components. The firing component i^* \in D which triggers the internal state transition and an output event is determined by i^* = Select(IMM(s)). \delta_{int}:S \rightarrow S is the internal state function. Given a partial state s=(\ldots, (s_{i},t_{si}, t_{ei}),\ldots) , the next state is given by \delta_{int}(s)=s'=(\ldots,(s_i', t_{si}', t_{ei}'), \ldots) where (s_i', t_{si}', t_{ei}')= \begin{cases} (s_i', ta_i(s_i'),0) & \text{if } i = i^*,\delta_{int}(s_i)=s_i',\\ (s_i', ta_i(s_i'),0) & \text{if } (\lambda_{i^*}(s_{i^*}), x_i) \in C_{yx},\delta_{ext}(s_i, t_{si}, t_{ei}, x_i)=(s', 1)\\ (s_i', t_{si}, t_{ei}) & \text{if } (\lambda_{i^*}(s_{i^*}), x_i) \in C_{yx},\delta_{ext}(s_i, t_{si}, t_{ei}, x_i)=(s', 0)\\ (s_i, t_{si}, t_{ei}) & \text{otherwise}. \end{cases} \lambda:S \rightarrow Y^\phi is the output function. Given a partial state s=(\ldots, (s_{i}, t_{si}, t_{ei}),\ldots) , \lambda(s)= \begin{cases} \phi &\text{if } \lambda_{i^*}(s_{i^*})=\phi \\ C_{yy}(\lambda_{i^*}(s_{i^*})) &\text{otherwise}. \end{cases} Given a total state q=(s,t_e) \in Q where s = (\ldots,(s_i, t_{ei}),\ldots) If unit event segment \omega is the null event segment, i.e. \omega=\epsilon_{[t, t+dt]} , the state trajectory in terms of timed event system is \Delta(q, \omega)=((\ldots,(s_i, t_{ei}+dt),\ldots), t_e+dt). Given a total state q=(s,t_s,t_e) \in Q where s = (\ldots,(s_i, t_{si}, t_{ei}),\ldots) If unit event segment \omega is the null event segment, i.e. \omega=\epsilon_{[t, t+dt]} , the state trajectory in terms of timed event system is \Delta(q, \omega)=((\ldots,(s_i,t_{si}, t_{ei}+dt),\ldots), t_{s}, t_e+dt). === Atomic DEVS === Given an atomic DEVS model, simulation algorithms are methods to generate the model's legal behaviors which are trajectories not to reach to illegal states. (see Behavior of DEVS). Zeigler originally introduced the algorithms that handle time variables related to lifespan t_s \in [0,\infty] and elapsed time t_e\in [0,\infty) by introducing two other time variables, last event time, t_l\in [0,\infty) , and next event time t_n\in [0,\infty] with the following relations: \, t_e = t - t_l and \, t_s = t_n - t_l where t\in [0,\infty) denotes the current time. And the remaining time, \,t_r=t_s-t_e is equivalently computed as \, t_r = t_n - t , apparently t_r \in [0,\infty] . Since the behavior of a given atomic DEVS model can be defined in two different views depending on the total state and the external transition function (refer to behavior of DEVS section), the simulation algorithms are also introduced in two different views as below. A=(X,Y,S,ta, \delta_{ext}, \delta_{int}, \lambda) // the associated Atomic DEVS model when receive init-message(Time t ) t_l \leftarrow t; t_n \leftarrow t_l + ta(s); when receive star-message(Time t ) if t \ne t_n then error: bad synchronization; y \leftarrow \lambda(s); send y-message( y,t ) to parent; s \leftarrow \delta_{int}(s) t_l \leftarrow t; t_n \leftarrow t_l + ta(s); ==== View 1: total states = states * elapsed times ==== As addressed in behavior of atomic DEVS section, when DEVS receives an input event, right calling \delta_{ext} , the last event time, t_l is set by the current time, t , thus the elapsed time t_e becomes zero because t_e = t - t_l . when receive x-message( x \in X , Time t ) if ( t_l \le t and t \le t_n ) == false then error: bad synchronization; s \leftarrow \delta_{ext}(s,t-t_l, x) t_l \leftarrow t; t_n \leftarrow t_l + ta(s); ==== View 2: total states = states * lifespans * elapsed times ==== Notice that as addressed in behavior of atomic DEVS section, depending on the value of b return by \delta_{ext} , last event time, t_l , and next event time, t_n ,consequently, elapsed time, t_e , and lifespan t_n , are updated (if b=1 ) or preserved (if b=0 ). when receive x-message( x \in X , Time t ) if ( t_l \le t and t \le t_n ) == false then error: bad synchronization; (s,b) \leftarrow \delta_{ext}(s, t-t_l, x) if b = 1 then t_l \leftarrow t; t_n \leftarrow t_l + ta(s); === Coupled DEVS === Given a coupled DEVS model, simulation algorithms are methods to generate the model's legal behaviors, which are a set of trajectories not to reach illegal states. (see behavior of a coupled DEVS model.) Zeigler originally introduced the algorithms that handle time variables related to lifespan t_s \in [0,\infty] and elapsed time t_e\in [0,\infty) by introducing two other time variables, last event time, t_l\in [0,\infty) , and next event time t_n\in [0,\infty] with the following relations: \, t_e = t - t_l and \, t_s = t_n - t_l where t\in [0,\infty) denotes the current time. And the remaining time, \,t_r=t_s-t_e is equivalently computed as \, t_r = t_n - t, apparently t_r \in [0,\infty] . Based on these relationships, the algorithms to simulate the behavior of a given coupled DEVS are written as follows. algorithm DEVS-coordinator Variables: parent // parent coordinator t_l : // time of last event t_n : // time of next event N=(X, Y, D, \{M_i\}, C_{xx}, C_{yx}, C_{yy},Select) // the associated coupled DEVS model when receive init-message(Time t) for each i \in D do send init-message(t) to child i t_l \leftarrow \max\{t_{li}: i \in D\} ; t_n \leftarrow \min\{t_{ni}: i \in D\} ; when receive star-message(Time t) if t \ne t_n then error: bad synchronization; i^* \leftarrow Select(\{i \in D: t_{ni} = t_n\}); send star-message(t)to i^* t_l \leftarrow \max\{t_{li}: i \in D\} ; t_n \leftarrow \min\{t_{ni}: i \in D\} ; when receive x-message( x \in X , Time t) if ( t_l \le t and t \le t_n ) == false then error: bad synchronization; for each (x,x_i) \in C_{xx} do send x-message( x_i ,t) to child i t_l \leftarrow \max\{t_{li}: i \in D\} ; t_n \leftarrow \min\{t_{ni}: i \in D\} ; when receive y-message( y_i \in Y_i , Time t) for each (y_i,x_i) \in C_{yx} do send x-message( x_i ,t) to child i if C_{yy}(y_i)\ne \phi then send y-message( C_{yy}(y_i) , t) to parent; t_l \leftarrow \max\{t_{li}: i \in D\} ; t_n \leftarrow \min\{t_{ni}: i \in D\} ; M = where X is a finite set of input events; Y is a finite set of output events; S is a finite set of states; s_0 \in S is the initial state; \tau: S \rightarrow \mathbb{Q}_{[0,\infty]} is the time advance function which defines the lifespan of a state where \mathbb{Q}_{[0,\infty]} is the set of non-negative rational numbers plus infinity. \delta_x: S \times X \rightarrow S \times \{0,1\} is the external transition function which defines how an input event changes the schedule as well as a state of the system. The internal schedule of a state s \in S is updated by \tau(s') if \delta_x(s)=(s',1) , otherwise(i.e., \delta_x(s)=(s',0) ), the schedule is preserved. \delta_y: S \rightarrow Y^\phi \times S is the output and internal transition function where Y^\phi = Y \cup \{\phi\} and \phi \notin Y denotes the silent event. The output and internal transition function defines how a state generates an output event, at the same time, how the state changes internally. Formal representation of ping-pong player The formal representation of the player in the ping-pong example shown in Fig. 1 can be given as follows. M= where X ={?receive}; Y ={!send}; S ={Send, Wait}; s_0 =Send for player A, Wait for player B; \tau (Send)=0.1, \tau (Wait)= \infty ; \delta_x (Wait,?receive)=(Send,1), \delta_x (Send,?receive)=(Send,0); \delta_y (Send)=(!send, Wait), \delta_y (Wait)=( \phi , Wait). Formal representation of one slot toaster The formal representation of the slot of Two-slot Toaster Fig. 2(a) and (b) can be given as follows. M= where X ={?push}; Y ={!pop}; S ={I, T}; s_0 =I; \tau (T)=20 for the left slot, 40 for the right slot, \tau (I)= \infty ; \delta_x (I, ?push)=(T,1), \delta_x (T,?push)=(T,0); \delta_y (T)=(!pop, I), \delta_y (I)=( \phi , I). Formal representation of crosswalk light controller As mentioned above, FD-DEVS is an relaxation of SP-DEVS. That means, FD-DEVS is a supper class of SP-DEVS. We would give a model of FD-DEVS of a crosswalk light controller which is used for SP-DEVS in this Wikipedia. M= where X ={?p}; Y ={!g:0, !g:1, !w:0, !w:1}; S ={BG, BW, G, GR, R, W, D}; s_0 =BG, \tau (BG)=0.5, \tau (BW)=0.5, \tau (G)=30, \tau (GR)=30, \tau (R)=2, \tau (W)=26, \tau (D)=2; \delta_x (G,?p)=(GR,0), \delta_x (s,?p)=(s,0) if s \neq G; \delta_y (BG)=(!g:1, BW), \delta_y (BW)=(!w:0, G), \delta_y (G)=( \phi , G), \delta_y (GR)=(!g:0, R), \delta_y (R)=(!w:1, W), \delta_y (W)=(!w:0, D), \delta_y (D)=(!g:1, G); A FD-DEVS model, M= is DEVS \mathcal{M}= where X,Y of \mathcal{M} are the same as those of M . S'=\{(s,t_s): s \in S,t_s \in \mathbb{T}^\infty\} s_0'=(s_0,\tau(s_0)) Given a state (s,t_s) \in S' , ta(s,t_s) = t_s. Given a state (s,t_s) \in S' and an input event x \in X , \delta_{ext}(s, t_s, t_e, x) = \begin{cases} (s',t_s - t_e) & \text{if } \delta_x(s,x)=(s',0) \\ (s',\tau(s')) & \text{if } \delta_x(s,x)=(s',1) \\ \end{cases} Given a state (s,t_s) \in S' , \delta_{int}(s,t_s)=(s',\tau(s')) if \delta_{y}(s)=(y,s'). Given a state (s,t_s) \in S' , \lambda(s,t_s)=y if \delta_{y}(s)=(y,s'). For details of DEVS behavior, the readers can refer to behavior of atomic DEVS section. Behavior of ping-pong player A Fig. 3. shows an event segment (top) and the associated state trajectory (bottom) of player A who plays the ping-pong game introduced in Fig. 1. In Fig. 3. the status of player A is described as (state, lifespan, elapsed time)=( s, t_s, t_e ) and the line segment of the bottom of Fig. 3. denotes the value of the elapsed time. Since the initial state of player A is "Send" and its lifetime is 0.1 seconds, the height of (Send, 0.1, t_e ) is 0.1 which is the value of t_s . After changing into (Wait, inf, 0) when t_e is reset by 0, player A doesn't know when t_e becomes 0 again. However, since player B sends back the ball to player A 0.1 second later, player A gets back to (Send, 0.1 0) at time 0.2. From that time, 0.1 seconds later when player A's status becomes (Send, 0.1, 0.1), player A sends back the ball to player B and gets into (Wait, inf, 0). Thus, this cyclic state transitions which move "Send" to "Wait" back and forth will go forever. Behavior of a toaster Fig. 4. shows an event segment (top) and the associated state trajectory (bottom) of the left slot of the two-slot toaster introduced in Fig. 2. Like Fig.3, the status of the left slot is described as (state, lifespan, elapsed time)=( s, t_s, t_e ) in Fig. 4. Since the initial state of the toaster is "I" and its lifetime is infinity, the height of (Wait, inf, t_e ) can be determined by when ?push occurs. Fig. 4. illustrates the case ?push happens at time 40 and the toaster changes into (T, 20, 0). From that time, 20 seconds later when its status becomes (T, 20, 20), the toaster gets back to (Wait, inf, 0) where we don't know when it gets back to "Toast" again. Fig. 4. shows the case that ?push occurs at time 90 so the toaster get into (T,20,0). Notice that even though there someone push again at time 97, that status (T, 20, 7) doesn't change at all because \delta_x (T,?push)=(T,1). The above controller for crosswalk lights can be modeled by an atomic SP-DEVS model. Formally, an atomic SP-DEVS is a 7-tuple M= where X is a finite set of input events; Y is a finite set of output events; S is a finite set of states; s_0 \in S is the initial state; \tau: S \rightarrow \mathbb{Q}_{[0,\infty]} is the time advanced function which defines the lifespan of a state where \mathbb{Q}_{[0,\infty]} is the set of non-negative rational numbers plus infinity. \delta_x: S \times X \rightarrow S is the external transition function which defines how an input event changes a state of the system. \delta_y: S \rightarrow Y^\phi \times S is the output and internal transition function where Y^\phi = Y \cup \{\phi\} and \phi \notin Y denotes the silent event. The output and internal transition function defines how a state generates an output event, at the same time, how the state changes internally. Formal representation of crosswalk controller The above controller shown in Fig. 2 can be written as M= where X ={?p}; Y ={!g:0, !g:1, !w:0, !w:1}; S ={BG, BW, G, GR, R, W, D}; s_0 =BG, \tau (BG)=0.5, \tau (BW)=0.5, \tau (G)=30, \tau (GR)=30, \tau (R)=2, \tau (W)=26, \tau (D)=2; \delta_x (G,?p)=GR, \delta_x (s,?p)=s if s \neq G; \delta_y (BG)=(!g:1, BW), \delta_y (BW)=(!w:0, G), \delta_y (G)=( \phi , G), \delta_y (GR)=(!g:0, R), \delta_y (R)=(!w:1, W), \delta_y (W)=(!w:0, D), \delta_y (D)=(!g:1, G); A SP-DEVS model, M= is DEVS \mathcal{M}= where X,Y of \mathcal{M} are the same as those of M . S'=\{(s,t_s): s \in S,t_s \in \mathbb{T}^\infty\} s_0'=(s_0,\tau(s_0)) Given a state (s,t_s) \in S' , ta(s,t_s) = t_s. Given a state (s,t_s) \in S' and an input event x \in X, \delta_{ext}(s, t_s, t_e, x) = (s',t_s - t_e) \text{ if } \delta_x(s,x)=s'. Given a state (s,t_s) \in S' , \delta_{int}(s,t_s)=(s',\tau(s') if \delta_{y}(s)=(y,s'). Given a state (s,t_s) \in S' , \lambda(s,t_s)=y if \delta_{y}(s)=(y,s'). Let a total state (s,t_s,t_e) of a SP-DEVS model be passive if t_s = \infty ; otherwise, it be active. One of known SP-DEVS's limitation is a phenomenon that "once an SP-DEVS model becomes passive, it never returns to become active (OPNA)". This phenomenon was found first by Hwang, although it was originally called ODNR ("once it dies, it never returns"). The reason why this one happens is because of the restriction (3) above in which no input event can change the schedule so the passive state can not be awaken into the active state. For example, the toaster models drawn in Fig. 3(b) are not SP-DEVS because the total state associated with "idle" (I), is passive but it moves to an active state, "toast" (T) whose toasting time is 20 seconds or 40 seconds. Actually, the model shown in Fig. 3(b) is FD-DEVS. ==References==

Text derived from https://en.wikipedia.org/w/index.php?oldid=1369355650 under CC BY-SA 4.0; modifications have been made.