DEVS is closed under coupling [Zeigper84] [ZPK00] . In other words, given a coupled DEVS model
N
{\displaystyle N}
, its behavior is described as an atomic DEVS model
M
{\displaystyle M}
. For a given coupled DEVS
N
{\displaystyle N}
, once we have an equivalent atomic DEVS
M
{\displaystyle M}
, behavior of
M
{\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
N
=<
X
,
Y
,
D
,
{
M
i
}
,
C
x
x
,
C
y
x
,
C
y
y
,
S
e
l
e
c
t
>
{\displaystyle N=<X,Y,D,\{M_{i}\},C_{xx},C_{yx},C_{yy},Select>}
, its behavior is described as an atomic DEVS model
M
=<
X
,
Y
,
S
,
s
0
,
t
a
,
δ
e
x
t
,
δ
i
n
t
,
λ
>
{\displaystyle M=<X,Y,S,s_{0},ta,\delta _{ext},\delta _{int},\lambda >}
where
X
{\displaystyle X}
and
Y
{\displaystyle Y}
are the input event set and the output event set, respectively.
S
=
×
i
∈
D
Q
i
{\displaystyle S={\underset {i\in D}{\times }}Q_{i}}
is the partial state set where
Q
i
=
{
(
s
i
,
t
e
i
)
|
s
i
∈
S
i
,
t
e
i
∈
(
T
∩
[
0
,
t
a
i
(
s
i
)
]
)
}
{\displaystyle Q_{i}=\{(s_{i},t_{ei})|s_{i}\in S_{i},t_{ei}\in (\mathbb {T} \cap [0,ta_{i}(s_{i})])\}}
is the total state set of component
i
∈
D
{\displaystyle i\in D}
(Refer to View1 of Behavior of DEVS ), where
T
=
[
0
,
∞
)
{\displaystyle \mathbb {T} =[0,\infty )}
is the set of non-negative real numbers.
s
0
=
×
i
∈
D
q
0
i
{\displaystyle s_{0}={\underset {i\in D}{\times }}q_{0i}}
is the initial state set where
q
0
i
=
(
s
0
i
,
0
)
{\displaystyle q_{0i}=(s_{0i},0)}
is the total initial state of component
i
∈
D
{\displaystyle i\in D}
.
t
a
:
S
→
T
∞
{\displaystyle ta:S\rightarrow \mathbb {T} ^{\infty }}
is the time advance function, where
T
∞
=
[
0
,
∞
]
{\displaystyle \mathbb {T} ^{\infty }=[0,\infty ]}
is the set of non-negative real numbers plus infinity.Given
s
=
(
…
,
(
s
i
,
t
e
i
)
,
…
)
{\displaystyle s=(\ldots ,(s_{i},t_{ei}),\ldots )}
,
t
a
(
s
)
=
min
{
t
a
i
(
s
i
)
−
t
e
i
|
i
∈
D
}
.
{\displaystyle ta(s)=\min\{ta_{i}(si)-t_{ei}|i\in D\}.}
δ
e
x
t
:
Q
×
X
→
S
{\displaystyle \delta _{ext}:Q\times X\rightarrow S}
is the external state function. Given a total state
q
=
(
s
,
t
e
)
{\displaystyle q=(s,t_{e})}
where
s
=
(
…
,
(
s
i
,
t
e
i
)
,
…
)
,
t
e
∈
(
T
∩
[
0
,
t
a
(
s
)
]
)
{\displaystyle s=(\ldots ,(s_{i},t_{ei}),\ldots ),t_{e}\in (\mathbb {T} \cap [0,ta(s)])}
, and input event
x
∈
X
{\displaystyle x\in X}
, the next state is given by
δ
e
x
t
(
q
,
x
)
=
s
′
=
(
…
,
(
s
i
′
,
t
e
i
′
)
,
…
)
{\displaystyle \delta _{ext}(q,x)=s'=(\ldots ,(s_{i}',t_{ei}'),\ldots )}
where
(
s
i
′
,
t
e
i
′
)
=
{
(
δ
e
x
t
(
s
i
,
t
e
i
,
x
i
)
,
0
)
if
(
x
,
x
i
)
∈
C
x
x
(
s
i
,
t
e
i
)
otherwise
.
{\displaystyle (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}}}
Given the partial state
s
=
(
…
,
(
s
i
,
t
e
i
)
,
…
)
∈
S
{\displaystyle s=(\ldots ,(s_{i},t_{ei}),\ldots )\in S}
, let
I
M
M
(
s
)
=
{
i
∈
D
|
t
a
i
(
s
i
)
=
t
a
(
s
)
}
{\displaystyle IMM(s)=\{i\in D|ta_{i}(s_{i})=ta(s)\}}
denote the set of imminent components . The firing component
i
∗
∈
D
{\displaystyle i^{*}\in D}
which triggers the internal state transition and an output event is determined by
i
∗
=
S
e
l
e
c
t
(
I
M
M
(
s
)
)
.
{\displaystyle i^{*}=Select(IMM(s)).}
δ
i
n
t
:
S
→
S
{\displaystyle \delta _{int}:S\rightarrow S}
is the internal state function. Given a partial state
s
=
(
…
,
(
s
i
,
t
e
i
)
,
…
)
{\displaystyle s=(\ldots ,(s_{i},t_{ei}),\ldots )}
, the next state is given by
δ
i
n
t
(
s
)
=
s
′
=
(
…
,
(
s
i
′
,
t
e
i
′
)
,
…
)
{\displaystyle \delta _{int}(s)=s'=(\ldots ,(s_{i}',t_{ei}'),\ldots )}
where
(
s
i
′
,
t
e
i
′
)
=
{
(
δ
i
n
t
(
s
i
)
,
0
)
if
i
=
i
∗
(
δ
e
x
t
(
s
i
,
t
e
i
,
x
i
)
,
0
)
if
(
λ
i
∗
(
s
i
∗
)
,
x
i
)
∈
C
y
x
(
s
i
,
t
e
i
)
otherwise
.
{\displaystyle (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}}}
λ
:
S
→
Y
ϕ
{\displaystyle \lambda :S\rightarrow Y^{\phi }}
is the output function. Given a partial state
s
=
(
…
,
(
s
i
,
t
e
i
)
,
…
)
{\displaystyle s=(\ldots ,(s_{i},t_{ei}),\ldots )}
,
λ
(
s
)
=
{
ϕ
if
λ
i
∗
(
s
i
∗
)
=
ϕ
C
y
y
(
λ
i
∗
(
s
i
∗
)
)
otherwise
.
{\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
N
=<
X
,
Y
,
D
,
{
M
i
}
,
C
x
x
,
C
y
x
,
C
y
y
,
S
e
l
e
c
t
>
{\displaystyle N=<X,Y,D,\{M_{i}\},C_{xx},C_{yx},C_{yy},Select>}
, its behavior is described as an atomic DEVS model
M
=<
X
,
Y
,
S
,
s
0
,
t
a
,
δ
e
x
t
,
δ
i
n
t
,
λ
>
{\displaystyle M=<X,Y,S,s_{0},ta,\delta _{ext},\delta _{int},\lambda >}
where
X
{\displaystyle X}
and
Y
{\displaystyle Y}
are the input event set and the output event set, respectively.
S
=
×
i
∈
D
Q
i
{\displaystyle S={\underset {i\in D}{\times }}Q_{i}}
is the partial state set where
Q
i
=
{
(
s
i
,
t
s
i
,
t
e
i
)
|
s
i
∈
S
i
,
t
s
i
∈
T
∞
,
t
e
i
∈
(
T
∩
[
0
,
t
s
i
]
)
}
{\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 [0,t_{si}])\}}
is the total state set of component
i
∈
D
{\displaystyle i\in D}
(Refer to View2 of Behavior of DEVS ).
s
0
=
×
i
∈
D
q
0
i
{\displaystyle s_{0}={\underset {i\in D}{\times }}q_{0i}}
is the initial state set where
q
0
i
=
(
s
0
i
,
t
a
i
(
s
0
i
)
,
0
)
{\displaystyle q_{0i}=(s_{0i},ta_{i}(s_{0i}),0)}
is the total initial state of component
i
∈
D
{\displaystyle i\in D}
.
t
a
:
S
→
T
∞
{\displaystyle ta:S\rightarrow \mathbb {T} ^{\infty }}
is the time advance function. Given
s
=
(
…
,
(
s
i
,
t
s
i
,
t
e
i
)
,
…
)
{\displaystyle s=(\ldots ,(s_{i},t_{si},t_{ei}),\ldots )}
,
t
a
(
s
)
=
min
{
t
s
i
−
t
e
i
|
i
∈
D
}
.
{\displaystyle ta(s)=\min\{t_{si}-t_{ei}|i\in D\}.}
δ
e
x
t
:
Q
×
X
→
S
×
{
0
,
1
}
{\displaystyle \delta _{ext}:Q\times X\rightarrow S\times \{0,1\}}
is the external state function. Given a total state
q
=
(
s
,
t
s
,
t
e
)
{\displaystyle q=(s,t_{s},t_{e})}
where
s
=
(
…
,
(
s
i
,
t
s
i
,
t
e
i
)
,
…
)
,
t
s
∈
T
∞
,
t
e
∈
(
T
∩
[
0
,
t
s
]
)
{\displaystyle s=(\ldots ,(s_{i},t_{si},t_{ei}),\ldots ),t_{s}\in \mathbb {T} ^{\infty },t_{e}\in (\mathbb {T} \cap [0,t_{s}])}
, and input event
x
∈
X
{\displaystyle x\in X}
, the next state is given by
δ
e
x
t
(
q
,
x
)
=
(
(
…
,
(
s
i
′
,
t
s
i
′
,
t
e
i
′
)
,
…
)
,
b
)
{\displaystyle \delta _{ext}(q,x)=((\ldots ,(s_{i}',t_{si}',t_{ei}'),\ldots ),b)}
where
(
s
i
′
,
t
s
i
′
,
t
e
i
′
)
=
{
(
s
i
′
,
t
a
i
(
s
i
′
)
,
0
)
if
(
x
,
x
i
)
∈
C
x
x
,
δ
e
x
t
(
s
i
,
t
s
i
,
t
e
i
,
x
i
)
=
(
s
i
′
,
1
)
(
s
i
′
,
t
s
i
,
t
e
i
)
if
(
x
,
x
i
)
∈
C
x
x
,
δ
e
x
t
(
s
i
,
t
s
i
,
t
e
i
,
x
i
)
=
(
s
i
′
,
0
)
(
s
i
,
t
e
i
)
otherwise
{\displaystyle (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_{ei})&{\text{otherwise}}\end{cases}}}
and
b
=
{
1
if
∃
i
∈
D
:
(
x
,
x
i
)
∈
C
x
x
,
δ
e
x
t
(
s
i
,
t
s
i
,
t
e
i
,
x
i
)
=
(
s
i
′
,
1
)
0
otherwise
.
{\displaystyle 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}}}
Given the partial state
s
=
(
…
,
(
s
i
,
t
s
i
,
t
e
i
)
,
…
)
∈
S
{\displaystyle s=(\ldots ,(s_{i},t_{si},t_{ei}),\ldots )\in S}
, let
I
M
M
(
s
)
=
{
i
∈
D
|
t
s
i
−
t
e
i
=
t
a
(
s
)
}
{\displaystyle IMM(s)=\{i\in D|t_{si}-t_{ei}=ta(s)\}}
denote the set of imminent components . The firing component
i
∗
∈
D
{\displaystyle i^{*}\in D}
which triggers the internal state transition and an output event is determined by
i
∗
=
S
e
l
e
c
t
(
I
M
M
(
s
)
)
.
{\displaystyle i^{*}=Select(IMM(s)).}
δ
i
n
t
:
S
→
S
{\displaystyle \delta _{int}:S\rightarrow S}
is the internal state function. Given a partial state
s
=
(
…
,
(
s
i
,
t
s
i
,
t
e
i
)
,
…
)
{\displaystyle s=(\ldots ,(s_{i},t_{si},t_{ei}),\ldots )}
, the next state is given by
δ
i
n
t
(
s
)
=
s
′
=
(
…
,
(
s
i
′
,
t
s
i
′
,
t
e
i
′
)
,
…
)
{\displaystyle \delta _{int}(s)=s'=(\ldots ,(s_{i}',t_{si}',t_{ei}'),\ldots )}
where
(
s
i
′
,
t
s
i
′
,
t
e
i
′
)
=
{
(
s
i
′
,
t
a
i
(
s
i
′
)
,
0
)
if
i
=
i
∗
,
δ
i
n
t
(
s
i
)
=
s
i
′
,
(
s
i
′
,
t
a
i
(
s
i
′
)
,
0
)
if
(
λ
i
∗
(
s
i
∗
)
,
x
i
)
∈
C
y
x
,
δ
e
x
t
(
s
i
,
t
s
i
,
t
e
i
,
x
i
)
=
(
s
′
,
1
)
(
s
i
′
,
t
s
i
,
t
e
i
)
if
(
λ
i
∗
(
s
i
∗
)
,
x
i
)
∈
C
y
x
,
δ
e
x
t
(
s
i
,
t
s
i
,
t
e
i
,
x
i
)
=
(
s
′
,
0
)
(
s
i
,
t
s
i
,
t
e
i
)
otherwise
.
{\displaystyle (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}}}
λ
:
S
→
Y
ϕ
{\displaystyle \lambda :S\rightarrow Y^{\phi }}
is the output function. Given a partial state
s
=
(
…
,
(
s
i
,
t
s
i
,
t
e
i
)
,
…
)
{\displaystyle s=(\ldots ,(s_{i},t_{si},t_{ei}),\ldots )}
,
λ
(
s
)
=
{
ϕ
if
λ
i
∗
(
s
i
∗
)
=
ϕ
C
y
y
(
λ
i
∗
(
s
i
∗
)
)
otherwise
.
{\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.,
|
D
|
>
0
{\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
q
=
(
s
,
t
e
)
∈
Q
{\displaystyle q=(s,t_{e})\in Q}
where
s
=
(
…
,
(
s
i
,
t
e
i
)
,
…
)
{\displaystyle s=(\ldots ,(s_{i},t_{ei}),\ldots )}
If unit event segment
ω
{\displaystyle \omega }
is the null event segment , i.e.
ω
=
ϵ
[
t
,
t
+
d
t
]
{\displaystyle \omega =\epsilon _{[t,t+dt]}}
, the state trajectory in terms of Timed Event System is
Δ
(
q
,
ω
)
=
(
(
…
,
(
s
i
,
t
e
i
+
d
t
)
,
…
)
,
t
e
+
d
t
)
.
{\displaystyle \Delta (q,\omega )=((\ldots ,(s_{i},t_{ei}+dt),\ldots ),t_{e}+dt).}
For View2
Given a total state
q
=
(
s
,
t
s
,
t
e
)
∈
Q
{\displaystyle q=(s,t_{s},t_{e})\in Q}
where
s
=
(
…
,
(
s
i
,
t
s
i
,
t
e
i
)
,
…
)
{\displaystyle s=(\ldots ,(s_{i},t_{si},t_{ei}),\ldots )}
If unit event segment
ω
{\displaystyle \omega }
is the null event segment , i.e.
ω
=
ϵ
[
t
,
t
+
d
t
]
{\displaystyle \omega =\epsilon _{[t,t+dt]}}
, the state trajectory in terms of Timed Event System is
Δ
(
q
,
ω
)
=
(
(
…
,
(
s
i
,
t
s
i
,
t
e
i
+
d
t
)
,
…
)
,
t
s
,
t
e
+
d
t
)
.
{\displaystyle \Delta (q,\omega )=((\ldots ,(s_{i},t_{si},t_{ei}+dt),\ldots ),t_{s},t_{e}+dt).}
The behavior of a couple DEVS network whose all sub-components are deterministic DEVS models can be non-deterministic if
S
e
l
e
c
t
(
I
M
M
(
s
)
)
{\displaystyle Select(IMM(s))}
is non-deterministic .
See also
References
[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 .