Behavior of DEVS
# 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. 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}}=<X,Y,S,s_{0},ta,\delta _{ext},\delta _{int},\lambda >$ 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}}=<Z,Q,Q_{0},Q_{A},\Delta >$ 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.

## View 2: total states = states * lifespans * elapsed times

Suppose that a DEVS model, ${\mathcal {M}}=<X,Y,S,s_{0},ta,\delta _{ext},\delta _{int},\lambda >$ 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}}=<Z,Q,Q_{0},Q_{A},\Delta >$ 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.

## Comparison of View1 and View2

### Features of View1

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 [Zeigler84] [ZPK00]. 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, 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 $\Delta$.

### Features of View2

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, modellers 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.

