Behavior of 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 [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]\displaystyle{ \mathcal{M}=\lt X,Y,S,s_0,ta,\delta_{ext},\delta_{int},\lambda\gt }[/math] has

1. the external state transition [math]\displaystyle{ \delta_{ext}:Q \times X \rightarrow S }[/math].
2. the total state set [math]\displaystyle{ Q=\{(s,t_e)| s \in S, t_e \in (\mathbb{T} \cap [0, ta(s)])\} }[/math] where [math]\displaystyle{ t_e }[/math] denotes elapsed time since last event and [math]\displaystyle{ \mathbb{T}=[0,\infty) }[/math] denotes the set of non-negative real numbers, and

Then the DEVS model, [math]\displaystyle{ \mathcal{M} }[/math] is a Timed Event System [math]\displaystyle{ \mathcal{G}=\lt Z,Q,Q_0,Q_A,\Delta\gt }[/math] where

• The event set [math]\displaystyle{ Z=X \cup Y^\phi }[/math].
• The state set [math]\displaystyle{ Q=Q_A \cup Q_N }[/math] where [math]\displaystyle{ Q_N=\{\bar{s} \not \in S \} }[/math].
• The set of initial states [math]\displaystyle{ \,Q_0 = \{(s_0,0)\} }[/math].
• The set of accepting states [math]\displaystyle{ Q_A = \mathcal{M}.Q. }[/math]
• The set of state trajectories [math]\displaystyle{ \Delta \subseteq Q \times \Omega_{Z,[t_l,t_u]} \times Q }[/math] is defined for two different cases: [math]\displaystyle{ q \in Q_N }[/math] and [math]\displaystyle{ q \in Q_A }[/math]. For a non-accepting state [math]\displaystyle{ q \in Q_N }[/math], there is no change together with any even segment [math]\displaystyle{ \omega \in \Omega_{Z,[t_l,t_u]} }[/math] so [math]\displaystyle{ (q,\omega,q) \in \Delta. }[/math]

For a total state [math]\displaystyle{ q=(s,t_e) \in Q_A }[/math] at time [math]\displaystyle{ t \in \mathbb{T} }[/math] and an event segment [math]\displaystyle{ \omega \in \Omega_{Z,[t_l,t_u]} }[/math] as follows.

If unit event segment [math]\displaystyle{ \omega }[/math] is the null event segment, i.e. [math]\displaystyle{ \omega=\epsilon_{[t, t+dt]} }[/math]

[math]\displaystyle{ \, (q, \omega, (s, t_e+dt)) \in \Delta. }[/math]

If unit event segment [math]\displaystyle{ \omega }[/math] is a timed event [math]\displaystyle{ \omega=(x, t) }[/math] where the event is an input event [math]\displaystyle{ x \in X }[/math],

[math]\displaystyle{ (q, \omega, (\delta_{ext}(q,x), 0)) \in \Delta. }[/math]

If unit event segment [math]\displaystyle{ \omega }[/math] is a timed event [math]\displaystyle{ \omega=(y, t) }[/math] where the event is an output event or the unobservable event [math]\displaystyle{ y \in Y^\phi }[/math],

[math]\displaystyle{ \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]\displaystyle{ \mathcal{M}=\lt X,Y,S,s_0,ta,\delta_{ext},\delta_{int},\lambda\gt }[/math] has

1. the total state set [math]\displaystyle{ 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]\displaystyle{ t_s }[/math] denotes lifespan of state [math]\displaystyle{ s }[/math], [math]\displaystyle{ t_e }[/math] denotes elapsed time since last [math]\displaystyle{ t_s }[/math]update, and [math]\displaystyle{ \mathbb{T}^\infty=[0,\infty) \cup \{ \infty \} }[/math] denotes the set of non-negative real numbers plus infinity,
2. the external state transition is [math]\displaystyle{ \delta_{ext}:Q \times X \rightarrow S \times \{0,1\} }[/math].

Then the DEVS [math]\displaystyle{ Q=\mathcal{D} }[/math] is a timed event system [math]\displaystyle{ \mathcal{G}=\lt Z,Q,Q_0,Q_A,\Delta\gt }[/math] where

