Concept within modeling and systems analysis
DEVS は 、 離散イベント システム仕様の略で、 状態遷移表 で記述できる離散イベント システム 、微分方程式で記述できる連続状態システム、連続状態と離散イベントのハイブリッド システムなど、一般的なシステムをモデル化および解析するための モジュール 式の階層型形式です。DEVS は、 時間制限のあるイベント システム です。
歴史 DEVSは、離散事象システム（DES）のモデリングと解析のための形式主義である。DEVS形式主義は、 アリゾナ大学 名誉教授の バーナード・P・ザイグラーによって発明された。DEVSは、ザイグラーが ミシガン大学 の准教授であった 1976年 [1]に、彼の最初の著書『 モデリングとシミュレーションの理論』 で一般に 公開された。DEVSは、出力が現在の状態のみによって決定され（入力に直接依存しない）、有限状態オートマトンである ムーアマシン 形式主義 [2] の拡張と見なすことができる。この拡張は、
各状態に寿命を関連付ける [1] カップリング と呼ばれる操作を伴う階層的概念を提供する 、 [3] 各状態の寿命は 実数 （より正確には非負の実数）または無限大であるため、離散時間システム、シーケンシャルマシン、および ムーアマシン とは区別されます。これらのシステムでは、時間はティックタイムに非負の整数を乗じて決定されます。さらに、寿命は 確率変数 となる可能性があり、例えば、ある状態の寿命は 指数 分布または 一様 分布になる可能性があります。DEVSの状態遷移関数と出力関数も 確率的に なる可能性があります。
1984年にZeiglerはDEVSモデルシミュレーションのための階層的アルゴリズムを提案し [4]、 これは1987年に Simulation 誌に掲載された。それ以来、DEVSから拡張された形式論がそれぞれ独自の目的で数多く導入されてきた。連続イベントと離散イベントを組み合わせたシステムにはDESS/DEVS、並列DESにはP-DEVS、DESの区分連続状態軌跡モデリングにはG-DEVS、リアルタイムDESにはRT-DEVS、セルラーDESにはcell-DEVS、ファジーDESにはfuzzy-DEVS、結合構造を動的に変化させるDESにはdynamic structuring DEVSなどがある。その拡張に加えて、システム特性の決定可能性を実現するためにSP-DEVSやFD-DEVSなどのサブクラスが研究されてきた。
モジュール式で階層的なモデリングビューと、シミュレーションベースの分析機能により、DEVS形式とそのバリエーションは、エンジニアリング（ハードウェア設計、ハードウェア/ソフトウェア共同設計、 通信システム 、 製造システムなど）と科学（ 生物学 、 社会学 など ）
の多くのアプリケーションで使用されています。
図1. ピンポンゲームのDEVSモデル
直感的な例 DEVSは、システム構造だけでなく、システムの振る舞いも定義します。DEVS形式におけるシステム振る舞いは、入力イベントと出力イベント、そして状態を用いて記述されます。例えば、図1の卓球選手の場合、入力イベントは ?receive 、出力イベントは !send です。各選手 A と Bには、 Send と Wait という 状態があります 。Send状態は、出力イベント !send で あるボールを送り返すのに0.1秒かかります。Wait状態 は、選手が入力イベント ?receiveで あるボールを受け取るまで続きます 。
ピンポンゲームの構造は、2 人のプレイヤーを接続することです。プレイヤー A の 出力イベント !send はプレイヤー B の 入力イベント ?receive に送信され、その逆も同様です。
従来の DEVS 形式では、 アトミック DEVS は システムの動作をキャプチャし、 結合 DEVS は システムの構造を記述します。
以下の正式な定義は古典的なDEVSのためのものです。 [5] この記事では、 非負の実数の集合である時間ベースと、 非負の実数に無限大を加えた集合である拡張時間ベースを使用します。 T = [ 0 , ∞ ) {\displaystyle \mathbb {T} =[0,\infty )} T ∞ = [ 0 , ∞ ] {\displaystyle \mathbb {T} ^{\infty }=[0,\infty ]}
アトミック開発者 アトミックDEVSモデルは7つの タプルとして定義される
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 >} どこ
X {\displaystyle X} 入力イベントの集合 です 。 Y {\displaystyle Y} 出力イベントのセット です 。 S {\displaystyle S} 連続した状態の集合 （または 部分的な状態の集合 とも呼ばれる） である。 s 0 ∈ S {\displaystyle s_{0}\in S} 初期状態 です 。 t a : S → T ∞ {\displaystyle ta:S\rightarrow \mathbb {T} ^{\infty }} 状態の寿命を決定するために使用される 時間前進関数 です。 δ e x t : Q × X → S {\displaystyle \delta _{ext}:Q\times X\rightarrow S} は入力イベントがシステムの状態をどのように変化させるかを定義する 外部遷移関数 であり、 は 合計状態の集合 であり、は 最後のイベント からの 経過時間 である 。 [6] Q = { ( s , t e ) | s ∈ S , t e ∈ ( T ∩ [ 0 , t a ( s ) ] ) } {\displaystyle Q=\{(s,t_{e})|s\in S,t_{e}\in (\mathbb {T} \cap [0,ta(s)])\}} t e {\displaystyle t_{e}} δ i n t : S → S {\displaystyle \delta _{int}:S\rightarrow S} システムの状態が内部的にどのように変化するかを定義する 内部遷移関数 です（経過時間が状態の有効期間に達したとき）。 λ : S → Y ϕ {\displaystyle \lambda :S\rightarrow Y^{\phi }} は 出力関数 であり 、 は サイレント イベントまたは 観測されない イベントです。この関数は、システムの状態がどのように出力イベントを生成するか（経過時間が状態の存続時間に達したとき）を定義します。 Y ϕ = Y ∪ { ϕ } {\displaystyle Y^{\phi }=Y\cup \{\phi \}} ϕ ∉ Y {\displaystyle \phi \not \in Y} 卓球選手のための原子DEVSモデル 図1のプレイヤーAの原子DEVSモデルは、プレイヤー=が与えられ 、 < X , Y , S , s 0 , t a , δ e x t , δ i n t , λ > {\displaystyle <X,Y,S,s_{0},ta,\delta _{ext},\delta _{int},\lambda >}
X = { ? receive } Y = { ! send } S = { ( d , σ ) | d ∈ { Wait , Send } , σ ∈ T ∞ } s 0 = ( Send , 0.1 ) t a ( s ) = σ for all s ∈ S δ e x t ( ( ( Wait , σ ) , t e ) , ? receive ) = ( Send , 0.1 ) δ i n t ( Send , σ ) = ( Wait , ∞ ) δ i n t ( Wait , σ ) = ( Send , 0.1 ) λ ( Send , σ ) = ! send λ ( Wait , σ ) = ϕ {\displaystyle {\begin{aligned}X&=\{?{\textit {receive}}\}\\Y&=\{!{\textit {send}}\}\\S&=\{(d,\sigma )|d\in \{{\textit {Wait}},{\textit {Send}}\},\sigma \in \mathbb {T} ^{\infty }\}\\s_{0}&=({\textit {Send}},0.1)\\ta(s)&=\sigma {\text{ for all }}s\in S\\\delta _{ext}((({\textit {Wait}},\sigma ),t_{e}),?{\textit {receive}})&=({\textit {Send}},0.1)\\\delta _{int}({\textit {Send}},\sigma )&=({\textit {Wait}},\infty )\\\delta _{int}({\textit {Wait}},\sigma )&=({\textit {Send}},0.1)\\\lambda ({\textit {Send}},\sigma )&=!{\textit {send}}\\\lambda ({\textit {Wait}},\sigma )&=\phi \end{aligned}}}
プレイヤー A とプレイヤー B は両方ともアトミック DEVS モデルです。
簡単に言えば、原子DEVSモデルの 状態が変化するケースは2つあります 。(1) 外部入力が システムに入ったとき 、(2) 経過時間が で定義される の寿命に達したときです 。(2)と同時に、 は で定義される 出力を生成します 。 M {\displaystyle M} s ∈ S {\displaystyle s\in S} x ∈ X {\displaystyle x\in X} M {\displaystyle M} t e {\displaystyle t_{e}} s {\displaystyle s} t a ( s ) {\displaystyle ta(s)} M {\displaystyle M} y ∈ Y {\displaystyle y\in Y} λ ( s ) {\displaystyle \lambda (s)}
与えられた原子DEVSモデルの正式な動作記述については、「原子DEVSの動作」セクションを参照してください。与えられた原子DEVSモデルの動作を実装するためのコンピュータアルゴリズムは、「原子DEVSのシミュレーションアルゴリズム」セクションで提供されています。
結合されたDEVS 結合DEVSは、どのサブコンポーネントがそれに属し、それらが互いにどのように接続されているかを定義します。結合DEVSモデルは、8つの タプルとして定義されます。
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>} どこ
X {\displaystyle X} 入力イベントの集合 です 。 Y {\displaystyle Y} 出力イベントのセット です 。 D {\displaystyle D} サブコンポーネントの名前セット です 。 { M i } {\displaystyle \{M_{i}\}} サブコンポーネントのセットで あり、 各サブコンポーネント は、アトミック DEVS モデルまたは結合 DEVS モデルのいずれかになります。 i ∈ D , M i {\displaystyle i\in D,M_{i}} C x x ⊆ X × ⋃ i ∈ D X i {\displaystyle C_{xx}\subseteq X\times \bigcup _{i\in D}X_{i}} 外部入力カップリングのセット です 。 C y x ⊆ ⋃ i ∈ D Y i × ⋃ i ∈ D X i {\displaystyle C_{yx}\subseteq \bigcup _{i\in D}Y_{i}\times \bigcup _{i\in D}X_{i}} 内部カップリングの集合 です 。 C y y : ⋃ i ∈ D Y i → Y ϕ {\displaystyle C_{yy}:\bigcup _{i\in D}Y_{i}\rightarrow Y^{\phi }} 外部出力結合関数 です 。 S e l e c t : 2 D → D {\displaystyle Select:2^{D}\rightarrow D} 同時発生するイベントのセットからイベントを選択する方法を定義する タイブレーク関数 です。 ピンポンゲームのための結合DEVSモデル 図 1 のピンポン ゲームは、結合された DEVS モデルとしてモデル化できます。 ここで 、; ; ; は上記のように記述されます。; ; ; そして 。 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>} X = { } {\displaystyle X=\{\}} Y = { } {\displaystyle Y=\{\}} D = { A , B } {\displaystyle D=\{A,B\}} M A and M B {\displaystyle M_{A}{\text{ and }}M_{B}} C x x = { } {\displaystyle C_{xx}=\{\}} C y x = { ( A . ! s e n d , B . ? r e c e i v e ) , ( B . ! s e n d , A . ? r e c e i v e ) } {\displaystyle C_{yx}=\{(A.!send,B.?receive),(B.!send,A.?receive)\}} C y y ( A . ! s e n d ) = ϕ , C y y ( B . ! s e n d ) = ϕ {\displaystyle C_{yy}(A.!send)=\phi ,C_{yy}(B.!send)=\phi }
簡単に言えば、原子DEVSクラスの振る舞いと同様に、結合DEVSモデルは、外部イベント が に入力された とき、(1) コンポーネントの状態を変化させます。 (2) コンポーネントの1つが内部状態遷移を実行し、出力 を生成したとき 。 ( 1) と (2) のどちらの場合も、トリガーイベントは結合集合と によって定義されるすべての影響に伝達され ます 。 N {\displaystyle N} x ∈ X {\displaystyle x\in X} N {\displaystyle N} M i {\displaystyle M_{i}} i ∈ D {\displaystyle i\in D} y i ∈ Y i {\displaystyle y_{i}\in Y_{i}} C x x , C y x , {\displaystyle C_{xx},C_{yx},} C y y {\displaystyle C_{yy}}
結合DEVSの動作の正式な定義については、「結合DEVSの動作」セクションを参照してください。特定の結合DEVSモードの動作を実装するためのコンピュータアルゴリズムについては、「結合DEVSのシミュレーションアルゴリズム」セクションを参照してください。
分析方法
離散事象システムのシミュレーション DEVSモデルのシミュレーションアルゴリズムは、時間同期とメッセージ伝播という2つの問題を考慮しています。DEVSの 時間同期 は、すべてのモデルの現在時刻を同一に制御することです。しかし、効率的な実行のために、アルゴリズムは、イベントがスケジュールされた最も緊急性の高い時刻に現在時刻をジャンプさせ、その内部状態遷移と出力生成を実行します。 メッセージ伝播は 、結合DEVSモデルで定義された関連する結合に沿って、入力イベントまたは出力イベントのいずれかであるトリガーメッセージを送信することです。詳細については、 「アトミックDEVSのシミュレーションアルゴリズム」 および 「結合DEVSのシミュレーションアルゴリズム」 を参照してください。
連続状態システムのシミュレーション 連続セグメントを区分的定数セグメントとして抽象化する量子化手法を導入することにより、DEVS は 微分代数方程式 のネットワークで記述される連続状態システムの挙動をシミュレートできます。この研究は 1990 年代に Zeigler 氏によって開始されました。 [7]多くの特性は 2000 年代に Kofman 教授と Nutaro 博士によって明らかにされました。2006 年には、 Continuous System Modeling [ 8] の著者である Cellier 教授 と Kofman 教授が教科書 Continuous System Simulation [9] を執筆し、 その第 11 章と第 12 章で DEVS が連続状態システムをシミュレートする方法を取り上げています。Nutaro 博士の本 [10] では、連続状態システムの離散イベント シミュレーションも取り上げられています。 [11]
離散事象システムの検証 サンプリングベースのシミュレーション法に代わる解析手法として、一般に 検証 と呼ばれる網羅的な生成動作アプローチがDEVS モデルの解析に適用されてきた。与えられた DEVS モデルがスケジュール保持型 DEVS (SP-DEVS)、有限かつ決定論的 DEVS (FD-DEVS) [12]、有限かつリアルタイム DEVS (FRT-DEVS) [13] などの DEVS のサブクラスである場合、与えられた DEVS モデル (特に結合 DEVS モデル) の 無限 状態は、動作的に 同型の有限構造 (到達可能性グラフ) によって抽象化できることが証明されている。 結果として、到達可能性グラフに基づいて、(1) デッドロックおよびライブロックフリーを定性的な特性として SP-DEVS [14] 、 FD-DEVS [15] 、 FRT-DEVS [13] で 決定可能であり、(2) 最小/最大処理時間境界を定量的な特性として SP-DEVS で決定可能であることが 2012 年までにわかっている。
時間制限付きイベントシステム 一般システムは、Zeigler [16] [17] によって、(1) 時間ベース、(2) 許容される入力セグメント、(3) システム状態、(4) 許容される入力セグメントを含む状態軌跡、(5) 与えられた状態に対する出力を定義する観点から記述されている。現在のセグメントとイベントセグメントに関連付けられた状態軌跡を定義するタイムドイベントシステムは、 非 決定論的な動作を可能にするために一般システムのクラスから生まれた。 [18] DEVS の動作は タイムドイベントシステムで記述できるため 、DEVS と RTDEVS はタイムドイベントシステムのサブクラスまたは同等のクラスである。
時間制限付きイベントシステムは構造である
G =< Z , Q , Q 0 , Q A , Δ > {\displaystyle {\mathcal {G}}=<Z,Q,Q_{0},Q_{A},\Delta >} どこ
Z {\displaystyle \,Z} はイベントの集合 です 。 Q {\displaystyle \,Q} は状態の集合で ある 。 Q 0 ⊆ Q {\displaystyle \,Q_{0}\subseteq Q} 初期状態の集合 です 。 Q A ⊆ Q {\displaystyle Q_{A}\subseteq Q} は受け入れ状態の集合で ある 。 Δ ⊆ Q × Ω Z , [ t l , t u ] × Q {\displaystyle \Delta \subseteq Q\times \Omega _{Z,[t_{l},t_{u}]}\times Q} は、イベントセグメント とともに 状態 が に変化する可能性があることを示す、 における 状態軌跡の集合 です 。2つの状態軌跡 と が連続している場合 、 かつ 2つのイベント軌跡 と が 連続しているといいます。2つの状態軌跡 と が連続している場合、 が成立します 。 ( q , ω , q ′ ) ∈ Δ {\displaystyle (q,\omega ,q')\in \Delta } q ∈ Q {\displaystyle q\in Q} q ′ ∈ Q {\displaystyle q'\in Q} ω ∈ Ω Z , [ t l , t u ] {\displaystyle \omega \in \Omega _{Z,[t_{l},t_{u}]}} ( q 1 , ω 1 , q 2 ) {\displaystyle (q_{1},\omega _{1},q_{2})} ( q 3 , ω 2 , q 4 ) ∈ Δ {\displaystyle (q_{3},\omega _{2},q_{4})\in \Delta } q 2 = q 3 {\displaystyle q_{2}=q_{3}} ω 1 {\displaystyle \omega _{1}} ω 2 {\displaystyle \omega _{2}} ( q , ω 1 , p ) {\displaystyle (q,\omega _{1},p)} ( p , ω 2 , q ′ ) ∈ Δ {\displaystyle (p,\omega _{2},q')\in \Delta } ( q , ω 1 ω 2 , q ′ ) ∈ Δ {\displaystyle (q,\omega _{1}\omega _{2},q')\in \Delta } 時間制限付きイベントシステム が与えられたとき 、 その動作の集合は 観測時間の長さに依存した 言語 と呼ばれる。 を観測時間の長さとする。 の場合 、 の長さの観測言語 は と表され 、次のように定義される。 G =< Z , Q , Q 0 , Q A , Δ > {\displaystyle {\mathcal {G}}=<Z,Q,Q_{0},Q_{A},\Delta >} t {\displaystyle t} 0 ≤ t < ∞ {\displaystyle 0\leq t<\infty } t {\displaystyle t} G {\displaystyle {\mathcal {G}}} L ( G , t ) {\displaystyle L({\mathcal {G}},t)}
L ( G , t ) = { ω ∈ Ω Z , [ 0 , t ] : ∃ ( q 0 , ω , q ) ∈ Δ , q 0 ∈ Q 0 , q ∈ Q A } . {\displaystyle L({\mathcal {G}},t)=\{\omega \in \Omega _{Z,[0,t]}:\exists (q_{0},\omega ,q)\in \Delta ,q_{0}\in Q_{0},q\in Q_{A}\}.} のイベントセグメントを の長 さの振る舞い と呼ぶ 。観測時間の長さを無限大に送ることで、 の無限長の観測言語 を定義する。 これは で表され 、次のように定義される 。 ω ∈ Ω Z , [ 0 , t ] {\displaystyle \omega \in \Omega _{Z,[0,t]}} t {\displaystyle t} G {\displaystyle {\mathcal {G}}} ω ∈ L ( G , t ) {\displaystyle \omega \in L({\mathcal {G}},t)} t {\displaystyle t} G {\displaystyle {\mathcal {G}}} L ( G , ∞ ) {\displaystyle L({\mathcal {G}},\infty )}
L ( G , ∞ ) = { ω ∈ lim t → ∞ Ω Z , [ 0 , t ] : ∃ { q : ( q 0 , ω , q ) ∈ Δ , q 0 ∈ Q 0 } ⊆ Q A } . {\displaystyle L({\mathcal {G}},\infty )=\{\omega \in {\underset {t\rightarrow \infty }{\lim }}\Omega _{Z,[0,t]}:\exists \{q:(q_{0},\omega ,q)\in \Delta ,q_{0}\in Q_{0}\}\subseteq Q_{A}\}.} の場合には、 イベント セグメントを の無限長の動作と呼びます 。 ω ∈ lim t → ∞ Ω Z , [ 0 , t ] {\displaystyle \omega \in {\underset {t\rightarrow \infty }{\lim }}\Omega _{Z,[0,t]}} G {\displaystyle {\mathcal {G}}} ω ∈ L ( G , ∞ ) {\displaystyle \omega \in L({\mathcal {G}},\infty )} ω ∈ L ( G , ∞ ) {\displaystyle \omega \in L({\mathcal {G}},\infty )}
DEVSのバリエーション
拡張（スーパークラス化） 過去数十年間に、古典的なDEVS形式論の数多くの拡張が開発されてきました。その中には、シミュレーション時間の経過に伴ってモデル構造が変化することを可能にする形式論があります。
G-DEVS、 [19] [20] 並列DEVS、動的構造化DEVS、セルDEVS、 [21] dynDEVS、ファジーDEVS、GK-DEVS、ml-DEVS、シンボリックDEVS、リアルタイムDEVS、rho-DEVS
制限事項（サブクラス化） 検証分析をサポートするために指定された、スケジュール保持 DEVS ( SP-DEVS ) および有限かつ決定論的 DEVS ( FD-DEVS )と呼ばれるサブクラスがいくつかあります。 SP-DEVS と FD-DEVS の表現力は E ( SP-DEVS ) E ( FD-DEVS ) E (DEVS) で、 E ( 形式主義) は 形式主義 の表現力を示します 。 ⊂ {\displaystyle \subset } ⊂ {\displaystyle \subset }
行動
アトミック開発者 与えられたDEVSモデルの振る舞いは、 イベントセグメント と呼ばれるヌルイベントを含む、時間指定イベントのシーケンスの集合です。これらのイベントは、モデルを一連の合法状態内においてある状態から別の状態へと遷移させます。このように定義するには、一連の合法状態だけでなく、一連の違法状態の概念も導入する必要があります。
さらに、与えられたDEVSモデルの振る舞いは、時間の経過とイベントの発生の両方において状態遷移がどのように変化するかを定義する必要があるため、一般システムと呼ばれるより一般的な形式論によって記述されてきた。 [22]この記事では、代わりに タイムドイベントシステム と呼ばれる一般システム形式のサブクラスを使用する 。
DEVSモデルの全体状態と外部状態遷移関数の定義方法に応じて、 タイムドイベントシステムを用いてDEVSモデルの動作を定義する方法は2つあります。 結合DEVSモデルの動作は アトミックDEVSモデルとして定義されるため 、結合DEVSクラスの動作もタイムドイベントシステムによって定義されます。
ビュー1: 合計状態 = 状態 * 経過時間 DEVSモデル が
、 M =< X , Y , S , s 0 , t a , δ e x t , δ i n t , λ > {\displaystyle {\mathcal {M}}=<X,Y,S,s_{0},ta,\delta _{ext},\delta _{int},\lambda >}
外部状態遷移 。 δ e x t : Q × X → S {\displaystyle \delta _{ext}:Q\times X\rightarrow S} 合計状態集合 は、 最後のイベントからの経過時間を表し、 非負の実数の集合を表し、 Q = { ( s , t e ) | s ∈ S , t e ∈ ( T ∩ [ 0 , t a ( s ) ] ) } {\displaystyle Q=\{(s,t_{e})|s\in S,t_{e}\in (\mathbb {T} \cap [0,ta(s)])\}} t e {\displaystyle t_{e}} T = [ 0 , ∞ ) {\displaystyle \mathbb {T} =[0,\infty )} DEVSモデルは、 時間制限のあるイベントシステム であり 、 M {\displaystyle {\mathcal {M}}} G =< Z , Q , Q 0 , Q A , Δ > {\displaystyle {\mathcal {G}}=<Z,Q,Q_{0},Q_{A},\Delta >}
イベントセット 。 Z = X ∪ Y ϕ {\displaystyle Z=X\cup Y^{\phi }} 状態 は に設定されます 。 Q = Q A ∪ Q N {\displaystyle Q=Q_{A}\cup Q_{N}} Q N = { s ¯ ∉ S } {\displaystyle Q_{N}=\{{\bar {s}}\not \in S\}} 初期状態の集合 。 Q 0 = { ( s 0 , 0 ) } {\displaystyle \,Q_{0}=\{(s_{0},0)\}} 受け入れ状態の集合 Q A = M . Q . {\displaystyle Q_{A}={\mathcal {M}}.Q.} 状態軌道の集合は、2つの異なるケース、 すなわち と について定義される 。非受理状態 の場合 、偶数セグメントとともに変化は起こらない ので、 Δ ⊆ Q × Ω Z , [ t l , t u ] × Q {\displaystyle \Delta \subseteq Q\times \Omega _{Z,[t_{l},t_{u}]}\times Q} q ∈ Q N {\displaystyle q\in Q_{N}} q ∈ Q A {\displaystyle q\in Q_{A}} q ∈ Q N {\displaystyle q\in Q_{N}} ω ∈ Ω Z , [ t l , t u ] {\displaystyle \omega \in \Omega _{Z,[t_{l},t_{u}]}} ( q , ω , q ) ∈ Δ . {\displaystyle (q,\omega ,q)\in \Delta .} 時刻 と イベント セグメントの 合計状態は 次のとおりです。 q = ( s , t e ) ∈ Q A {\displaystyle q=(s,t_{e})\in Q_{A}} t ∈ T {\displaystyle t\in \mathbb {T} } ω ∈ Ω Z , [ t l , t u ] {\displaystyle \omega \in \Omega _{Z,[t_{l},t_{u}]}}
単位イベントセグメントが ヌルイベントセグメント である 場合 、すなわち ω {\displaystyle \omega } ω = ϵ [ t , t + d t ] {\displaystyle \omega =\epsilon _{[t,t+dt]}}
( q , ω , ( s , t e + d t ) ) ∈ Δ . {\displaystyle \,(q,\omega ,(s,t_{e}+dt))\in \Delta .} ユニットイベントセグメントが 入力イベントである 時間指定イベント で ある場合 、 ω {\displaystyle \omega } ω = ( x , t ) {\displaystyle \omega =(x,t)} x ∈ X {\displaystyle x\in X}
( q , ω , ( δ e x t ( q , x ) , 0 ) ) ∈ Δ . {\displaystyle (q,\omega ,(\delta _{ext}(q,x),0))\in \Delta .} 単位イベントセグメントが 時間指定イベント であり、 イベントが出力イベントまたは観測不可能なイベントで ある場合 、 ω {\displaystyle \omega } ω = ( y , t ) {\displaystyle \omega =(y,t)} y ∈ Y ϕ {\displaystyle y\in Y^{\phi }}
{ ( q , ω , ( δ i n t ( s ) , 0 ) ) ∈ Δ if t e = t a ( s ) , y = λ ( s ) ( q , ω , s ¯ ) otherwise . {\displaystyle {\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}}} この動作のビューをシミュレートするコンピュータ アルゴリズムは、 atomic DEVS セクションのシミュレーション アルゴリズムで入手できます。
視点2: 総状態数 = 状態数 * 寿命 * 経過時間 DEVSモデル が
、 M =< X , Y , S , s 0 , t a , δ e x t , δ i n t , λ > {\displaystyle {\mathcal {M}}=<X,Y,S,s_{0},ta,\delta _{ext},\delta _{int},\lambda >}
全体の状態集合。 ここで は 状態の寿命 、 は最終 更新からの経過時間、 は 非負の実数と無限大の集合を表す。 Q = { ( s , t s , t e ) | s ∈ S , t s ∈ T ∞ , t e ∈ ( T ∩ [ 0 , t s ] ) } {\displaystyle Q=\{(s,t_{s},t_{e})|s\in S,t_{s}\in \mathbb {T} ^{\infty },t_{e}\in (\mathbb {T} \cap [0,t_{s}])\}} t s {\displaystyle t_{s}} s {\displaystyle s} t e {\displaystyle t_{e}} t s {\displaystyle t_{s}} T ∞ = [ 0 , ∞ ) ∪ { ∞ } {\displaystyle \mathbb {T} ^{\infty }=[0,\infty )\cup \{\infty \}} 外部状態遷移は です 。 δ e x t : Q × X → S × { 0 , 1 } {\displaystyle \delta _{ext}:Q\times X\rightarrow S\times \{0,1\}} DEVS は時間制限のあるイベントシステムで 、 Q = D {\displaystyle Q={\mathcal {D}}} G =< Z , Q , Q 0 , Q A , Δ > {\displaystyle {\mathcal {G}}=<Z,Q,Q_{0},Q_{A},\Delta >}
イベントセット 。 Z = X ∪ Y ϕ {\displaystyle Z=X\cup Y^{\phi }} 状態 は に設定されます 。 Q = Q A ∪ Q N {\displaystyle Q=Q_{A}\cup Q_{N}} Q N = { s ¯ ∉ S } {\displaystyle Q_{N}=\{{\bar {s}}\not \in S\}} 初期状態の集合 。 Q 0 = { ( s 0 , t a ( s 0 ) , 0 ) } {\displaystyle \,Q_{0}=\{(s_{0},ta(s_{0}),0)\}} 受け入れ状態のセット 。 Q A = M . Q {\displaystyle Q_{A}={\mathcal {M}}.Q} 状態軌道の集合は、 とという 2つのケースに依存します 。非受理状態の場合 、どのセグメントにも変化はない ので、 Δ ⊆ Q × Ω Z , [ t l , t u ] × Q {\displaystyle \Delta \subseteq Q\times \Omega _{Z,[t_{l},t_{u}]}\times Q} q ∈ Q N {\displaystyle q\in Q_{N}} q ∈ Q A {\displaystyle q\in Q_{A}} q ∈ Q N {\displaystyle q\in Q_{N}} ω ∈ Ω Z , [ t l , t u ] {\displaystyle \omega \in \Omega _{Z,[t_{l},t_{u}]}} ( q , ω , q ) ∈ Δ . {\displaystyle (q,\omega ,q)\in \Delta .} 時刻 と イベント セグメントの 合計状態は 次のとおりです。 q = ( s , t s , t e ) ∈ Q A {\displaystyle q=(s,t_{s},t_{e})\in Q_{A}} t ∈ T {\displaystyle t\in \mathbb {T} } ω ∈ Ω Z , [ t l , t u ] {\displaystyle \omega \in \Omega _{Z,[t_{l},t_{u}]}}
単位イベントセグメントが ヌルイベントセグメント である 場合 、すなわち ω {\displaystyle \omega } ω = ϵ [ t , t + d t ] {\displaystyle \omega =\epsilon _{[t,t+dt]}}
( q , ω , ( s , t s , t e + d t ) ) ∈ Δ . {\displaystyle (q,\omega ,(s,t_{s},t_{e}+dt))\in \Delta .} ユニットイベントセグメントが 入力イベントである 時間指定イベント で ある場合 、 ω {\displaystyle \omega } ω = ( x , t ) {\displaystyle \omega =(x,t)} x ∈ X {\displaystyle x\in X}
{ ( q , ω , ( s ′ , t a ( s ′ ) , 0 ) ) ∈ Δ if δ e x t ( s , t s , t e , x ) = ( s ′ , 1 ) , ( q , ω , ( s ′ , t s , t e ) ) ∈ Δ otherwise,i.e. δ e x t ( s , t s , t e , x ) = ( s ′ , 0 ) . {\displaystyle {\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}}} 単位イベントセグメントが 時間指定イベント であり、 イベントが出力イベントまたは観測不可能なイベントで ある場合 、 ω {\displaystyle \omega } ω = ( y , t ) {\displaystyle \omega =(y,t)} y ∈ Y ϕ {\displaystyle y\in Y^{\phi }}
{ ( q , ω , ( s ′ , t a ( s ′ ) , 0 ) ) ∈ Δ if t e = t s , y = λ ( s ) , δ i n t ( s ) = s ′ , ( q , ω , s ¯ ) ∈ Δ otherwise . {\displaystyle {\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}}} この動作のビューをシミュレートするコンピュータ アルゴリズムは、 atomic DEVS セクションのシミュレーション アルゴリズムで入手できます。
ビュー1とビュー2の比較
view1の特徴 ビュー1はZeigler [23] によって導入され、全状態 と q = ( s , t e ) ∈ Q {\displaystyle q=(s,t_{e})\in Q}
t a ( s ) = σ {\displaystyle \,ta(s)=\sigma } ここで 残り時間は [23] [22] である。言い換えれば、部分状態の集合は実際には状態集合 である 。DEVSモデルが入力イベントを受信すると 、view1は経過時間をゼロにリセットする。DEVSモデルが 寿命制御の観点から 無視する必要がある場合、モデル作成者は残り時間を更新する必要がある。 σ {\displaystyle \sigma } S = { ( d , σ ) | d ∈ S ′ , σ ∈ T ∞ } {\displaystyle S=\{(d,\sigma )|d\in S',\sigma \in \mathbb {T} ^{\infty }\}} S ′ {\displaystyle S'} x ∈ X {\displaystyle x\in X} t e {\displaystyle t_{e}} x {\displaystyle x}
σ = σ − t e {\displaystyle \,\sigma =\sigma -t_{e}} 外部状態遷移関数は モデル作成者の責任です。 δ e x t {\displaystyle \delta _{ext}}
の取り得る値の数は 、DEVSモデルに入力される可能性のあるイベントの数と同じなので、無限です。したがって、状態の数 も無限であり、これがview2が提案された理由です。 σ {\displaystyle \sigma } s = ( d , σ ) ∈ S {\displaystyle s=(d,\sigma )\in S}
DEVSモデルの有限頂点到達可能性グラフを気にしないのであれば、view1は、 DEVSモデルに入力イベントが到着するたびに経過時間を扱うという単純さという利点があります。しかし、DEVSのモデラーは 上記のように処理する方法を知っておく必要があるという欠点があります。これは、それ自体では明示的に説明されていませんが、 で説明されています 。 t e = 0 {\displaystyle t_{e}=0} σ {\displaystyle \sigma } δ e x t {\displaystyle \delta _{ext}} Δ {\displaystyle \Delta }
view2の特徴 View2はHwangとZeigler [24] [25] によって導入され、 合計状態が与えられた場合 、残り時間は 次のように計算される。 q = ( s , t s , t e ) ∈ Q {\displaystyle q=(s,t_{s},t_{e})\in Q} σ {\displaystyle \sigma }
σ = t s − t e . {\displaystyle \,\sigma =t_{s}-t_{e}.} DEVSモデルが入力イベント を受信すると 、view2は の場合にのみ経過時間を ゼロにリセットします 。DEVSモデルが 寿命制御の観点から を無視する必要がある場合、モデラーは を使用できます 。 x ∈ X {\displaystyle x\in X} t e {\displaystyle t_{e}} δ e x t ( q , x ) = ( s ′ , 1 ) {\displaystyle \delta _{ext}(q,x)=(s',1)} x {\displaystyle x} δ e x t ( q , x ) = ( s ′ , 0 ) {\displaystyle \delta _{ext}(q,x)=(s',0)}
ビュー1とは異なり、残り時間は本質的に の要素ではないため 、状態の数、つまり が 有限であれば、有限頂点（およびエッジ）の状態遷移図を描くことができます。 [24] [25] その結果、 SP-DEVS や FD-DEVS などのDEVSクラスのネットワークの振る舞いを、到達可能性グラフと呼ばれる有限頂点グラフとして抽象化することができます。 [24] [25] σ {\displaystyle \sigma } S {\displaystyle S} | S | {\displaystyle |S|}
結合されたDEVS DEVSは結合に関して閉じている。 [3] [26] 言い換えれば、結合DEVSモデルが与えられた場合 、その動作は原子DEVSモデルとして記述される 。与えられた結合DEVSに対して 、同等の原子DEVSが与えられれば 、その動作は 時間イベントシステム に基づく 原子DEVSの挙動 を参照することができる 。 N {\displaystyle N} M {\displaystyle M} N {\displaystyle N} M {\displaystyle M} M {\displaystyle M}
アトミック DEVS の動作 と同様に 、結合 DEVS クラスの動作は、全体の状態セットの定義とその処理に応じて次のように説明されます。
ビュー1: 合計状態 = 状態 * 経過時間 結合DEVSモデルが与えられた場合 、その動作は原子DEVSモデルとして記述される。 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>} 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 >}
どこ
X {\displaystyle X} および は、それぞれ入力イベント セットと出力イベント セットです。 Y {\displaystyle Y} S = × i ∈ D Q i {\displaystyle S={\underset {i\in D}{\times }}Q_{i}} は部分状態セットであり、 はコンポーネントの全体状態セットです( DEVS の動作のビュー 1 を参照 )。 は非負の実数のセットです。 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})])\}} i ∈ D {\displaystyle i\in D} T = [ 0 , ∞ ) {\displaystyle \mathbb {T} =[0,\infty )} s 0 = × i ∈ D q 0 i {\displaystyle s_{0}={\underset {i\in D}{\times }}q_{0i}} は初期状態セットであり、 はコンポーネントの合計初期状態です 。 q 0 i = ( s 0 i , 0 ) {\displaystyle q_{0i}=(s_{0i},0)} i ∈ D {\displaystyle i\in D} t a : S → T ∞ {\displaystyle ta:S\rightarrow \mathbb {T} ^{\infty }} は時間進行関数であり、 非負 の実数と無限大の集合である。 T ∞ = [ 0 , ∞ ] {\displaystyle \mathbb {T} ^{\infty }=[0,\infty ]} 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} は外部状態関数である。全体の状態が与えられ 、入力イベントが与えられた 場合 、次の状態は次のように与えられる。 q = ( s , t e ) {\displaystyle q=(s,t_{e})} 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)])} x ∈ X {\displaystyle x\in X} δ e x t ( q , x ) = s ′ = ( … , ( s i ′ , t e i ′ ) , … ) {\displaystyle \delta _{ext}(q,x)=s'=(\ldots ,(s_{i}',t_{ei}'),\ldots )} どこ
( 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}}} 部分状態 が与えられたとき 、 は 切迫したコンポーネントの集合 を表すものとする 。 内部状態遷移と出力イベントをトリガーする 発火コンポーネントは、次のように決定される。 s = ( … , ( s i , t e i ) , … ) ∈ S {\displaystyle s=(\ldots ,(s_{i},t_{ei}),\ldots )\in S} 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)\}} i ∗ ∈ D {\displaystyle i^{*}\in D}
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} は内部状態関数である。部分状態 が与えられた場合 、次の状態は次のように与えられる。 s = ( … , ( s i , t e i ) , … ) {\displaystyle s=(\ldots ,(s_{i},t_{ei}),\ldots )} δ i n t ( s ) = s ′ = ( … , ( s i ′ , t e i ′ ) , … ) {\displaystyle \delta _{int}(s)=s'=(\ldots ,(s_{i}',t_{ei}'),\ldots )} どこ
( 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 }} は出力関数である。部分状態が与えられると 、 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}}}
ビュー2: 合計状態 = 状態 * 寿命 * 経過時間 結合DEVSモデルが与えられた場合 、その動作は原子DEVSモデルとして記述される。 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>} 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 >}
どこ
X {\displaystyle X} および は、それぞれ入力イベント セットと出力イベント セットです。 Y {\displaystyle Y} S = × i ∈ D Q i {\displaystyle S={\underset {i\in D}{\times }}Q_{i}} は部分的な状態セットで、 はコンポーネントの全体の状態セットです( DEVS セクションの動作のビュー 2 を参照 )。 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}])\}} i ∈ D {\displaystyle i\in D} s 0 = × i ∈ D q 0 i {\displaystyle s_{0}={\underset {i\in D}{\times }}q_{0i}} は初期状態セットであり、 はコンポーネントの合計初期状態です 。 q 0 i = ( s 0 i , t a i ( s 0 i ) , 0 ) {\displaystyle q_{0i}=(s_{0i},ta_{i}(s_{0i}),0)} i ∈ D {\displaystyle i\in D} t a : S → T ∞ {\displaystyle ta:S\rightarrow \mathbb {T} ^{\infty }} は時間進行関数である 。 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\}} は外部状態関数である。全体の状態が与えられ 、入力イベントが与えられた 場合 、次の状態は次のように与えられる。 q = ( s , t s , t e ) {\displaystyle q=(s,t_{s},t_{e})} 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}])} x ∈ X {\displaystyle x\in X} δ 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)} どこ
( 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 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_{si},t_{ei})&{\text{otherwise}}\end{cases}}} そして
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}}} 部分状態 が与えられたとき 、 は 切迫したコンポーネントの集合 を表すものとする 。 内部状態遷移と出力イベントをトリガーする 発火コンポーネントは、次のように決定される。 s = ( … , ( s i , t s i , t e i ) , … ) ∈ S {\displaystyle s=(\ldots ,(s_{i},t_{si},t_{ei}),\ldots )\in S} 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)\}} i ∗ ∈ D {\displaystyle i^{*}\in D}
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} は内部状態関数である。部分状態 が与えられた場合 、次の状態は次のように与えられる。 s = ( … , ( s i , t s i , t e i ) , … ) {\displaystyle s=(\ldots ,(s_{i},t_{si},t_{ei}),\ldots )} δ 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 )} どこ
( 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 }} は出力関数である。部分状態が与えられると 、 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}}}
時間の経過 空でないサブコンポーネントを持つ結合 DEVS モデル、つまり 、経過時間をトレースするクロックの数は倍数であるため、モデルの時間経過が顕著になります。 | D | > 0 {\displaystyle |D|>0}
ビュー1 全体の状態が与えられ 、 q = ( s , t e ) ∈ Q {\displaystyle q=(s,t_{e})\in Q} s = ( … , ( s i , t e i ) , … ) {\displaystyle s=(\ldots ,(s_{i},t_{ei}),\ldots )}
単位イベントセグメントが ヌルイベントセグメント である 場合 、すなわち、 時間制限イベントシステム における状態軌跡 は、 ω {\displaystyle \omega } ω = ϵ [ t , t + d t ] {\displaystyle \omega =\epsilon _{[t,t+dt]}}
Δ ( 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).}
ビュー2の場合 全体の状態が与えられ 、 q = ( s , t s , t e ) ∈ Q {\displaystyle q=(s,t_{s},t_{e})\in Q} s = ( … , ( s i , t s i , t e i ) , … ) {\displaystyle s=(\ldots ,(s_{i},t_{si},t_{ei}),\ldots )}
単位イベントセグメントが ヌルイベントセグメント である 場合 、すなわち、 時間制限イベントシステム における状態軌跡 は、 ω {\displaystyle \omega } ω = ϵ [ t , t + d t ] {\displaystyle \omega =\epsilon _{[t,t+dt]}}
Δ ( 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).}
シミュレーションアルゴリズム
アトミック開発者 原子DEVSモデルが与えられた場合、シミュレーションアルゴリズムは、モデルの正当な動作、すなわち不正な状態に到達しない軌跡を生成する手法である。（ DEVSの動作を参照）。Zeiglerは、 寿命 と 経過時間 に関連する時間変数を扱うアルゴリズムを、 前回のイベント時間 、、 次回のイベント時間 という2つの時間変数を導入し 、 以下の関係式で表すことにより初めて導入した。 [3] t s ∈ [ 0 , ∞ ] {\displaystyle t_{s}\in [0,\infty ]} t e ∈ [ 0 , ∞ ) {\displaystyle t_{e}\in [0,\infty )} t l ∈ [ 0 , ∞ ) {\displaystyle t_{l}\in [0,\infty )} t n ∈ [ 0 , ∞ ] {\displaystyle t_{n}\in [0,\infty ]}
t e = t − t l {\displaystyle \,t_{e}=t-t_{l}} そして
t s = t n − t l {\displaystyle \,t_{s}=t_{n}-t_{l}} ここで、 は 現在時刻 を表します 。そして 残り時間 は 、 t ∈ [ 0 , ∞ ) {\displaystyle t\in [0,\infty )}
t r = t s − t e {\displaystyle \,t_{r}=t_{s}-t_{e}} は次のように計算される。
t r = t n − t {\displaystyle \,t_{r}=t_{n}-t} 、 どうやら 。 t r ∈ [ 0 , ∞ ] {\displaystyle t_{r}\in [0,\infty ]}
特定の原子 DEVS モデルの動作は、全体の状態と外部遷移関数に応じて 2 つの異なるビューで定義できるため ( DEVS の動作 セクションを参照)、シミュレーション アルゴリズムも以下のように 2 つの異なるビューで導入されます。
共通部品 全体の状態の 2 つの異なるビューに関係なく、初期化および内部遷移ケースのアルゴリズムは一般的に以下のように定義されます。
DEVSシミュレータ 変数: 親 // 親コーディネーター t l {\displaystyle t_{l}} // 最後のイベントの時刻 // 次のイベントの時刻 // 関連する Atomic DEVS モデル t n {\displaystyle t_{n}} A = ( X , Y , S , t a , δ e x t , δ i n t , λ ) {\displaystyle A=(X,Y,S,ta,\delta _{ext},\delta _{int},\lambda )} init-message を受信したとき(Time ) star-message を受信したとき(Time ) t {\displaystyle t} t l ← t ; {\displaystyle t_{l}\leftarrow t;} t n ← t l + t a ( s ) ; {\displaystyle t_{n}\leftarrow t_{l}+ta(s);} t {\displaystyle t} もし そうなら t ≠ t n {\displaystyle t\neq t_{n}} エラー: 同期が不正です。 y ← λ ( s ) ; {\displaystyle y\leftarrow \lambda (s);} y-message( ) を親に送信します。 y , t {\displaystyle y,t} s ← δ i n t ( s ) {\displaystyle s\leftarrow \delta _{int}(s)} t l ← t ; {\displaystyle t_{l}\leftarrow t;} t n ← t l + t a ( s ) ; {\displaystyle t_{n}\leftarrow t_{l}+ta(s);}
ビュー1: 合計状態 = 状態 * 経過時間 アトミック DEVS の動作 セクションで説明したように、DEVS が入力イベントを受信すると、 最後のイベント時間で ある の呼び出し権が 現在の時間 によって設定され 、 のため経過時間は 0 になります 。 δ e x t {\displaystyle \delta _{ext}} t l {\displaystyle t_{l}} t {\displaystyle t} t e {\displaystyle t_{e}} t e = t − t l {\displaystyle t_{e}=t-t_{l}}
x-message( , Time ) を受信するとき x ∈ X {\displaystyle x\in X} t {\displaystyle t} かつ == false の 場合 ( t l ≤ t {\displaystyle (t_{l}\leq t} t ≤ t n ) {\displaystyle t\leq t_{n})} エラー: 同期が不正です。 s ← δ e x t ( s , t − t l , x ) {\displaystyle s\leftarrow \delta _{ext}(s,t-t_{l},x)} t l ← t ; {\displaystyle t_{l}\leftarrow t;} t n ← t l + t a ( s ) ; {\displaystyle t_{n}\leftarrow t_{l}+ta(s);}
視点2: 総状態数 = 状態数 * 寿命 * 経過時間 アトミック DEVS の動作 セクションで説明されているように、 による戻り 値 、最後のイベント時間、 および次のイベント時間に応じ て、経過時間、 および寿命 が更新される ( の場合 ) か、または保持される ( の場合 ) ことに注意してください。 b {\displaystyle b} δ e x t {\displaystyle \delta _{ext}} t l {\displaystyle t_{l}} t n {\displaystyle t_{n}} t e {\displaystyle t_{e}} t n {\displaystyle t_{n}} b = 1 {\displaystyle b=1} b = 0 {\displaystyle b=0}
x-message( , Time ) を受信するとき x ∈ X {\displaystyle x\in X} t {\displaystyle t} かつ == false の 場合 ( t l ≤ t {\displaystyle (t_{l}\leq t} t ≤ t n ) {\displaystyle t\leq t_{n})} エラー: 同期が不正です。 ( s , b ) ← δ e x t ( s , t − t l , x ) {\displaystyle (s,b)\leftarrow \delta _{ext}(s,t-t_{l},x)} もし そうなら b = 1 {\displaystyle b=1} t l ← t ; {\displaystyle t_{l}\leftarrow t;} t n ← t l + t a ( s ) ; {\displaystyle t_{n}\leftarrow t_{l}+ta(s);}
結合されたDEVS 結合DEVSモデルが与えられた場合、シミュレーションアルゴリズムはモデルの 合法的な 動作、つまり不正な状態に到達しない軌跡のセットを生成する方法です。（ 結合DEVSモデルの動作を参照）。Zeiglerは当初、 寿命 と 経過時間 に関連する時間変数を処理するアルゴリズムを、 最後のイベント時間 、、 および 次のイベント時間 という2つの時間変数を導入し、 次の関係でそれらを処理しました。 [3] t s ∈ [ 0 , ∞ ] {\displaystyle t_{s}\in [0,\infty ]} t e ∈ [ 0 , ∞ ) {\displaystyle t_{e}\in [0,\infty )} t l ∈ [ 0 , ∞ ) {\displaystyle t_{l}\in [0,\infty )} t n ∈ [ 0 , ∞ ] {\displaystyle t_{n}\in [0,\infty ]}
t e = t − t l {\displaystyle \,t_{e}=t-t_{l}} そして
t s = t n − t l {\displaystyle \,t_{s}=t_{n}-t_{l}} ここで、 は 現在時刻 を表します 。そして 残り時間 は 、 t ∈ [ 0 , ∞ ) {\displaystyle t\in [0,\infty )}
t r = t s − t e {\displaystyle \,t_{r}=t_{s}-t_{e}} は次のように計算される。
t r = t n − t , {\displaystyle \,t_{r}=t_{n}-t,} どうやら 。これらの関係に基づいて、特定の結合されたDEVSの動作をシミュレートするアルゴリズムは次のように記述されます。 t r ∈ [ 0 , ∞ ] {\displaystyle t_{r}\in [0,\infty ]}
アルゴリズム DEVS コーディネーター 変数: 親 // 親コーディネーター t l {\displaystyle t_{l}} : // 最後のイベントの時間 : // 次のイベントの時間 // 関連する結合DEVSモデル t n {\displaystyle t_{n}} 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)} それぞれの init-message(Time t ) を受信すると 、 子に init-message( t )を送信 します 。 i ∈ D {\displaystyle i\in D} i {\displaystyle i} t l ← max { t l i : i ∈ D } {\displaystyle t_{l}\leftarrow \max\{t_{li}:i\in D\}} t n ← min { t n i : i ∈ D } {\displaystyle t_{n}\leftarrow \min\{t_{ni}:i\in D\}} スターメッセージを受信したとき ( 時刻 t ) t ≠ t n {\displaystyle t\neq t_{n}} エラー: 同期が不正です。 i ∗ ← S e l e c t ( { i ∈ D : t n i = t n } ) ; {\displaystyle i^{*}\leftarrow Select(\{i\in D:t_{ni}=t_{n}\});} スターメッセージ( t )を ; ;に送信します。 i ∗ {\displaystyle i^{*}} t l ← max { t l i : i ∈ D } {\displaystyle t_{l}\leftarrow \max\{t_{li}:i\in D\}} t n ← min { t n i : i ∈ D } {\displaystyle t_{n}\leftarrow \min\{t_{ni}:i\in D\}} x-message( , Time t ) を受信した とき 、 and == false の場合 x ∈ X {\displaystyle x\in X} ( t l ≤ t {\displaystyle (t_{l}\leq t} t ≤ t n ) {\displaystyle t\leq t_{n})} エラー: 同期が不正です。 それぞれに対して、 x -message( , t ) を子に送信し ます 。 ( x , x i ) ∈ C x x {\displaystyle (x,x_{i})\in C_{xx}} x i {\displaystyle x_{i}} i {\displaystyle i} t l ← max { t l i : i ∈ D } {\displaystyle t_{l}\leftarrow \max\{t_{li}:i\in D\}} t n ← min { t n i : i ∈ D } {\displaystyle t_{n}\leftarrow \min\{t_{ni}:i\in D\}} それぞれに対して y-message( , Time t ) を受信すると、 子に x-message( , t ) を送信 し、 そうで ない場合は 親に y-message( , t ) を送信します。 ; ; y i ∈ Y i {\displaystyle y_{i}\in Y_{i}} ( y i , x i ) ∈ C y x {\displaystyle (y_{i},x_{i})\in C_{yx}} x i {\displaystyle x_{i}} i {\displaystyle i} C y y ( y i ) ≠ ϕ {\displaystyle C_{yy}(y_{i})\neq \phi } C y y ( y i ) {\displaystyle C_{yy}(y_{i})} t l ← max { t l i : i ∈ D } {\displaystyle t_{l}\leftarrow \max\{t_{li}:i\in D\}} t n ← min { t n i : i ∈ D } {\displaystyle t_{n}\leftarrow \min\{t_{ni}:i\in D\}}
FD-DEVS FD-DEVS （ 有限・決定論的離散事象システム仕様）は、 離散事象動的システムを シミュレーションと検証の両方の方法でモデル化および解析するための形式です 。FD-DEVSは、Classic DEVSから継承されたモジュール型および階層型のモデリング機能も提供します。
歴史 FD-DEVSは、当初スケジュール制御可能なDEVS [27] と名付けられ、30年間DEVS形式論の 未解決問題 であったネットワークの検証解析を支援するために設計されました。さらに、 SP-DEVS のいわゆる「 OPNA 問題」を解決することも目的としていました 。従来のDEVSの観点から見ると、FD-DEVSには3つの制約があります。
事象集合と状態集合の有限性、 状態の寿命は 有理数 または無限大でスケジュールすることができ、 内部スケジュールは入力イベントによって保存または更新されます。 3つ目の制約は、入力イベントによってスケジュールが常に保存されるSP-DEVS からの緩和とも見ることができます 。この緩和によりOPNA問題は発生しなくなりますが、SP-DEVSネットワークの経過時間を抽象化するために使用できるタイムライン抽象化がFD-DEVSネットワークではもはや役に立たないという制約が1つあります。 [27] しかし、D. Dill教授によって発明された別の時間抽象化手法 [28] は、FD-DEVSネットワークの有限頂点到達可能性グラフを取得するために適用できます。
例
ピンポンゲーム 図1: 卓球ゲームのFD-DEVS結合図 2人のプレイヤーが参加する卓球の試合を例に考えてみましょう。各プレイヤーはFD-DEVSでモデル化でき、プレイヤーモデルは入力イベント ?receive と出力イベント !send を持ち 、 Send と Wait の2つの状態を持ちます。プレイヤーが「Send」状態に入ると、「!send」を生成し、送信時間（0.1時間単位）が経過すると「Wait」状態に戻ります。「Wait」状態のまま「?receive」状態になると、再び「Send」状態になります。つまり、プレイヤーモデルは「?receive」状態になるまで永遠に「Wait」状態のままです。
完全なピンポンマッチを作るには、一方のプレイヤーが攻撃側（初期状態は「送信」）として開始し、もう一方のプレイヤーが防御側（初期状態は「待機」）として開始します。したがって、図1では、プレイヤーAが最初の攻撃側、プレイヤーBが最初の防御側となります。さらに、ゲームを続行するには、図1に示すように、各プレイヤーの「?send」イベントを他のプレイヤーの「?receive」イベントと結合させる必要があります。
2スロットトースター 図2: (a) 2スロットトースター (b) 2スロットトースターのFD-DEVS結合図 図2(a)に示すように、2つのスロットがあり、それぞれにスタートノブが付いたトースターを考えてみましょう。各スロットは、トースト時間以外は同じ機能を持っています。最初はノブは押されていませんが、ノブを押すと、対応するスロットでトーストが開始され、それぞれのトースト時間（左のスロットは20秒、右のスロットは40秒）で焼き上がります。トースト時間が経過すると、各スロットとノブがポップアップします。対応するスロットがトースト中にノブを押そうとしても、何も起こらないことに注意してください。
図2(b)に示すように、FD-DEVSを用いてこれをモデル化することができます。2つのスロットは、入力イベントが「?push」、出力イベントが「!pop」であるアトミックFD-DEVSとしてモデル化されます。状態は「Idle」（I）と「Toast」（T）で、初期状態は「idle」です。「Idle」の状態で「?push」（ノブが押されたため）を受信すると、状態は「Toast」に変化します。つまり、「?push」イベントを受信しない限り、状態は永久に「Idle」のままです。20秒（つまり40秒）後、左（つまり右）のスロットは「Idle」に戻ります。
アトミック FD-DEVS
M =< X , Y , S , s 0 , τ , δ x , δ y > {\displaystyle M=<X,Y,S,s_{0},\tau ,\delta _{x},\delta _{y}>}
どこ
X {\displaystyle X} 入力イベントの有限集合 です 。 Y {\displaystyle Y} 出力イベントの有限集合 です 。 S {\displaystyle S} は有限の状態集合 である 。 s 0 ∈ S {\displaystyle s_{0}\in S} 初期状態 です 。 τ : S → Q [ 0 , ∞ ] {\displaystyle \tau :S\rightarrow \mathbb {Q} _{[0,\infty ]}} は、非負の有理数と無限大の集合である 状態の寿命を定義する 時間前進関数 です。 Q [ 0 , ∞ ] {\displaystyle \mathbb {Q} _{[0,\infty ]}} δ x : S × X → S × { 0 , 1 } {\displaystyle \delta _{x}:S\times X\rightarrow S\times \{0,1\}} は、入力イベントがシステムの状態とスケジュールをどのように変化させるかを定義する 外部遷移関数 である。状態の内部スケジュールは、 の場合 に によって更新され 、それ以外の場合（すなわち ）にはスケジュールが維持される。 [29] s ∈ S {\displaystyle s\in S} τ ( s ′ ) {\displaystyle \tau (s')} δ x ( s ) = ( s ′ , 1 ) {\displaystyle \delta _{x}(s)=(s',1)} δ x ( s ) = ( s ′ , 0 ) {\displaystyle \delta _{x}(s)=(s',0)} δ y : S → Y ϕ × S {\displaystyle \delta _{y}:S\rightarrow Y^{\phi }\times S} は 出力および内部遷移関数 であり 、 は サイレントイベント を表す 。出力および内部遷移関数は、状態がどのように出力イベントを生成するか、同時に状態が内部的にどのように変化するかを定義する。 [30] Y ϕ = Y ∪ { ϕ } {\displaystyle Y^{\phi }=Y\cup \{\phi \}} ϕ ∉ Y {\displaystyle \phi \notin Y} 卓球選手の正式な表現 図 1 に示すピンポンの例におけるプレーヤーの正式な表現は、次のように表すことができます。 ここで 、 ={?receive}; ={!send}; ={Send, Wait}; =プレーヤー A の場合は Send、プレーヤー B の場合は Wait; (Send)=0.1、 (Wait)= ; (Wait,?receive)=(Send,1)、 (Send,?receive)=(Send,0)、 (Send)=(!send, Wait)、 (Wait)=( , Wait)。 M =< X , Y , S , s 0 , τ , δ x , δ y > {\displaystyle M=<X,Y,S,s_{0},\tau ,\delta _{x},\delta _{y}>} X {\displaystyle X} Y {\displaystyle Y} S {\displaystyle S} s 0 {\displaystyle s_{0}} τ {\displaystyle \tau } τ {\displaystyle \tau } ∞ {\displaystyle \infty } δ x {\displaystyle \delta _{x}} δ x {\displaystyle \delta _{x}} δ y {\displaystyle \delta _{y}} δ y {\displaystyle \delta _{y}} ϕ {\displaystyle \phi }
1スロットトースターの正式な表現 2スロットトースター図2(a)および(b)のスロットの正式な表現は、次のように表すことができます。 ここで 、 ={?push}; ={!pop}; ={I, T}; =I; 左のスロットの場合は(T)=20、右のスロットの場合は40、 (I)= ; (I, ?push)=(T,1)、 (T,?push)=(T,0)、 (T)=(!pop, I)、 (I)=( , I) です。 M =< X , Y , S , s 0 , τ , δ x , δ y > {\displaystyle M=<X,Y,S,s_{0},\tau ,\delta _{x},\delta _{y}>} X {\displaystyle X} Y {\displaystyle Y} S {\displaystyle S} s 0 {\displaystyle s_{0}} τ {\displaystyle \tau } τ {\displaystyle \tau } ∞ {\displaystyle \infty } δ x {\displaystyle \delta _{x}} δ x {\displaystyle \delta _{x}} δ y {\displaystyle \delta _{y}} δ y {\displaystyle \delta _{y}} ϕ {\displaystyle \phi }
横断歩道信号制御装置の正式な表現 上で述べたように、FD-DEVS は SP-DEVS の緩和版です。つまり、FD-DEVS は SP-DEVS のスーパークラスです。 この Wikipedia では、 SP-DEVS で使用されている 横断歩道信号コントローラ の FD-DEVS モデルを示します。ここで 、 ={?p}; ={!g:0, !g:1, !w:0, !w:1}; ={BG, BW, G, GR, R, W, D}; =BG, (BG)=0.5, (BW)=0.5, (G)=30, (GR)=30, (R)=2, (W)=26, (D)=2; (G,?p)=(GR,0), (s,?p)=(s,0) if s G; (BG)=(!g:1, BW)、 (BW)=(!w:0, G)、 (G)=( 、G)、 (GR)=(!g:0, R)、 (R)=(!w:1, W)、 (W)=(!w:0, D)、 (D)=(!g:1, G); M =< X , Y , S , s 0 , τ , δ x , δ y > {\displaystyle M=<X,Y,S,s_{0},\tau ,\delta _{x},\delta _{y}>} X {\displaystyle X} Y {\displaystyle Y} S {\displaystyle S} s 0 {\displaystyle s_{0}} τ {\displaystyle \tau } τ {\displaystyle \tau } τ {\displaystyle \tau } τ {\displaystyle \tau } τ {\displaystyle \tau } τ {\displaystyle \tau } τ {\displaystyle \tau } δ x {\displaystyle \delta _{x}} δ x {\displaystyle \delta _{x}} ≠ {\displaystyle \neq } δ y {\displaystyle \delta _{y}} δ y {\displaystyle \delta _{y}} δ y {\displaystyle \delta _{y}} ϕ {\displaystyle \phi } δ y {\displaystyle \delta _{y}} δ y {\displaystyle \delta _{y}} δ y {\displaystyle \delta _{y}} δ y {\displaystyle \delta _{y}}
FD-DEVSモデルの動作 図3. イベントセグメントとプレイヤーAの状態軌跡 FD-DEVSはDEVSのサブクラスである FD-DEVSモデルは、 DEVS が M =< X , Y , S , s 0 , τ , δ x , δ y > {\displaystyle M=<X,Y,S,s_{0},\tau ,\delta _{x},\delta _{y}>} M =< X , Y , S ′ , s 0 ′ , t a , δ e x t , δ i n t , λ > {\displaystyle {\mathcal {M}}=<X,Y,S',s_{0}',ta,\delta _{ext},\delta _{int},\lambda >}
X , Y {\displaystyle X,Y} の は の と同じです 。 M {\displaystyle {\mathcal {M}}} M {\displaystyle M} S ′ = { ( s , t s ) : s ∈ S , t s ∈ T ∞ } {\displaystyle S'=\{(s,t_{s}):s\in S,t_{s}\in \mathbb {T} ^{\infty }\}} s 0 ′ = ( s 0 , τ ( s 0 ) ) {\displaystyle s_{0}'=(s_{0},\tau (s_{0}))} 状態が与えられた場合 、 ( s , t s ) ∈ S ′ {\displaystyle (s,t_{s})\in S'} t a ( s , t s ) = t s . {\displaystyle ta(s,t_{s})=t_{s}.} 状態 と入力イベントが与えられると 、 ( s , t s ) ∈ S ′ {\displaystyle (s,t_{s})\in S'} x ∈ X {\displaystyle x\in X} δ e x t ( s , t s , t e , x ) = { ( s ′ , t s − t e ) if δ x ( s , x ) = ( s ′ , 0 ) ( s ′ , τ ( s ′ ) ) if δ x ( s , x ) = ( s ′ , 1 ) {\displaystyle \delta _{ext}(s,t_{s},t_{e},x)={\begin{cases}(s',t_{s}-t_{e})&{\text{if }}\delta _{x}(s,x)=(s',0)\\(s',\tau (s'))&{\text{if }}\delta _{x}(s,x)=(s',1)\\\end{cases}}}
状態が与えられた 場合 、 ( s , t s ) ∈ S ′ {\displaystyle (s,t_{s})\in S'} δ i n t ( s , t s ) = ( s ′ , τ ( s ′ ) ) {\displaystyle \delta _{int}(s,t_{s})=(s',\tau (s'))} δ y ( s ) = ( y , s ′ ) . {\displaystyle \delta _{y}(s)=(y,s').} 状態が与えられた 場合 、 ( s , t s ) ∈ S ′ {\displaystyle (s,t_{s})\in S'} λ ( s , t s ) = y {\displaystyle \lambda (s,t_{s})=y} δ y ( s ) = ( y , s ′ ) . {\displaystyle \delta _{y}(s)=(y,s').} DEVS の動作の詳細については、 atomic DEVS の動作 セクションを参照してください 。
卓球選手Aの行動 図3は、図1で紹介したピンポンゲームをプレイするプレイヤーAのイベントセグメント（上）と、関連する状態軌跡（下）を示しています。図3では、プレイヤーAの状態は（状態、生存期間、経過時間）=（ ）と記述され、図3の下部の線分は経過時間の値を示しています。プレイヤーAの初期状態は「Send」で、生存期間は0.1秒であるため、（Send, 0.1, ）の高さは0.1であり、これは の値です 。 が0にリセットされたときに（Wait, inf, 0）に変化した後 、プレイヤーAは がいつ再び0になるかわかりません 。しかし、プレイヤーBが0.1秒後にボールをプレイヤーAに送り返すため、プレイヤーAは時刻0.2に（Send, 0.1 0）に戻ります。その時点から0.1秒後、プレイヤーAの状態が(Send, 0.1, 0.1)になると、プレイヤーAはプレイヤーBにボールを送り返し、(Wait, inf, 0)の状態になります。このように、「Send」と「Wait」を行き来するこの循環的な状態遷移は永久に繰り返されます。 s , t s , t e {\displaystyle s,t_{s},t_{e}} t e {\displaystyle t_{e}} t s {\displaystyle t_{s}} t e {\displaystyle t_{e}} t e {\displaystyle t_{e}}
図4. トースターのイベントセグメントと状態軌跡 トースターの動作 図4は、図2で紹介した2スロットトースターの左スロットのイベントセグメント（上）と関連する状態軌跡（下）を示しています。図3と同様に、図4 では左スロットの状態は（状態、寿命、経過時間）=（）と記述されています。トースターの初期状態は「I」で寿命は無限大であるため、（Wait, inf, ）の高さは、?pushの発生時刻によって決定できます。図4は、?pushが時刻40で発生し、トースターの状態が（T, 20, 0）に変化するケースを示しています。その時点から20秒後、状態が（T, 20, 20）になると、トースターは（Wait, inf, 0）に戻りますが、いつ再び「Toast」に戻るかはわかりません。図4は、時刻90で「?push」が発生し、トースターが(T,20,0)に移動したケースを示しています。時刻97で誰かが再び「push」したにもかかわらず、(T, ?push)=(T,1)であるため、状態(T,20,7)は全く変化しないことに注意してください。 s , t s , t e {\displaystyle s,t_{s},t_{e}} t e {\displaystyle t_{e}} δ x {\displaystyle \delta _{x}}
利点 図5. 2スロットトースターの到達可能性グラフ
タイムゾーン抽象化の適用性 有限数の状態とイベントとともに入力イベントによって保存または変更できる非負の有理数値寿命の特性は、FD-DEVSネットワークの動作が、経過時間の無限個の値をD. Dill教授によって導入された時間抽象化技術を使用して抽象化することによって、同等の有限頂点到達可能性グラフとして抽象化できることを保証します。 [28] 有限頂点到達可能性グラフ（RG）を生成するアルゴリズムは、Zeiglerによって導入されました。 [25] [31]
到達可能性グラフ 図5は、図2に示した2スロットトースターの到達可能性グラフを示している。到達可能性グラフでは、各頂点は独自の離散状態と時間帯を持ち、これらは範囲とである 。 例えば、図5のノード(6)の場合、離散状態情報は((E, ),(T,40))であり、時間帯はである 。各有向アーチは、関連するイベントとリセットモデルの集合とともに、そのソース頂点がデスティネーション頂点にどのように変化するかを示している。例えば、遷移アーク(6)から(5)は push1 イベントによってトリガーされる。その時、アークの集合{1}は経過時間1（つまり、 遷移(6)から(5)が発生したときに0にリセットされる）を示す。 [25] t e 1 , t e 2 {\displaystyle t_{e1},t_{e2}} t e 1 − t e 2 {\displaystyle t_{e1}-t_{e2}} ∞ {\displaystyle \infty } 0 ≤ t e 1 ≤ 40 , 0 ≤ t e 2 ≤ 40 , − 20 ≤ t e 1 − t 21 ≤ 0 {\displaystyle 0\leq t_{e1}\leq 40,0\leq t_{e2}\leq 40,-20\leq t_{e1}-t_{21}\leq 0} t e 1 {\displaystyle t_{e1}}
安全性の決定可能性 定性的な特性として、FD-DEVSネットワークの安全性は、(1)与えられたネットワークのRGを生成し、(2)いくつかの悪い状態に到達可能かどうかを確認することによって決定できます。 [24]
生存の決定可能性 定性的な特性として、FD-DEVSネットワークの活性は、(1)与えられたネットワークのRGを生成すること、(2)RGから、 頂点が 強く連結された成分であるカーネル 有向非巡回グラフ （KDAG）を生成すること、(3)KDAGの頂点に活性状態の集合を含む状態遷移サイクルが含まれているかどうかを確認することによって決定できる。 [24]
デメリット
非決定性を記述する表現力が弱い FD-DEVS のすべての特性関数が決定論的であるという特徴は、 非決定論的な振る舞いを持つシステムをモデル化する際、ある種の制約となる可能性があります。例えば、図1に示すピンポンゲームのプレイヤーが「送信」状態で確率的な寿命を持つ場合、FD-DEVS は非決定論的な振る舞いを効果的に捉えることができません。 τ , δ x , δ y {\displaystyle \tau ,\delta _{x},\delta _{y}}
検証のため C#で書かれたDEVS# [32]と Python で書かれたXSY [33] という2つのオープンソースライブラリがあり 、安全性と活性を見つけるための到達可能性グラフベースの検証アルゴリズムをサポートしています。
XML経由のシミュレーション DEVS、特にFDDEVSを用いた標準化のために、サウラブ・ミッタル博士は同僚とともにFDDEVSのXML形式の定義に取り組んできました。 [34] この標準XML形式はUMLの実行に使用されました。 [35]
SP-開発者 SP-DEVS （ スケジュール保持型離散事象システム仕様 ）は、離散事象システムをシミュレーションと検証の両方の方法でモデリングおよび解析するための形式です。SP-DEVSは、従来のDEVSから継承されたモジュール型および階層型のモデリング機能も提供します。
歴史 SP-DEVSは、ネットワークの検証分析を支援するために設計されており、元のネットワークの有限頂点到達可能性グラフを取得することを保証しています。これは、約30年間DEVS形式における未解決問題でした。ネットワークのこのような到達可能性グラフを取得するために、SP-DEVSには以下の3つの制約が課されています。
事象集合と状態集合の有限性、 状態の寿命は有理数または無限大でスケジュールすることができ、 外部イベントから内部スケジュールを保護します。 したがって、SP-DEVSはDEVSとFD-DEVSの両方のサブクラスです。これらの3つの制約により、状態数が有限であっても、SP-DEVSクラスは結合に対して閉じています。この性質により、SP-DEVS結合モデルであっても、いくつかの質的特性と量的特性について有限頂点グラフに基づく検証が可能になります。
横断歩道コントローラの例 システム要件 図1. 横断歩道システム 図2. 横断歩道信号コントローラのSP-DEVSモデル 横断歩道システムを考えてみましょう。赤信号（それぞれ歩行禁止信号）は青信号（それぞれ歩行者信号）とは逆の動作をするため、図1に示すように、緑信号（G）と歩行者信号（W）の2つの信号と、1つの押しボタンだけを考えます。GとWの2つの信号を、一連のタイミング制約に従って制御します。
2つのライトを初期化するには、Gが点灯するまでに0.5秒かかり、0.5秒後にWが消灯します。その後、30秒ごとに、誰かが押しボタンを押すと、Gが消灯しWが点灯する可能性があります。安全上の理由から、Gが消灯してから2秒後にWが点灯します。26秒後にWが消灯し、さらに2秒後にGが再び点灯します。これらの動作が繰り返されます。
コントローラー設計 上記の要件を満たすコントローラーを構築するには、1 つの入力イベント「push-button」（?p で省略）と、青信号と歩行信号のコマンド信号として使用される 4 つの出力イベント「green-on」（!g:1）、「green-off」（!g:0）、「walk-on」（!w:1）、「walk-off」（!w:0）を検討します。 コントローラーの状態セットとして、「booting-green」（BG）、「booting-walk」（BW）、「green-on」（G）、「green-to-red」（GR）、「red-on」（R）、「walk-on」（W）、「delay」（D）を検討します。 図 2 に示すように状態遷移を設計しましょう。 最初、コントローラーは寿命が 0.5 秒の BG から開始します。 寿命が過ぎると、BW 状態に移行し、この時点で「green-on」イベントも生成します。 BWに0.5秒間滞在した後、30秒間存続するG状態に移行します。コントローラは、出力イベントを生成せずにGからGにループすることでGに留まり続けることも、外部入力イベント?pを受信したときにGR状態に移行することもできます。ただし、 GRでの 実際の滞在時間 は、Gでのループの残り時間です。GRから、出力イベント!g:0を生成してR状態に移行し、そのR状態は2秒間持続した後、出力イベント!w:1を生成してW状態に移行します。26秒後、!w:0を生成してD状態に移行し、Dで2秒間滞在した後、出力イベント!g:1を生成してGに戻ります。
アトミック SP-DEVS
上記の横断歩道信号機のコントローラは、アトミックSP-DEVSモデルでモデル化できます。正式には、アトミックSP-DEVSは7つの 要素から構成されるタプルです。 M =< X , Y , S , s 0 , τ , δ x , δ y > {\displaystyle M=<X,Y,S,s_{0},\tau ,\delta _{x},\delta _{y}>}
どこ
X {\displaystyle X} 入力イベントの有限集合 です 。 Y {\displaystyle Y} 出力イベントの有限集合 です 。 S {\displaystyle S} は有限の状態集合 である 。 s 0 ∈ S {\displaystyle s_{0}\in S} 初期状態 です 。 τ : S → Q [ 0 , ∞ ] {\displaystyle \tau :S\rightarrow \mathbb {Q} _{[0,\infty ]}} は、非負の有理数と無限大の集合である 状態の寿命を定義する 時間進行関数 です。 Q [ 0 , ∞ ] {\displaystyle \mathbb {Q} _{[0,\infty ]}} δ x : S × X → S {\displaystyle \delta _{x}:S\times X\rightarrow S} 入力イベントがシステムの状態をどのように変化させるかを定義する 外部遷移関数 です。 δ y : S → Y ϕ × S {\displaystyle \delta _{y}:S\rightarrow Y^{\phi }\times S} は 出力および内部遷移関数 であり 、 は サイレントイベント を表す 。出力および内部遷移関数は、状態がどのように出力イベントを生成するか、同時に状態が内部的にどのように変化するかを定義する。 [36] Y ϕ = Y ∪ { ϕ } {\displaystyle Y^{\phi }=Y\cup \{\phi \}} ϕ ∉ Y {\displaystyle \phi \notin Y} 横断歩道管理者の正式な表現 図 2 に示す上記のコントローラは、次のように記述できます。 ここで 、={?p}; ={!g:0, !g:1, !w:0, !w:1}; ={BG, BW, G, GR, R, W, D}; =BG、 (BG) =0.5、 (BW)=0.5、(G) = 30、 (GR)=30、 (R)=2、(W)=26、 (D)=2; (G、?p)=GR、 (s、?p)=s if s G; (BG)=(!g:1, BW)、 (BW)=(!w:0, G)、 (G)=( 、G)、 (GR)=(!g:0, R)、 (R)=(!w:1, W)、 (W)=(!w:0, D)、 (D)=(!g:1, G); M =< X , Y , S , s 0 , τ , δ x , δ y > {\displaystyle M=<X,Y,S,s_{0},\tau ,\delta _{x},\delta _{y}>} X {\displaystyle X} Y {\displaystyle Y} S {\displaystyle S} s 0 {\displaystyle s_{0}} τ {\displaystyle \tau } τ {\displaystyle \tau } τ {\displaystyle \tau } τ {\displaystyle \tau } τ {\displaystyle \tau } τ {\displaystyle \tau } τ {\displaystyle \tau } δ x {\displaystyle \delta _{x}} δ x {\displaystyle \delta _{x}} ≠ {\displaystyle \neq } δ y {\displaystyle \delta _{y}} δ y {\displaystyle \delta _{y}} δ y {\displaystyle \delta _{y}} ϕ {\displaystyle \phi } δ y {\displaystyle \delta _{y}} δ y {\displaystyle \delta _{y}} δ y {\displaystyle \delta _{y}} δ y {\displaystyle \delta _{y}}
SP-DEVSモデルの動作 図3. SP-DEVSモデルのイベントセグメントとその状態軌跡 原子SP-DEVSのダイナミクスを捉えるには、時間に関連する2つの変数を導入する必要があります。1つは 寿命 、もう1つは 最後のリセットからの 経過時間 です。は寿命を表します。寿命は連続的に増加するのではなく、離散イベントが発生したときに設定されます。 は 経過時間を表します。経過時間は、リセットがない場合、時間の経過とともに連続的に増加します。 t s ∈ Q [ 0 , ∞ ] {\displaystyle t_{s}\in \mathbb {Q} _{[0,\infty ]}} t e ∈ [ 0 , ∞ ] {\displaystyle t_{e}\in [0,\infty ]}
図 3 は、図 2 に示した SP-DEVS モデルのイベント セグメントに関連付けられた状態軌跡を示しています。図 3 の上部には、横軸が時間軸であるイベント トラジェクトリが示されているため、特定の時間にイベントが発生することを示しています。たとえば、!g:1 は 0.5 で発生し、!w:0 は 1.0 時間単位で発生します。図 3 の下部には、上記のイベント セグメントに関連付けられた状態軌跡が示されており、状態は その寿命と経過時間に の形式で関連付けられています 。たとえば、(G, 30, 11) は、状態が G で、寿命が であり、経過時間が 11 時間単位であることを示します。図 3 の下部の線分は、SP-DEVS で唯一の連続変数である経過時間の時間フローを示しています。 s ∈ S {\displaystyle s\in S} ( s , t s , t e ) {\displaystyle (s,t_{s},t_{e})}
SF-DEVSの興味深い特徴の1つは、外部イベント?pが発生したときに図3の時刻47に描かれているSP-DEVSの制約(3)のスケジュールが保存されることです。この瞬間、状態がGからGRに変化しても経過時間は変わらないため、線分は時刻47で途切れず、この例では30 まで成長できます 。入力イベントからのスケジュールのこの保存と、時間の進み方が非負の有理数に制限されているため(上記の制約(2)を参照)、SP-DEVSモデルでは、すべてののこぎりの高さは非負の有理数または無限大になります(図3の下部に示すように)。 t e {\displaystyle t_{e}} t e {\displaystyle t_{e}}
SP-DEVSはDEVSのサブクラスである SP-DEVSモデルは、 DEVS において M =< X , Y , S , s 0 , τ , δ x , δ y > {\displaystyle M=<X,Y,S,s_{0},\tau ,\delta _{x},\delta _{y}>} M =< X , Y , S ′ , s 0 ′ , t a , δ e x t , δ i n t , λ > {\displaystyle {\mathcal {M}}=<X,Y,S',s_{0}',ta,\delta _{ext},\delta _{int},\lambda >}
X , Y {\displaystyle X,Y} の は の と同じです 。 M {\displaystyle {\mathcal {M}}} M {\displaystyle M} S ′ = { ( s , t s ) : s ∈ S , t s ∈ T ∞ } {\displaystyle S'=\{(s,t_{s}):s\in S,t_{s}\in \mathbb {T} ^{\infty }\}} s 0 ′ = ( s 0 , τ ( s 0 ) ) {\displaystyle s_{0}'=(s_{0},\tau (s_{0}))} 状態が与えられた場合 、 ( s , t s ) ∈ S ′ {\displaystyle (s,t_{s})\in S'} t a ( s , t s ) = t s . {\displaystyle ta(s,t_{s})=t_{s}.} 状態 と入力イベントが与えられた場合 ( s , t s ) ∈ S ′ {\displaystyle (s,t_{s})\in S'} x ∈ X , δ e x t ( s , t s , t e , x ) = ( s ′ , t s − t e ) if δ x ( s , x ) = s ′ . {\displaystyle x\in X,\delta _{ext}(s,t_{s},t_{e},x)=(s',t_{s}-t_{e}){\text{ if }}\delta _{x}(s,x)=s'.} 状態が与えられた 場合 、 ( s , t s ) ∈ S ′ {\displaystyle (s,t_{s})\in S'} δ i n t ( s , t s ) = ( s ′ , τ ( s ′ ) {\displaystyle \delta _{int}(s,t_{s})=(s',\tau (s')} δ y ( s ) = ( y , s ′ ) . {\displaystyle \delta _{y}(s)=(y,s').} 状態が与えられた 場合 、 ( s , t s ) ∈ S ′ {\displaystyle (s,t_{s})\in S'} λ ( s , t s ) = y {\displaystyle \lambda (s,t_{s})=y} δ y ( s ) = ( y , s ′ ) . {\displaystyle \delta _{y}(s)=(y,s').}
利点 有限数の状態とイベントとともに入力イベントによって変更されない非負の有理数値の寿命の特性は、経過時間の無限個の値を抽象化することによって、SP-DEVS ネットワークの動作を同等の有限頂点到達可能性グラフとして抽象化できることを保証します。
SP-DEVSネットワークの各コンポーネントの経過時間の無限の場合を抽象化するために、タイム ライン抽象化 と呼ばれる、スケジュールの順序と相対的な差が保存される時間抽象化手法が導入されました。 [37] [38] タイムライン抽象化技術を使用することで、任意のSP-DEVSネットワークの動作を、頂点と辺の数が有限である到達可能性グラフとして抽象化できます。
定性的な特性として、SP-DEVSネットワークの安全性は、（1）与えられたネットワークの有限頂点到達可能性グラフを生成し、（2）いくつかの悪い状態が到達可能かどうかを確認することによって決定できます。 [37]
質的特性として、SP-DEVSネットワークの活性は、(1)与えられたネットワークの有限頂点到達可能性グラフ(RG)を生成すること、(2)RGから、頂点が 強く連結された成分であるカーネル有向 非巡回グラフ (KDAG)を生成すること 、(3)KDAGの頂点に活性状態の集合を含む状態遷移サイクルが含まれているかどうかを確認することによって決定できる。 [37]
定量的な特性として、SP-DEVSネットワークにおける2つのイベントからの最小および最大処理時間境界は、(1)有限頂点到達可能性グラフを生成し、(2.a)最小処理時間境界の最短経路を求め、(2.b)最大処理時間境界の最長経路（もしあれば）を求めることによって計算できる。 [38]
デメリット の場合、 SP-DEVS モデルの 全状態を パッシブに します。それ以外の場合は、 アクティブ にします。 ( s , t s , t e ) {\displaystyle (s,t_{s},t_{e})} t s = ∞ {\displaystyle t_{s}=\infty }
SP-DEVSの既知の限界の一つは、「SP-DEVSモデルが一度パッシブ状態になると、二度とアクティブ状態に戻らない（OPNA）」という現象である。この現象はHwang [39] によって初めて発見されたが、当初はODNR（「一度死んだら二度と戻らない」）と呼ばれていた。この現象が発生する理由は、上記の制約（3）により、入力イベントによってスケジュールが変更されないため、パッシブ状態からアクティブ状態に復帰できないためである。
例えば、図3(b)に示すトースターモデルは、SP-DEVSではありません。「アイドル」（I）に関連付けられた全体状態は受動的ですが、トースト時間が20秒または40秒である「トースト」（T）という能動的状態に移行するためです。実際には、図3(b)に示すモデルは FD-DEVS です。
DEVS# [32] と呼ばれるオープンソースライブラリがあり、 安全性と活性度、および最小/最大処理時間の境界を見つけるためのいくつかのアルゴリズムをサポートしています。
参照
DEVS関連記事
参考文献 ^ ab Zeigler, Bernard (1976). モデリングとシミュレーションの理論（第1版）. ニューヨーク: Wiley Interscience. ISBN 0-12-778455-1 2012年6月21日時点のオリジナルよりアーカイブ。 ^ Zeigler, Bernard (1968). オートマトンにおけるフィードバック複雑性について (Ph.D.). ミシガン大学. オートマトンとはザイグラー博士の博士論文の数学的モデルであった。 ^ abcd Zeigler, Bernard (1984). 多面的モデリングと離散事象シミュレーション . ロンドン; オーランド: Academic Press. ISBN 978-0-12-778450-2 。 ^ Zeigler, Bernard (1987). 「オブジェクト指向環境における階層的かつモジュール型の離散イベントモデリング」. シミュレーション . 49 (5): 219– 230. doi :10.1177/003754978704900506. S2CID 62648626. ^ Zeigler, Bernard; Kim, Tag Gon; Praehofer, Herbert (2000). 『モデリングとシミュレーションの理論』 （第2版）. ニューヨーク: Academic Press. ISBN 978-0-12-778455-7 。 ^ 外部遷移関数を と定義することもできます。 ここで 、は 全体状態 に対して 部分状態 、 は の寿命 、は の 最終更新 からの経過時間 となります 。この関数の理解方法の詳細については、 「DEVS の動作」の 記事を参照してください 。 δ e x t : Q × X → S × { 0 , 1 } {\displaystyle \delta _{ext}:Q\times X\rightarrow S\times \{0,1\}} Q = S × T ∞ × T {\displaystyle Q=S\times \mathbb {T} ^{\infty }\times \mathbb {T} } ( s , t s , t e ) ∈ Q {\displaystyle (s,t_{s},t_{e})\in Q} s ∈ S {\displaystyle s\in S} t s ∈ T ∞ {\displaystyle t_{s}\in \mathbb {T} ^{\infty }} s {\displaystyle s} t e ∈ ( T ∩ [ 0 , t s ] ) {\displaystyle t_{e}\in (\mathbb {T} \cap [0,t_{s}])} t s {\displaystyle t_{s}} ^ [ 要引用 ] ^ セリエ、フランソワ E. (1991)。 継続的システム モデリング (第 1 版)。スプリンガー。 ISBN 978-0-387-97502-3 。 ^ セリエ、フランソワ E.コフマン、アーネスト (2006)。 連続システム シミュレーション (第 1 版)。スプリンガー。 ISBN 978-0-387-26102-7 。 ^ Nutaro, James (2010). 『シミュレーションのためのソフトウェア構築：C++による理論、アルゴリズム、アプリケーション』 （第1版）. Wiley. ISBN 978-0-470-41469-9 。 ^ 離散事象 法を用いて連続システムをシミュレートするために量子化された値を用いることは、 それより数年前、1990年代初頭に、ある フランス 人エンジニアによって実験的に試みられていました。彼は当時、 ヴァランシエンヌ大学 からスピンオフした企業 （現在はシュナイダーエレクトリック 傘下）に勤務していました 。この 量子化は 、このエンジニアが構想者であり主要 開発者でもある シミュレーション ソフトウェア の機能であり 、 PLC プログラムのチェックやオペレータのトレーニング に使用されています。 ^ Hwang, MH; Zeigler, BP (2009). 「有限かつ決定論的DEVSネットワークの到達可能性グラフ」. IEEE Transactions on Automation Science and Engineering . 6 (3): 454– 467. doi :10.1109/TASE.2009.2024064 (2025年7月1日非アクティブ). {{cite journal }}: CS1 maint: DOI inactive as of July 2025 (link )^ ab Hwang, MH "43". 有限およびリアルタイムDEVSネットワークの定性的検証 。2012年モデリング・シミュレーション理論シンポジウム議事録 - DEVS統合M&Sシンポジウム。 ^ Hwang, MH (2005年4月2日～8日). チュートリアル: スケジュール保存型DEVSに基づくリアルタイムシステムの検証 . 2005年DEVSシンポジウム議事録. サンディエゴ. ISBN 1-56555-293-8 。 ^ Hwang, MH; Zeigler, BP 「有限かつ決定論的DEVSを用いたモジュラー検証フレームワーク」 2006年DEVSシンポジウム議事録。米国アラバマ州ハンツビル。pp. 57– 65。 ^ Zeigler, Bernard (1976). モデリングとシミュレーションの理論 （初版）. ニューヨーク: Wiley Interscience. ^ Zeigler, Bernard ; Kim, Tag Gon ; Praehofer, Herbert (2000). 『モデリングとシミュレーションの理論』 （第2版）. ニューヨーク: Academic Press. ISBN 978-0-12-778455-7 。 ^ Hwang, Moon H. (2012). 有限およびリアルタイムDEVSネットワークの定性的検証 . Proceedings of 2012 TMS/DEVS. オーランド、フロリダ州、米国. pp. 43:1–43:8. ISBN 978-1-61839-786-7 。 ^ Giambiasi, N.; Escude, B.; Ghosh, S. (2001). 「動的システムの一般化離散イベントシミュレーション」. SCS Transactions: DEVS方法論の最近の進歩-パートII . 18 (4): 216– 229. ^ Zacharewicz, Gregory; Frydman, Claudia; Giambiasi, Norbert (2008). 「ワークフローの分散シミュレーションのためのG-DEVS/HLA環境」 (PDF) . シミュレーション . 84 (5): 197– 213. doi :10.1177/0037549708092833. ^ ウェイナー、ガブリエル・A. (2009). 『離散事象モデリングとシミュレーション：実践者のためのアプローチ』 （第1版）CRC Press. ISBN 978-1-4200-5336-4 。 ^ ab Zeigler, Bernard ; Kim, Tag Gon ; Praehofer, Herbert (2000). Theory of Modeling and Simulation (second ed.). New York: Academic Press. ISBN 978-0-12-778455-7 。 ^ ab Zeigler, Bernard (1984). 多面的モデリングと離散事象シミュレーション . ロンドン; オーランド: Academic Press. ISBN 978-0-12-778450-2 。 ^ abcde Hwang, MH; Zeigler, Bernard (2006). 有限かつ決定論的なDEVSネットワークの到達可能グラフ. 2006年DEVSシンポジウム議事録. アラバマ州ハンツビル. pp. 48– 56. 2012年7月26日時点のオリジナルよりアーカイブ。 ^ abcde Hwang, MH; Zeigler, Bernard (2009). 「有限および決定論的DEVSの到達可能性グラフ」. IEEE Transactions on Automation Science and Engineering . 6 (3): 454– 467. doi :10.1109/TASE.2009.2024064 (2025年7月1日非アクティブ). {{cite journal }}: CS1 maint: DOI inactive as of July 2025 (link )^ Zeigler, Bernard; Kim, Tag Gon; Praehofer, Herbert (2000). 『モデリングとシミュレーションの理論』 （第2版）. ニューヨーク: Academic Press. ISBN 978-0-12-778455-7 。 ^ ab Hwang, MH (2005年8月). 再構成可能な自動化システムの有限状態グローバル動作の生成：DEVSアプローチ. Proceedings of 2005 IEEE-CASE. エドモントン、カナダ. 2012年12月8日時点のオリジナルよりアーカイブ。 ^ ab Dill, DL (1989). 有限状態並行システムのタイミング仮定と検証 . 有限状態システムのコンピュータ支援検証手法に関するワークショップ議事録. グルノーブル, フランス. pp. 197– 212. ^ Hwang, MH (2005年8月). 再構成可能な自動化システムの有限状態グローバル動作の生成：DEVSアプローチ. Proceedings of 2005 IEEE-CASE. エドモントン、カナダ. 2012年12月8日時点のオリジナルよりアーカイブ。 （注： は と の 2 つの機能に分けられます ） δ x {\displaystyle \delta _{x}} ρ : S × X → { 0 , 1 } {\displaystyle \rho :S\times X\rightarrow \{0,1\}} δ x : S × X → S {\displaystyle \delta _{x}:S\times X\rightarrow S} ^ Zeigler, Bernard ; Kim, Tag Gon ; Praehofer, Herbert (2000). 『モデリングとシミュレーションの理論』 （第2版）. ニューヨーク: Academic Press. ISBN 978-0-12-778455-7 。 （注： は と の 2 つの機能に分けられます ） δ y {\displaystyle \delta _{y}} λ : S → Y ϕ {\displaystyle \lambda :S\rightarrow Y^{\phi }} δ i n t : S → S {\displaystyle \delta _{int}:S\rightarrow S} ^ Hwang, MH; Zeigler, Bernard (2006). 有限かつ決定論的DEVSを用いたモジュラー検証フレームワーク. 2006年DEVSシンポジウム議事録. アラバマ州ハンツビル. pp. 57– 65. 2012年7月26日時点のオリジナルよりアーカイブ。 ^ ab "DEVSsharp" . 2025年4月13日 閲覧。 ^ 「XSY」。 ^ Mittal, Saurabh. 「xFDDEVS」 . 2025年4月13日 閲覧。 ^ Risco-Martín, José L.; de la Cruz, Jesús M.; Mittal, Saurabh; Zeigler, Bernard (2009). 「eUDEVS: DEVS理論に基づく実行可能なUMLモデリングとシミュレーション」. SIMULATION, Transaction of the Society for Modeling and Simulation International . 85 ( 11–12 ): 750–777 . arXiv : 2407.08281 . doi :10.1177/0037549709104727. ^ Zeigler, Bernard ; Kim, Tag Gon ; Praehofer, Herbert (2000). 『モデリングとシミュレーションの理論』 （第2版）. ニューヨーク: Academic Press. ISBN 978-0-12-778455-7 。 （注： は と の 2 つの機能に分けられます ） δ y {\displaystyle \delta _{y}} λ : S → Y ϕ {\displaystyle \lambda :S\rightarrow Y^{\phi }} δ i n t : S → S {\displaystyle \delta _{int}:S\rightarrow S} ^ abc Hwang, MH (2005年4月2日～8日). チュートリアル: スケジュール保存型DEVSに基づくリアルタイムシステムの検証. 2005年DEVSシンポジウム議事録. サンディエゴ. ISBN 978-1-56555-293-7 。 ^ ab Hwang, MH; Cho, SK; Zeigler, Bernard ; Lin, F. (2007). スケジュール保持型DEVSの処理時間境界（レポート）. ACIMS. 2012年7月26日時点のオリジナルよりアーカイブ。 2008年3月18日 閲覧 。 ^ Hwang, MH (2005年8月1～2日). 「再構成可能な自動化システムの有限状態グローバル動作の生成：DEVSアプローチ」2005年IEEE-CASE会議論文集. エドモントン、カナダ. 
![{\displaystyle \mathbb {T} ^{\infty }=[0,\infty ]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a51f5260ac8b0db3fffa43d12541e3b27a993693)
![{\displaystyle Q=\{(s,t_{e})|s\in S,t_{e}\in (\mathbb {T} \cap [0,ta(s)])\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/858859e0349f18cc0370c8a7d8be94737def6d21)
![{\displaystyle \Delta \subseteq Q\times \Omega _{Z,[t_{l},t_{u}]}\times Q}](https://wikimedia.org/api/rest_v1/media/math/render/svg/dd4aa1a8249e4c2515cbf417a658ae967a8c0215)
![{\displaystyle \omega \in \Omega _{Z,[t_{l},t_{u}]}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b7cfe075628a7736029e86ae72332f6f2c53bfb9)
![{\displaystyle L({\mathcal {G}},t)=\{\omega \in \Omega _{Z,[0,t]}:\exists (q_{0},\omega ,q)\in \Delta ,q_{0}\in Q_{0},q\in Q_{A}\}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/208d64904cee9a5882695934e19baef37159d226)
![{\displaystyle \omega \in \Omega _{Z,[0,t]}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/bfb0d5bc3fdd4876f2b1031c6b0eec316c497056)
![{\displaystyle L({\mathcal {G}},\infty )=\{\omega \in {\underset {t\rightarrow \infty }{\lim }}\Omega _{Z,[0,t]}:\exists \{q:(q_{0},\omega ,q)\in \Delta ,q_{0}\in Q_{0}\}\subseteq Q_{A}\}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1074fd4431b43b11336aeefc545b6e32ef8c9ad6)
![{\displaystyle \omega \in {\underset {t\rightarrow \infty }{\lim }}\Omega _{Z,[0,t]}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e3d49a62bff81d741b329204e536d50753433377)
![{\displaystyle \omega =\epsilon _{[t,t+dt]}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d4a559c0043781d00b72cf937c03976416a4dee4)
![{\displaystyle Q=\{(s,t_{s},t_{e})|s\in S,t_{s}\in \mathbb {T} ^{\infty },t_{e}\in (\mathbb {T} \cap [0,t_{s}])\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/293c6673e551e1e86d4493f7a1767a51f9ba9b1c)
![{\displaystyle Q_{i}=\{(s_{i},t_{ei})|s_{i}\in S_{i},t_{ei}\in (\mathbb {T} \cap [0,ta_{i}(s_{i})])\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c6a6f8c85bb715c8b250f30967fe09fbf82d0d5c)
![{\displaystyle s=(\ldots ,(s_{i},t_{ei}),\ldots ),t_{e}\in (\mathbb {T} \cap [0,ta(s)])}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6c049da6c3f9c17d6e0aef6b251e3b7a65d521d5)
![{\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}])\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9fdb5fe7dc823e5425f13932d033e82160968853)
![{\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}])}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2fa258ccd8a79cfdad11355abf75f35266a1e280)
![{\displaystyle t_{s}\in [0,\infty ]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/79271fd0ef3aab6c30848858b171090c99378c3f)
![{\displaystyle t_{n}\in [0,\infty ]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/98eadf6dc07d60ffb950a9b2a0a54afc343cc243)
![{\displaystyle t_{r}\in [0,\infty ]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/bf4b90f5ae8de36600a0cbabf1be373b62359324)
![{\displaystyle \tau :S\rightarrow \mathbb {Q} _{[0,\infty ]}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8c9e66e62a84adce3a3c0a99f557529468691304)
![{\displaystyle \mathbb {Q} _{[0,\infty ]}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/292dcc3a0f5302dd4fa6259c528365d3bf3c3ca5)
![{\displaystyle t_{s}\in \mathbb {Q} _{[0,\infty ]}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4a3aa219ae7dc079e806e1d4f13ac4272bc132da)
![{\displaystyle t_{e}\in [0,\infty ]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3d46262368ccb11501662c0a285a41de8fdf29e2)
![{\displaystyle t_{e}\in (\mathbb {T} \cap [0,t_{s}])}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1cd77b9cab095cd0e9c761832412cf805e487aee)
