Misplaced Pages

This article has multiple issues. Please help improve it or discuss these issues on the talk page. (Learn how and when to remove these messages) The topic of this article may not meet Misplaced Pages's general notability guideline. Please help to demonstrate the notability of the topic by citing reliable secondary sources that are independent of the topic and provide significant coverage of it beyond a mere trivial mention. If notability cannot be shown, the article is likely to be merged, redirected, or deleted. Find sources: "Behavior of coupled DEVS" – news · newspapers · books · scholar · JSTOR (November 2012) (Learn how and when to remove this message) This article may need to be rewritten to comply with Misplaced Pages's quality standards. You can help. The talk page may contain suggestions. (December 2020) This article may be too technical for most readers to understand. Please help improve it to make it understandable to non-experts, without removing the technical details. (November 2012) (Learn how and when to remove this message) (Learn how and when to remove this message)

In theoretical computer science, DEVS is closed under coupling . In other words, given a coupled DEVS model ${\displaystyle N}$, its behavior is described as an atomic DEVS model ${\displaystyle M}$. For a given coupled DEVS ${\displaystyle N}$, once we have an equivalent atomic DEVS ${\displaystyle M}$, behavior of ${\displaystyle M}$ 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 ${\displaystyle N=<X,Y,D,\{M_{i}\},C_{xx},C_{yx},C_{yy},Select>}$, its behavior is described as an atomic DEVS model ${\displaystyle M=<X,Y,S,s_{0},ta,\delta _{ext},\delta _{int},\lambda >}$

where

• ${\displaystyle X}$ and ${\displaystyle Y}$ are the input event set and the output event set, respectively.
• ${\displaystyle S={\underset {i\in D}{\times }}Q_{i}}$ is the partial state set where ${\displaystyle Q_{i}=\{(s_{i},t_{ei})|s_{i}\in S_{i},t_{ei}\in (\mathbb {T} \cap )\}}$ is the total state set of component ${\displaystyle i\in D}$ (Refer to View1 of Behavior of DEVS), where ${\displaystyle \mathbb {T} =[0,\infty )}$ is the set of non-negative real numbers.
• ${\displaystyle s_{0}={\underset {i\in D}{\times }}q_{0i}}$ is the initial state set where ${\displaystyle q_{0i}=(s_{0i},0)}$ is the total initial state of component ${\displaystyle i\in D}$.
• ${\displaystyle ta:S\rightarrow \mathbb {T} ^{\infty }}$ is the time advance function, where ${\displaystyle \mathbb {T} ^{\infty }=}$ is the set of non-negative real numbers plus infinity. Given ${\displaystyle s=(\ldots ,(s_{i},t_{ei}),\ldots )}$, ${\displaystyle ta(s)=\min\{ta_{i}(si)-t_{ei}|i\in D\}.}$

• ${\displaystyle \delta _{ext}:Q\times X\rightarrow S}$ is the external state function. Given a total state ${\displaystyle q=(s,t_{e})}$ where ${\displaystyle s=(\ldots ,(s_{i},t_{ei}),\ldots ),t_{e}\in (\mathbb {T} \cap )}$, and input event ${\displaystyle x\in X}$, the next state is given by ${\displaystyle \delta _{ext}(q,x)=s'=(\ldots ,(s_{i}',t_{ei}'),\ldots )}$

where

Given the partial state ${\displaystyle s=(\ldots ,(s_{i},t_{ei}),\ldots )\in S}$, let ${\displaystyle IMM(s)=\{i\in D|ta_{i}(s_{i})=ta(s)\}}$ denote the set of imminent components. The firing component ${\displaystyle i^{*}\in D}$ which triggers the internal state transition and an output event is determined by

• ${\displaystyle \delta _{int}:S\rightarrow S}$ is the internal state function. Given a partial state ${\displaystyle s=(\ldots ,(s_{i},t_{ei}),\ldots )}$, the next state is given by ${\displaystyle \delta _{int}(s)=s'=(\ldots ,(s_{i}',t_{ei}'),\ldots )}$

where

• ${\displaystyle \lambda :S\rightarrow Y^{\phi }}$ is the output function. Given a partial state ${\displaystyle s=(\ldots ,(s_{i},t_{ei}),\ldots )}$, ${\displaystyle \lambda (s)={\begin{cases}\phi &{\text{if }}\lambda _{i^{*}}(s_{i^{*}})=\phi \\C_{yy}(\lambda _{i^{*}}(s_{i^{*}}))&{\text{otherwise}}.\end{cases}}}$

View2: Total states = states * lifespan * elapsed times

Given a coupled DEVS model ${\displaystyle N=<X,Y,D,\{M_{i}\},C_{xx},C_{yx},C_{yy},Select>}$, its behavior is described as an atomic DEVS model ${\displaystyle M=<X,Y,S,s_{0},ta,\delta _{ext},\delta _{int},\lambda >}$

where

• ${\displaystyle X}$ and ${\displaystyle Y}$ are the input event set and the output event set, respectively.
• ${\displaystyle S={\underset {i\in D}{\times }}Q_{i}}$ is the partial state set where ${\displaystyle 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 )\}}$ is the total state set of component ${\displaystyle i\in D}$ (Refer to View2 of Behavior of DEVS).
• ${\displaystyle s_{0}={\underset {i\in D}{\times }}q_{0i}}$ is the initial state set where ${\displaystyle q_{0i}=(s_{0i},ta_{i}(s_{0i}),0)}$ is the total initial state of component ${\displaystyle i\in D}$.
• ${\displaystyle ta:S\rightarrow \mathbb {T} ^{\infty }}$ is the time advance function. Given ${\displaystyle s=(\ldots ,(s_{i},t_{si},t_{ei}),\ldots )}$, ${\displaystyle ta(s)=\min\{t_{si}-t_{ei}|i\in D\}.}$

