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

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

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

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

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

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

$\displaystyle{ \, (q, \omega, (s, t_e+dt)) \in \Delta. }$

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

$\displaystyle{ (q, \omega, (\delta_{ext}(q,x), 0)) \in \Delta. }$

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

$\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} }$

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

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

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

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

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

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

$\displaystyle{ (q, \omega, (s, t_s, t_e+dt)) \in \Delta. }$

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

$\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} }$

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

$\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} }$

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

$\displaystyle{ \, ta(s)=\sigma }$

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

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

$\displaystyle{ \, \sigma = \sigma - t_e }$

in the external state transition function $\displaystyle{ \delta_{ext} }$ that is the responsibility of the modellers.

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

Features of View2

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

$\displaystyle{ \, \sigma = t_s - t_e. }$

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

Unlike View1, since the remaining time $\displaystyle{ \sigma }$ is not component of $\displaystyle{ S }$ in nature, if the number of states, i.e. $\displaystyle{ |S| }$ 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].