• The event set [math]\displaystyle{ Z=X \cup Y^\phi }[/math].
• The state set [math]\displaystyle{ Q=Q_A \cup Q_N }[/math] where [math]\displaystyle{ Q_N=\{ \bar{s} \not \in S \} }[/math].
• The set of initial states[math]\displaystyle{ \,Q_0 = \{(s_0,ta(s_0),0)\} }[/math].
• The set of acceptance states [math]\displaystyle{ Q_A = \mathcal{M}.Q }[/math].
• The set of state trajectories [math]\displaystyle{ \Delta \subseteq Q \times \Omega_{Z,[t_l,t_u]} \times Q }[/math] is depending on two cases: [math]\displaystyle{ q \in Q_N }[/math] and [math]\displaystyle{ q \in Q_A }[/math]. For a non-accepting state [math]\displaystyle{ q \in Q_N }[/math], there is no changes together with any segment [math]\displaystyle{ \omega \in \Omega_{Z,[t_l,t_u]} }[/math] so [math]\displaystyle{ (q,\omega,q) \in \Delta. }[/math]

For a total state [math]\displaystyle{ q=(s,t_s, t_e) \in Q_A }[/math] at time [math]\displaystyle{ t \in \mathbb{T} }[/math] and an event segment [math]\displaystyle{ \omega \in \Omega_{Z,[t_l,t_u]} }[/math] as follows.

If unit event segment [math]\displaystyle{ \omega }[/math] is the null event segment, i.e. [math]\displaystyle{ \omega=\epsilon_{[t, t+dt]} }[/math]

[math]\displaystyle{ (q, \omega, (s, t_s, t_e+dt)) \in \Delta. }[/math]

If unit event segment [math]\displaystyle{ \omega }[/math] is a timed event [math]\displaystyle{ \omega=(x, t) }[/math] where the event is an input event [math]\displaystyle{ x \in X }[/math],

[math]\displaystyle{ \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]\displaystyle{ \omega }[/math] is a timed event [math]\displaystyle{ \omega=(y, t) }[/math] where the event is an output event or the unobservable event [math]\displaystyle{ y \in Y^\phi }[/math],

[math]\displaystyle{ \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]\displaystyle{ q=(s,t_e) \in Q }[/math] and

[math]\displaystyle{ \, ta(s)=\sigma }[/math]

where [math]\displaystyle{ \sigma }[/math] is the remaining time [Zeigler84] [ZPK00]. In other words, the set of partial states is indeed [math]\displaystyle{ S=\{(d,\sigma)| d \in S', \sigma \in \mathbb{T}^\infty \} }[/math] where [math]\displaystyle{ S' }[/math] is a state set.

When a DEVS model receives an input event [math]\displaystyle{ x \in X }[/math], View1 resets the elapsed time [math]\displaystyle{ t_e }[/math] by zero, if the DEVS model needs to ignore [math]\displaystyle{ x }[/math] in terms of the lifespan control, modellers have to update the remaining time

[math]\displaystyle{ \, \sigma = \sigma - t_e }[/math]

in the external state transition function [math]\displaystyle{ \delta_{ext} }[/math] that is the responsibility of the modellers.

Since the number of possible values of [math]\displaystyle{ \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]\displaystyle{ 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]\displaystyle{ 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]\displaystyle{ \sigma }[/math] as above, which is not explicitly explained in [math]\displaystyle{ \delta_{ext} }[/math] itself but in [math]\displaystyle{ \Delta }[/math].

Features of View2

View2 has been introduced by Hwang and Zeigler[HZ06][HZ07] in which given a total state [math]\displaystyle{ q=(s, t_s, t_e) \in Q }[/math], the remaining time, [math]\displaystyle{ \sigma }[/math] is computed as

[math]\displaystyle{ \, \sigma = t_s - t_e. }[/math]

When a DEVS model receives an input event [math]\displaystyle{ x \in X }[/math], View2 resets the elapsed time [math]\displaystyle{ t_e }[/math] by zero only if [math]\displaystyle{ \delta_{ext}(q,x)=(s',1) }[/math]. If the DEVS model needs to ignore [math]\displaystyle{ x }[/math] in terms of the lifespan control, modellers can use [math]\displaystyle{ \delta_{ext}(q,x)=(s',0) }[/math].

Unlike View1, since the remaining time [math]\displaystyle{ \sigma }[/math] is not component of [math]\displaystyle{ S }[/math] in nature, if the number of states, i.e. [math]\displaystyle{ |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] Bernard Zeigler (1976). Theory of Modeling and Simulation (first ed.). Wiley Interscience, New York. 
• [Zeigler84] Bernard Zeigler (1984). Multifacetted Modeling and Discrete Event Simulation. Academic Press, London; Orlando. ISBN 978-0-12-778450-2. 
• [ZKP00] Bernard Zeigler; Tag Gon Kim; Herbert Praehofer (2000). Theory of Modeling and Simulation (second ed.). Academic Press, New York. ISBN 978-0-12-778455-7. 
• [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