• ${\displaystyle \delta _{ext}:Q\times X\rightarrow S\times \{0,1\}}$ is the external state function. Given a total state ${\displaystyle q=(s,t_{s},t_{e})}$ where ${\displaystyle s=(\ldots ,(s_{i},t_{si},t_{ei}),\ldots ),t_{s}\in \mathbb {T} ^{\infty },t_{e}\in (\mathbb {T} \cap )}$, and input event ${\displaystyle x\in X}$, the next state is given by ${\displaystyle \delta _{ext}(q,x)=((\ldots ,(s_{i}',t_{si}',t_{ei}'),\ldots ),b)}$

where

and

Given the partial state ${\displaystyle s=(\ldots ,(s_{i},t_{si},t_{ei}),\ldots )\in S}$, let ${\displaystyle IMM(s)=\{i\in D|t_{si}-t_{ei}=ta(s)\}}$ denote the set of imminent components. The firing component ${\displaystyle i^{*}\in D}$ which triggers the internal state transition and an output event is determined by

• ${\displaystyle \delta _{int}:S\rightarrow S}$ is the internal state function. Given a partial state ${\displaystyle s=(\ldots ,(s_{i},t_{si},t_{ei}),\ldots )}$, the next state is given by ${\displaystyle \delta _{int}(s)=s'=(\ldots ,(s_{i}',t_{si}',t_{ei}'),\ldots )}$

where

• ${\displaystyle \lambda :S\rightarrow Y^{\phi }}$ is the output function. Given a partial state ${\displaystyle s=(\ldots ,(s_{i},t_{si},t_{ei}),\ldots )}$, ${\displaystyle \lambda (s)={\begin{cases}\phi &{\text{if }}\lambda _{i^{*}}(s_{i^{*}})=\phi \\C_{yy}(\lambda _{i^{*}}(s_{i^{*}}))&{\text{otherwise}}.\end{cases}}}$

Time passage

Since in a coupled DEVS model with non-empty sub-components, i.e., ${\displaystyle |D|>0}$, 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 ${\displaystyle q=(s,t_{e})\in Q}$ where ${\displaystyle s=(\ldots ,(s_{i},t_{ei}),\ldots )}$

If unit event segment ${\displaystyle \omega }$ is the null event segment, i.e. ${\displaystyle \omega =\epsilon _{}}$, the state trajectory in terms of Timed Event System is

For View2

Given a total state ${\displaystyle q=(s,t_{s},t_{e})\in Q}$ where ${\displaystyle s=(\ldots ,(s_{i},t_{si},t_{ei}),\ldots )}$

If unit event segment ${\displaystyle \omega }$ is the null event segment, i.e. ${\displaystyle \omega =\epsilon _{}}$, the state trajectory in terms of Timed Event System is

Remarks

1. The behavior of a couple DEVS network whose all sub-components are deterministic DEVS models can be non-deterministic if ${\displaystyle Select(IMM(s))}$ is non-deterministic.

See also

• DEVS
• Behavior of Atomic DEVS
• Simulation Algorithms for Coupled DEVS
• Simulation Algorithms for Atomic DEVS

References

• Bernard Zeigler (1984). Multifacetted Modeling and Discrete Event Simulation. Academic Press, London; Orlando. ISBN 978-0-12-778450-2.
• 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.

• Automata (computation)
• Formal specification languages