Английская Википедия:Behavior of DEVS
Шаблон:Multiple issues 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 [ZPK00]. 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, <math>\mathcal{M}=<X,Y,S,s_0,ta,\delta_{ext},\delta_{int},\lambda></math> has
- the external state transition <math> \delta_{ext}:Q \times X \rightarrow S</math>.
- the total state set <math>Q=\{(s,t_e)| s \in S, t_e \in (\mathbb{T} \cap [0, ta(s)])\}</math> where <math> t_e </math> denotes elapsed time since last event and <math> \mathbb{T}=[0,\infty)</math> denotes the set of non-negative real numbers, and
Then the DEVS model, <math>\mathcal{M} </math> is a Timed Event System <math>\mathcal{G}=<Z,Q,Q_0,Q_A,\Delta> </math> where
- The event set <math>Z=X \cup Y^\phi</math>.
- The state set <math>Q=Q_A \cup Q_N</math> where <math> Q_N=\{\bar{s} \not \in S \}</math>.
- The set of initial states <math> \,Q_0 = \{(s_0,0)\}</math>.
- The set of accepting states <math> Q_A = \mathcal{M}.Q.</math>
- The set of state trajectories <math> \Delta \subseteq Q \times \Omega_{Z,[t_l,t_u]}
\times Q</math> is defined for two different cases: <math> q \in Q_N </math> and <math> q \in Q_A </math>. For a non-accepting state <math> q \in Q_N </math>, there is no change together with any even segment <math>\omega \in \Omega_{Z,[t_l,t_u]}</math> so <math>(q,\omega,q) \in \Delta.</math>
For a total state <math> q=(s,t_e) \in Q_A</math> at time <math> t \in \mathbb{T} </math> and an event segment <math> \omega \in \Omega_{Z,[t_l,t_u]}</math> as follows.
If unit event segment <math> \omega</math> is the null event segment, i.e. <math> \omega=\epsilon_{[t, t+dt]}</math>
<math>\, (q, \omega, (s, t_e+dt)) \in \Delta.</math>If unit event segment <math> \omega</math> is a timed event <math> \omega=(x, t)</math> where the event is an input event <math> x \in X</math>,
<math>(q, \omega, (\delta_{ext}(q,x), 0)) \in \Delta.
</math>If unit event segment <math> \omega</math> is a timed event <math> \omega=(y, t)</math> where the event is an output event or the unobservable event <math> y \in Y^\phi</math>,
<math>\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}
</math>
Computer algorithms to simulate this view of behavior are available at Simulation Algorithms for Atomic DEVS.
View 2: total states = states * lifespans * elapsed times
Suppose that a DEVS model, <math>\mathcal{M}=<X,Y,S,s_0,ta,\delta_{ext},\delta_{int},\lambda></math> has
- the total state set <math>Q=\{(s,t_s, t_e)| s \in S, t_s\in \mathbb{T}^\infty, t_e \in (\mathbb{T} \cap [0, t_s])\}</math> where <math> t_s </math> denotes lifespan of state <math> s </math>, <math> t_e </math> denotes elapsed time since last <math>t_s </math>update, and <math> \mathbb{T}^\infty=[0,\infty) \cup \{ \infty \}</math> denotes the set of non-negative real numbers plus infinity,
- the external state transition is <math> \delta_{ext}:Q \times X \rightarrow S \times \{0,1\} </math>.
Then the DEVS <math>Q=\mathcal{D}</math> is a timed event system <math>\mathcal{G}=<Z,Q,Q_0,Q_A,\Delta> </math> where
- The event set <math>Z=X \cup Y^\phi</math>.
- The state set <math>Q=Q_A \cup Q_N </math> where <math> Q_N=\{ \bar{s} \not \in S \}</math>.
- The set of initial states<math> \,Q_0 = \{(s_0,ta(s_0),0)\}</math>.
- The set of acceptance states <math> Q_A = \mathcal{M}.Q</math>.
- The set of state trajectories <math> \Delta \subseteq Q \times \Omega_{Z,[t_l,t_u]}
\times Q</math> is depending on two cases: <math>q \in Q_N </math> and <math>q \in Q_A </math>. For a non-accepting state <math> q \in Q_N </math>, there is no changes together with any segment <math>\omega \in \Omega_{Z,[t_l,t_u]}</math> so <math>(q,\omega,q) \in \Delta.</math>
For a total state <math> q=(s,t_s, t_e) \in Q_A</math> at time <math> t \in \mathbb{T} </math> and an event segment <math> \omega \in \Omega_{Z,[t_l,t_u]}</math> as follows.
If unit event segment <math> \omega</math> is the null event segment, i.e. <math> \omega=\epsilon_{[t, t+dt]}</math>
<math> (q, \omega, (s, t_s, t_e+dt)) \in \Delta.</math>If unit event segment <math> \omega</math> is a timed event <math> \omega=(x, t)</math> where the event is an input event <math> x \in X</math>,
<math>\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}
</math>If unit event segment <math> \omega</math> is a timed event <math> \omega=(y, t)</math> where the event is an output event or the unobservable event <math> y \in Y^\phi</math>,
<math>\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}
</math>
Computer algorithms to simulate this view of behavior are available at Simulation Algorithms for Atomic DEVS.
Comparison of View1 and View2
Features of View1
View1 has been introduced by Zeigler [Zeigler84] in which given a total state <math> q=(s,t_e) \in Q </math> and
where <math> \sigma </math> is the remaining time [Zeigler84] [ZPK00]. In other words, the set of partial states is indeed <math>S=\{(d,\sigma)| d \in S', \sigma \in \mathbb{T}^\infty \} </math> where <math> S'</math> is a state set.
When a DEVS model receives an input event <math> x \in X</math>, View1 resets the elapsed time <math> t_e </math> by zero, if the DEVS model needs to ignore <math> x </math> in terms of the lifespan control, modellers have to update the remaining time
in the external state transition function <math> \delta_{ext} </math> that is the responsibility of the modellers.
Since the number of possible values of <math> \sigma </math> 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 <math> s=(d, \sigma) \in S </math> 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 <math> t_e=0</math> every time any input event arrives into the DEVS model. But disadvantage might be modelers of DEVS should know how to manage <math>\sigma</math> as above, which is not explicitly explained in <math>\delta_{ext} </math> itself but in <math>\Delta</math>.
Features of View2
View2 has been introduced by Hwang and Zeigler[HZ06][HZ07] in which given a total state <math> q=(s, t_s, t_e) \in Q </math>, the remaining time, <math> \sigma</math> is computed as
When a DEVS model receives an input event <math> x \in X</math>, View2 resets the elapsed time <math> t_e </math> by zero only if <math> \delta_{ext}(q,x)=(s',1)</math>. If the DEVS model needs to ignore <math> x </math> in terms of the lifespan control, modellers can use <math> \delta_{ext}(q,x)=(s',0) </math>.
Unlike View1, since the remaining time <math> \sigma </math> is not component of <math> S </math> in nature, if the number of states, i.e. <math> |S| </math> is finite, we can draw a finite-vertex (as well as edge) state-transition diagram [HZ06][HZ07]. 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 [HZ06][HZ07].
See also
- DEVS
- Behavior of Coupled DEVS
- Simulation Algorithms for Atomic DEVS
- Simulation Algorithms for Coupled DEVS
References
- [Zeigler76] Шаблон:Cite book
- [Zeigler84] Шаблон:Cite book
- [ZKP00] Шаблон:Cite book
- [HZ06] M. H. Hwang and Bernard Zeigler, ``A Reachable Graph of Finite and Deterministic DEVS Networks``, Proceedings of 2006 DEVS Symposium, pp48-56, Huntsville, Alabama, USA, (Available at https://web.archive.org/web/20120726134045/http://www.acims.arizona.edu/ and http://moonho.hwang.googlepages.com/publications)
- [HZ07] M.H. Hwang and Bernard Zeigler, ``Reachability Graph of Finite & Deterministic DEVS``, IEEE Transactions on Automation Science and Engineering, Volume 6, Issue 3, 2009, pp. 454–467, http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?isnumber=5153598&arnumber=5071137&count=19&index=7
