Английская Википедия:Behavior of coupled DEVS
Шаблон:Multiple issues In theoretical computer science, DEVS is closed under coupling [Zeigper84] [ZPK00]. In other words, given a coupled DEVS model <math> N </math>, its behavior is described as an atomic DEVS model <math> M</math>. For a given coupled DEVS <math> N </math>, once we have an equivalent atomic DEVS <math> M </math>, behavior of <math> M </math> can be referred to behavior of atomic DEVS which is based on Timed Event System.
Similar to behavior of atomic DEVS, behavior of the Coupled DEVS class is described depending on definition of the total state set and its handling as follows.
View1: Total states = states * elapsed times
Given a coupled DEVS model <math> N = <X,Y,D,\{M_i\},C_{xx}, C_{yx}, C_{yy}, Select></math>, its behavior is described as an atomic DEVS model <math> M = <X,Y,S,s_0,ta, \delta_{ext}, \delta_{int}, \lambda> </math>
where
- <math>X</math> and <math>Y</math> are the input event set and the output event set, respectively.
- <math>S=\underset{i \in D}\times Q_i</math> is the partial state set where <math>Q_i=\{(s_i,t_{ei})| s_i \in S_i, t_{ei} \in (\mathbb{T} \cap [0, ta_i(s_i)])\} </math> is the total state set of component <math> i \in D</math> (Refer to View1 of Behavior of DEVS), where <math> \mathbb{T}=[0,\infty)</math> is the set of non-negative real numbers.
- <math>s_0=\underset{i \in D}\times q_{0i}</math> is the initial state set where <math>q_{0i}=(s_{0i},0)</math> is the total initial state of component <math> i \in D </math>.
- <math>ta:S \rightarrow \mathbb{T}^\infty </math> is the time advance function, where <math> \mathbb{T}^\infty=[0,\infty]</math> is the set of non-negative real numbers plus infinity. Given <math>s=(\ldots, (s_{i},t_{ei}),\ldots)</math>, <math> ta(s)= \min\{ ta_i(si) - t_{ei}| i \in D\}.
</math>
- <math>\delta_{ext}:Q \times X \rightarrow S </math> is the external state function. Given a total state <math>q=(s,t_e)</math> where <math>s=(\ldots, (s_{i}, t_{ei}),\ldots), t_e \in (\mathbb{T}\cap [0,ta(s)] )</math>, and input event <math> x \in X </math>, the next state is given by <math> \delta_{ext}(q, x)=s'=(\ldots,(s_i', t_{ei}'), \ldots) </math>
where
(s_i', t_{ei}')= \begin{cases} (\delta_{ext}(s_i, t_{ei}, x_i),0) & \text{if } (x, x_i) \in C_{xx}\\ (s_i, t_{ei}) & \text{otherwise}. \end{cases}
</math>Given the partial state <math>s=(\ldots,(s_i, t_{ei}),\ldots) \in S </math>, let <math> IMM(s)=\{i \in D| ta_i(s_i) = ta(s) \} </math> denote the set of imminent components. The firing component <math> i^* \in D </math> which triggers the internal state transition and an output event is determined by
- <math>\delta_{int}:S \rightarrow S </math> is the internal state function. Given a partial state <math> s=(\ldots, (s_{i}, t_{ei}),\ldots)</math>, the next state is given by <math> \delta_{int}(s)=s'=(\ldots,(s_i', t_{ei}'), \ldots) </math>
where
(s_i', t_{ei}')= \begin{cases} (\delta_{int}(s_i),0) & \text{if } i = i^*\\ (\delta_{ext}(s_i, t_{ei}, x_i),0) & \text{if } (\lambda_{i^*}(s_{i^*}), x_i) \in C_{yx}\\ (s_i, t_{ei}) & \text{otherwise}. \end{cases}
</math>- <math>\lambda:S \rightarrow Y^\phi </math> is the output function. Given a partial state <math> s=(\ldots, (s_{i}, t_{ei}),\ldots)</math>, <math> \lambda(s)=
\begin{cases} \phi &\text{if } \lambda_{i^*}(s_{i^*})=\phi \\ C_{yy}(\lambda_{i^*}(s_{i^*})) &\text{otherwise}. \end{cases}
</math>
View2: Total states = states * lifespan * elapsed times
Given a coupled DEVS model <math> N = <X,Y,D,\{M_i\},C_{xx}, C_{yx}, C_{yy}, Select></math>, its behavior is described as an atomic DEVS model <math> M = <X,Y,S,s_0,ta, \delta_{ext}, \delta_{int}, \lambda> </math>
where
- <math>X</math> and <math>Y</math> are the input event set and the output event set, respectively.
- <math>S=\underset{i \in D}\times Q_i</math> is the partial state set where <math>Q_i=\{(s_i,t_{si}, t_{ei})| s_i \in S_i, t_{si} \in \mathbb{T}^\infty, t_{ei} \in (\mathbb{T} \cap [0, t_{si}])\} </math> is the total state set of component <math> i \in D</math> (Refer to View2 of Behavior of DEVS).
- <math>s_0=\underset{i \in D}\times q_{0i}</math> is the initial state set where <math>q_{0i}=(s_{0i},ta_i(s_{0i}),0)</math> is the total initial state of component <math> i \in D </math>.
- <math>ta:S \rightarrow \mathbb{T}^\infty </math> is the time advance function. Given <math>s=(\ldots, (s_{i},t_{si},t_{ei}),\ldots)</math>, <math> ta(s)= \min\{ t_{si} - t_{ei}| i \in D\}.
</math>
- <math>\delta_{ext}:Q \times X \rightarrow S \times \{0, 1\} </math> is the external state function. Given a total state <math>q=(s,t_s,t_e)</math> where <math>s=(\ldots, (s_{i}, t_{si},t_{ei}),\ldots), t_s \in \mathbb{T}^\infty, t_e \in (\mathbb{T}\cap [0,t_s] )</math>, and input event <math> x \in X </math>, the next state is given by <math> \delta_{ext}(q, x)=((\ldots,(s_i', t_{si}', t_{ei}'), \ldots),b) </math>
where
(s_i', t_{si}', t_{ei}')= \begin{cases} (s_i', ta_i(s_i'), 0) & \text{if } (x, x_i) \in C_{xx},\delta_{ext}(s_i, t_{si}, t_{ei}, x_i)=(s_i',1)\\ (s_i', t_{si}, t_{ei} ) & \text{if } (x, x_i) \in C_{xx},\delta_{ext}(s_i, t_{si}, t_{ei}, x_i)=(s_i',0)\\ (s_i, t_{si}, t_{ei}) & \text{otherwise} \end{cases}
</math>and
b= \begin{cases} 1 & \text{if } \exists i \in D: (x, x_i) \in C_{xx},\delta_{ext}(s_i, t_{si}, t_{ei}, x_i)=(s_i',1)\\ 0 & \text{otherwise}. \end{cases}
</math>Given the partial state <math>s=(\ldots,(s_i, t_{si}, t_{ei}),\ldots) \in S </math>, let <math> IMM(s)=\{i \in D| t_{si} - t_{ei} = ta(s) \} </math> denote the set of imminent components. The firing component <math> i^* \in D </math> which triggers the internal state transition and an output event is determined by
- <math>\delta_{int}:S \rightarrow S </math> is the internal state function. Given a partial state <math> s=(\ldots, (s_{i},t_{si}, t_{ei}),\ldots)</math>, the next state is given by <math> \delta_{int}(s)=s'=(\ldots,(s_i', t_{si}', t_{ei}'), \ldots) </math>
where
(s_i', t_{si}', t_{ei}')= \begin{cases} (s_i', ta_i(s_i'),0) & \text{if } i = i^*,\delta_{int}(s_i)=s_i',\\ (s_i', ta_i(s_i'),0) & \text{if } (\lambda_{i^*}(s_{i^*}), x_i) \in C_{yx},\delta_{ext}(s_i, t_{si}, t_{ei}, x_i)=(s', 1)\\ (s_i', t_{si}, t_{ei}) & \text{if } (\lambda_{i^*}(s_{i^*}), x_i) \in C_{yx},\delta_{ext}(s_i, t_{si}, t_{ei}, x_i)=(s', 0)\\ (s_i, t_{si}, t_{ei}) & \text{otherwise}. \end{cases}
</math>- <math>\lambda:S \rightarrow Y^\phi </math> is the output function. Given a partial state <math> s=(\ldots, (s_{i}, t_{si}, t_{ei}),\ldots)</math>, <math> \lambda(s)=
\begin{cases} \phi &\text{if } \lambda_{i^*}(s_{i^*})=\phi \\ C_{yy}(\lambda_{i^*}(s_{i^*})) &\text{otherwise}. \end{cases}
</math>
Time passage
Since in a coupled DEVS model with non-empty sub-components, i.e., <math> |D|>0</math>, the number of clocks which trace their elapsed times are multiple, so time passage of the model is noticeable.
- For View1
Given a total state <math> q=(s,t_e) \in Q </math> where <math> s = (\ldots,(s_i, t_{ei}),\ldots) </math>
If unit event segment <math> \omega</math> is the null event segment, i.e. <math> \omega=\epsilon_{[t, t+dt]}</math>, the state trajectory in terms of Timed Event System is
- For View2
Given a total state <math> q=(s,t_s,t_e) \in Q </math> where <math> s = (\ldots,(s_i, t_{si}, t_{ei}),\ldots) </math>
If unit event segment <math> \omega</math> is the null event segment, i.e. <math> \omega=\epsilon_{[t, t+dt]}</math>, the state trajectory in terms of Timed Event System is
Remarks
- The behavior of a couple DEVS network whose all sub-components are deterministic DEVS models can be non-deterministic if <math> Select(IMM(s))</math> is non-deterministic.
See also
- DEVS
- Behavior of Atomic DEVS
- Simulation Algorithms for Coupled DEVS
- Simulation Algorithms for Atomic DEVS
References
- [Zeigler84] Шаблон:Cite book
- [ZKP00] Шаблон:Cite book
