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, ${ℳ}=<X,Y,S,s_0,ta,{\delta }_{ext},{\delta }_{int},\lambda >$ has

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

Then the DEVS model, ${ℳ}$ is a Timed Event System ${𝒢}=<Z,Q,Q_0,Q_A,\mathrm{\Delta }>$ where

• The event set $Z=X\cup Y^{\varphi }$.
• The state set $Q=Q_A\cup Q_N$ where $Q_N=\{\overline{s}\in ̸S\}$.
• The set of initial states $Q_0=\{(s_0,0)\}$.
• The set of accepting states $Q_A={ℳ}.Q.$
• The set of state trajectories $\mathrm{\Delta }\subseteq Q\times {\mathrm{\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 {\mathrm{\Omega }}_{Z,[t_l,t_u]}$ so $(q,\omega ,q)\in \mathrm{\Delta }.$

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

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

$(q,\omega ,(s,t_e+dt))\in \mathrm{\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 \mathrm{\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^{\varphi }$,

$\{\begin{array}{ll}(q,\omega ,({\delta }_{int}(s),0))\in \mathrm{\Delta }& \text{<mrow data-mjx-texclass="ORD">if</mrow>}{t}_e=ta(s),y=\lambda (s)\\ (q,\omega ,\overline{s})& \text{<mrow data-mjx-texclass="ORD">otherwise</mrow>}.\end{array}$

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, ${ℳ}=<X,Y,S,s_0,ta,{\delta }_{ext},{\delta }_{int},\lambda >$ has

1. the total state set $Q=\{(s,t_s,t_e)|s\in S,t_s\in {\mathbb{𝕋}}^{\mathrm{\infty }},t_e\in (\mathbb{𝕋}\cap [0,t_s])\}$ where $t_s$ denotes lifespan of state $s$, $t_e$ denotes elapsed time since last $t_s$update, and ${\mathbb{𝕋}}^{\mathrm{\infty }}=[0,\mathrm{\infty })\cup \{\mathrm{\infty }\}$ denotes the set of non-negative real numbers plus infinity,
2. the external state transition is ${\delta }_{ext}:Q\times X\to S\times \{0,1\}$.

Then the DEVS $Q={𝒟}$ is a timed event system ${𝒢}=<Z,Q,Q_0,Q_A,\mathrm{\Delta }>$ where

• The event set $Z=X\cup Y^{\varphi }$.
• The state set $Q=Q_A\cup Q_N$ where $Q_N=\{\overline{s}\in ̸S\}$.
• The set of initial states$Q_0=\{(s_0,ta(s_0),0)\}$.
• The set of acceptance states $Q_A={ℳ}.Q$.
• The set of state trajectories $\mathrm{\Delta }\subseteq Q\times {\mathrm{\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 {\mathrm{\Omega }}_{Z,[t_l,t_u]}$ so $(q,\omega ,q)\in \mathrm{\Delta }.$

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

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

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

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

$\{\begin{array}{ll}(q,\omega ,(s^{\prime },ta(s^{\prime }),0))\in \mathrm{\Delta }& \text{<mrow data-mjx-texclass="ORD">if</mrow>}{\delta }_{ext}(s,t_s,t_e,x)=(s^{\prime },1),\\ (q,\omega ,(s^{\prime },t_s,t_e))\in \mathrm{\Delta }& \text{<mrow data-mjx-texclass="ORD">otherwise<mo>,</mo>i<mo stretchy="false">.</mo>e<mo stretchy="false">.</mo></mrow>}{\delta }_{ext}(s,t_s,t_e,x)=(s^{\prime },0).\end{array}$

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^{\varphi }$,

$\{\begin{array}{ll}(q,\omega ,(s^{\prime },ta(s^{\prime }),0))\in \mathrm{\Delta }& \text{<mrow data-mjx-texclass="ORD">if</mrow>}{t}_e=t_s,y=\lambda (s),{\delta }_{int}(s)=s^{\prime },\\ (q,\omega ,\overline{s})\in \mathrm{\Delta }& \text{<mrow data-mjx-texclass="ORD">otherwise</mrow>}.\end{array}$

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

$q=(s,t_e)\in Q$

and

$ta(s)=\sigma$

where $\sigma$ is the remaining time [Zeigler84] [ZPK00]. In other words, the set of partial states is indeed $S=\{(d,\sigma )|d\in S^{\prime },\sigma \in {\mathbb{𝕋}}^{\mathrm{\infty }}\}$ where $S^{\prime }$ 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, modellers have to update the remaining time

$\sigma =\sigma -t_e$

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

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 $\mathrm{\Delta }$.

Features of View2

View2 has been introduced by Hwang and Zeigler[HZ06][HZ07] 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^{\prime },1)$. If the DEVS model needs to ignore $x$ in terms of the lifespan control, modellers can use ${\delta }_{ext}(q,x)=(s^{\prime },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 [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