開発者

DEVS は、離散イベント システム仕様の略で、状態遷移表で記述できる離散イベント システム、微分方程式で記述できる連続状態システム、連続状態と離散イベントのハイブリッド システムなど、一般的なシステムをモデル化および解析するためのモジュール式の階層型形式です。DEVS は、時間制限のあるイベント システムです。

歴史

DEVSは、離散事象システム（DES）のモデリングと解析のための形式論である。DEVS形式論は、アリゾナ大学名誉教授のバーナード・P・ザイグラーによって考案された。DEVSは、ザイグラーがミシガン大学の准教授であった1976年^{[ 1 ]}に、ザイグラーの最初の著書『モデリングとシミュレーションの理論』で一般に公開された。DEVSは、出力が現在の状態のみによって決定され（入力に直接依存しない）、有限状態オートマトンである ムーアマシン形式論^{[ 2 ]}の拡張と見なすことができる。この拡張は、

1. 各状態に寿命を関連付ける^{[ 1 ]}
2. 階層的な概念にカップリングと呼ばれる操作を与えること^{[ 3 ]}

各状態の寿命は実数（より正確には非負の実数）または無限大であるため、離散時間システム、シーケンシャルマシン、およびムーアマシンとは区別されます。これらのシステムでは、時間はティックタイムに非負の整数を乗じて決定されます。さらに、寿命は確率変数となる可能性があり、例えば、ある状態の寿命は指数分布または一様分布になる可能性があります。DEVSの状態遷移関数と出力関数も確率的になる可能性があります。

Zeigler は 1984 年に 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 ]}この記事では、非負の実数の集合である時間ベースと、非負の実数に無限大を加えた集合である拡張時間ベースを使用する。 ${\displaystyle \mathbb {T} =[0,\infty )}$ ${\displaystyle \mathbb {T} ^{\infty }=[0,\infty ]}$

アトミック開発者

アトミックDEVSモデルは7つのタプルとして定義される

${\displaystyle M=<X,Y,S,s_{0},ta,\delta _{ext},\delta _{int},\lambda >}$

どこ

• ${\displaystyle X}$ 入力イベントの集合です。
• ${\displaystyle Y}$ 出力イベントのセットです。
• ${\displaystyle S}$ 連続した状態の集合（または部分的な状態の集合とも呼ばれる）である。
• ${\displaystyle s_{0}\in S}$ 初期状態です。
• ${\displaystyle ta:S\rightarrow \mathbb {T} ^{\infty}}$ 状態の寿命を決定するために使用される時間前進関数です。
• ${\displaystyle \delta _{ext}:Q\times X\rightarrow S}$ は入力イベントがシステムの状態をどのように変化させるかを定義する外部遷移関数であり、は合計状態の集合であり、は最後のイベントからの経過時間である。^{[ 6 ]}${\displaystyle Q=\{(s,t_{e})|s\in S,t_{e}\in (\mathbb {T} \cap [0,ta(s)])\}}$ ${\displaystyle t_{e}}$
• ${\displaystyle \delta _{int}:S\rightarrow S}$ システムの状態が内部的にどのように変化するかを定義する内部遷移関数です（経過時間が状態の有効期間に達したとき）。
• ${\displaystyle \lambda :S\rightarrow Y^{\phi }}$ は出力関数であり、はサイレントイベントまたは観測されないイベントです。この関数は、システムの状態がどのように出力イベントを生成するか（経過時間が状態の存続時間に達したとき）を定義します。${\displaystyle Y^{\phi }=Y\cup \{\phi \}}$ ${\displaystyle \phi \not \in Y}$

卓球選手のための原子DEVSモデル

図1のプレイヤーAの原子DEVSモデルは、プレイヤー=が与えられ、${\displaystyle <X,Y,S,s_{0},ta,\delta _{ext},\delta _{int},\lambda >}$

${\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)と同時に、は で定義される出力を生成します。 ${\displaystyle M}$ ${\displaystyle s\in S}$ ${\displaystyle x\in X}$ ${\displaystyle M}$ ${\displaystyle t_{e}}$ ${\displaystyle s}$ ${\displaystyle ta(s)}$ ${\displaystyle M}$ ${\displaystyle y\in Y}$ ${\displaystyle \lambda (s)}$

与えられた原子DEVSモデルの正式な動作記述については、 「原子DEVSの動作」セクションを参照してください。与えられた原子DEVSモデルの動作を実装するためのコンピュータアルゴリズムについては、「原子DEVSのシミュレーションアルゴリズム」セクションを参照してください。

結合されたDEVS

結合DEVSは、どのサブコンポーネントがそれに属し、それらが互いにどのように接続されているかを定義します。結合DEVSモデルは、8つのタプルとして定義されます。

${\displaystyle N=<X,Y,D,\{M_{i}\},C_{xx},C_{yx},C_{yy},Select>}$

どこ

• ${\displaystyle X}$ 入力イベントの集合です。
• ${\displaystyle Y}$ 出力イベントのセットです。
• ${\displaystyle D}$ サブコンポーネントの名前セットです。
• ${\displaystyle \{M_{i}\}}$ サブコンポーネントのセットであり、各サブコンポーネントは、アトミック DEVS モデルまたは結合 DEVS モデルのいずれかになります。${\displaystyle i\in D,M_{i}}$
• ${\displaystyle C_{xx}\subseteq X\times \bigcup _{i\in D}X_{i}}$ 外部入力カップリングのセットです。
• ${\displaystyle C_{yx}\subseteq \bigcup _{i\in D}Y_{i}\times \bigcup _{i\in D}X_{i}}$ 内部カップリングの集合です。
• ${\displaystyle C_{yy}:\bigcup _{i\in D}Y_{i}\rightarrow Y^{\phi }}$ 外部出力結合関数です。
• ${\displaystyle Select:2^{D}\rightarrow D}$ 同時発生するイベントのセットからイベントを選択する方法を定義するタイブレーク関数です。

ピンポンゲームのための結合DEVSモデル

図 1 のピンポン ゲームは、結合された DEVS モデルとしてモデル化できます。ここで、; ; ;は上記のように記述されます。; ; ; そして。 ${\displaystyle N=<X,Y,D,\{M_{i}\},C_{xx},C_{yx},C_{yy},Select>}$ ${\displaystyle X=\{\}}$ ${\displaystyle Y=\{\}}$ ${\displaystyle D=\{A,B\}}$ ${\displaystyle M_{A}{\text{ and }}M_{B}}$ ${\displaystyle C_{xx}=\{\}}$ ${\displaystyle C_{yx}=\{(A.!send,B.?receive),(B.!send,A.?receive)\}}$ ${\displaystyle C_{yy}(A.!send)=\phi ,C_{yy}(B.!send)=\phi }$

簡単に言えば、原子DEVSクラスの振る舞いと同様に、結合DEVSモデルは、外部イベントが に入力されたとき、(1) コンポーネントの状態を変化させます。 (2) コンポーネントの1つが内部状態遷移を実行し、出力 を生成したとき。( 1) と (2) のどちらの場合も、トリガーイベントは結合集合と によって定義されるすべての影響に伝達されます。 ${\displaystyle N}$ ${\displaystyle x\in X}$ ${\displaystyle N}$ ${\displaystyle M_{i}}$ ${\displaystyle i\in D}$ ${\displaystyle y_{i}\in Y_{i}}$ ${\displaystyle C_{xx},C_{yx},}$ ${\displaystyle C_{yy}}$

結合DEVSの動作の正式な定義については、 「結合DEVSの動作」セクションを参照してください。特定の結合DEVSモードの動作を実装するためのコンピュータアルゴリズムについては、「結合DEVSのシミュレーションアルゴリズム」セクションを参照してください。

分析方法

離散事象システムのシミュレーション

DEVSモデルのシミュレーションアルゴリズムは、時間同期とメッセージ伝播という2つの問題を考慮しています。DEVSの時間同期は、すべてのモデルの現在時刻を同一に制御することです。しかし、効率的な実行のために、アルゴリズムは、イベントがスケジュールされた最も緊急性の高い時刻に現在時刻をジャンプさせ、その内部状態遷移と出力生成を実行します。メッセージ伝播は、結合DEVSモデルで定義された関連する結合に沿って、入力イベントまたは出力イベントのいずれかであるトリガーメッセージを送信することです。詳細については、「アトミックDEVSのシミュレーションアルゴリズム」および「結合DEVSのシミュレーションアルゴリズム」を参照してください。

連続状態システムのシミュレーション

連続セグメントを区分的定数セグメントとして抽象化する量子化手法を導入することにより、DEVS は微分代数方程式のネットワークで記述される連続状態システムの挙動をシミュレートできます。この研究は 1990 年代に Zeigler 氏によって開始されました。^{[ 7 ]}多くの特性は 2000 年代に Kofman 教授と Nutaro 博士によって明らかにされました。2006 年には、Continuous System Modelingの著者である Cellier 教授[ ^{8 ]}と 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）最小/最大処理時間境界は、2012年までにSP-DEVSで定量的な特性として決定可能である。

時間制限付きイベントシステム

一般システムは、 ^{( 1 )時間基準、 ( 2)許容される入力セグメント、(3)システム状態、( 4} )許容される入力セグメントを含む状態軌跡、(5)与えられた状態に対する出力を定義する観点から、Zeigler [16] [17]によって記述されている。電流セグメントとイベントセグメントに関連付けられた状態軌跡を定義するタイムドイベントシステムは、非決定論的な動作を可能にするために一般システムのクラスから生まれた。^{[ 18 ]} DEVSの動作はタイムドイベントシステムで記述できるため、 DEVSとRTDEVSはタイムドイベントシステムのサブクラスまたは同等のクラスである。

時間制限付きイベントシステムは構造である

${\displaystyle {\mathcal {G}}=<Z,Q,Q_{0},Q_{A},\Delta >}$

どこ

• ${\displaystyle \,Z}$ はイベントの集合です。
• ${\displaystyle \,Q}$ は状態の集合である。
• ${\displaystyle \,Q_{0}\subseteq Q}$ 初期状態の集合です。
• ${\displaystyle Q_{A}\subseteq Q}$ は受け入れ状態の集合である。
• ${\displaystyle \Delta \subseteq Q\times \Omega _{Z,[t_{l},t_{u}]}\times Q}$ は、イベントセグメントとともに状態が に変化する可能性があることを示す、における状態軌跡の集合です。2つの状態軌跡 と が連続している場合、かつ2つのイベント軌跡と が連続しているといいます。2つの状態軌跡と が連続している場合、が成立します。${\displaystyle (q,\omega ,q')\in \Delta }$ ${\displaystyle q\in Q}$ ${\displaystyle q'\in Q}$ ${\displaystyle \omega \in \Omega _{Z,[t_{l},t_{u}]}}$ ${\displaystyle (q_{1},\omega _{1},q_{2})}$ ${\displaystyle (q_{3},\omega _{2},q_{4})\in \Delta }$ ${\displaystyle q_{2}=q_{3}}$ ${\displaystyle \omega _{1}}$ ${\displaystyle \omega _{2}}$ ${\displaystyle (q,\omega _{1},p)}$ ${\displaystyle (p,\omega _{2},q')\in \Delta }$ ${\displaystyle (q,\omega _{1}\omega _{2},q')\in \Delta }$

時間制限付きイベントシステム が与えられたとき、その動作の集合は観測時間の長さに依存した言語と呼ばれる。を観測時間の長さとする。 の場合、の長さの観測言語は と表され、次のように定義される。${\displaystyle {\mathcal {G}}=<Z,Q,Q_{0},Q_{A},\Delta >}$ ${\displaystyle t}$ ${\displaystyle 0\leq t<\infty }$ ${\displaystyle t}$ ${\displaystyle {\mathcal {G}}}$ ${\displaystyle L({\mathcal {G}},t)}$

${\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}\}.}$

のイベントセグメントを の長さの振る舞いと呼ぶ。観測時間の長さを無限大に送ることで、の無限長の観測言語を定義する。これは で表され、次のように定義される。${\displaystyle \omega \in \Omega _{Z,[0,t]}}$ ${\displaystyle t}$ ${\displaystyle {\mathcal {G}}}$ ${\displaystyle \omega \in L({\mathcal {G}},t)}$ ${\displaystyle t}$ ${\displaystyle {\mathcal {G}}}$ ${\displaystyle L({\mathcal {G}},\infty )}$

${\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}\}.}$

の場合には、イベント セグメントをの無限長の動作と呼びます。 ${\displaystyle \omega \in {\underset {t\rightarrow \infty }{\lim }}\Omega _{Z,[0,t]}}$ ${\displaystyle {\mathcal {G}}}$ ${\displaystyle \omega \in L({\mathcal {G}},\infty )}$ ${\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モデルが 、${\displaystyle {\mathcal {M}}=<X,Y,S,s_{0},ta,\delta _{ext},\delta _{int},\lambda >}$

1. 外部状態遷移。${\displaystyle \delta _{ext}:Q\times X\rightarrow S}$
2. 全体の状態集合は、最後のイベントからの経過時間を表し、非負の実数の集合を表し、${\displaystyle Q=\{(s,t_{e})|s\in S,t_{e}\in (\mathbb {T} \cap [0,ta(s)])\}}$ ${\displaystyle t_{e}}$ ${\displaystyle \mathbb {T} =[0,\infty )}$

DEVSモデルは、時間制限のあるイベントシステムであり、${\displaystyle {\mathcal {M}}}$ ${\displaystyle {\mathcal {G}}=<Z,Q,Q_{0},Q_{A},\Delta >}$

• イベントセット。${\displaystyle Z=X\cup Y^{\phi }}$
• 状態は に設定されます。${\displaystyle Q=Q_{A}\cup Q_{N}}$ ${\displaystyle Q_{N}=\{{\bar {s}}\not \in S\}}$
• 初期状態の集合。${\displaystyle \,Q_{0}=\{(s_{0},0)\}}$
• 受け入れ状態の集合${\displaystyle Q_{A}={\mathcal {M}}.Q.}$
• 状態軌道の集合は、2つの異なるケース、すなわち とについて定義される。非受理状態 の場合、偶数セグメントとともに変化は起こらないので、${\displaystyle \Delta \subseteq Q\times \Omega _{Z,[t_{l},t_{u}]}\times Q}$ ${\displaystyle q\in Q_{N}}$ ${\displaystyle q\in Q_{A}}$ ${\displaystyle q\in Q_{N}}$ ${\displaystyle \omega \in \Omega _{Z,[t_{l},t_{u}]}}$ ${\displaystyle (q,\omega ,q)\in \Delta .}$

時刻とイベント セグメントの合計状態は次のとおりです。 ${\displaystyle q=(s,t_{e})\in Q_{A}}$ ${\displaystyle t\in \mathbb {T} }$ ${\displaystyle \omega \in \Omega _{Z,[t_{l},t_{u}]}}$

単位イベントセグメントがヌルイベントセグメントである 場合、すなわち${\displaystyle \omega }$ ${\displaystyle \omega =\epsilon _{[t,t+dt]}}$

${\displaystyle \,(q,\omega ,(s,t_{e}+dt))\in \Delta .}$

ユニットイベントセグメントが 入力イベントである時間指定イベントである場合、${\displaystyle \omega }$ ${\displaystyle \omega =(x,t)}$ ${\displaystyle x\in X}$

${\displaystyle (q,\omega ,(\delta _{ext}(q,x),0))\in \Delta .}$

単位イベントセグメントが時間指定イベントであり、イベントが出力イベントまたは観測不可能なイベントである場合、${\displaystyle \omega }$ ${\displaystyle \omega =(y,t)}$ ${\displaystyle y\in Y^{\phi }}$

${\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モデルが 、${\displaystyle {\mathcal {M}}=<X,Y,S,s_{0},ta,\delta _{ext},\delta _{int},\lambda >}$

1. 全体の状態集合。ここで は状態の寿命、は最終更新からの経過時間、 は非負の実数と無限大の集合を表す。${\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}])\}}$ ${\displaystyle t_{s}}$ ${\displaystyle s}$ ${\displaystyle t_{e}}$ ${\displaystyle t_{s}}$ ${\displaystyle \mathbb {T} ^{\infty }=[0,\infty )\cup \{\infty \}}$
2. 外部状態遷移は です。${\displaystyle \delta _{ext}:Q\times X\rightarrow S\times \{0,1\}}$

DEVSは時間制限のあるイベントシステムで、${\displaystyle Q={\mathcal {D}}}$ ${\displaystyle {\mathcal {G}}=<Z,Q,Q_{0},Q_{A},\Delta >}$

• イベントセット。${\displaystyle Z=X\cup Y^{\phi }}$
• 状態は に設定されます。${\displaystyle Q=Q_{A}\cup Q_{N}}$ ${\displaystyle Q_{N}=\{{\bar {s}}\not \in S\}}$
• 初期状態の集合。${\displaystyle \,Q_{0}=\{(s_{0},ta(s_{0}),0)\}}$
• 受け入れ状態のセット。${\displaystyle Q_{A}={\mathcal {M}}.Q}$
• 状態軌道の集合は、とという2つのケースに依存します。非受理状態の場合、どのセグメントにも変化はないので、${\displaystyle \Delta \subseteq Q\times \Omega _{Z,[t_{l},t_{u}]}\times Q}$ ${\displaystyle q\in Q_{N}}$ ${\displaystyle q\in Q_{A}}$ ${\displaystyle q\in Q_{N}}$ ${\displaystyle \omega \in \Omega _{Z,[t_{l},t_{u}]}}$ ${\displaystyle (q,\omega ,q)\in \Delta .}$

時刻とイベント セグメントの合計状態は次のとおりです。 ${\displaystyle q=(s,t_{s},t_{e})\in Q_{A}}$ ${\displaystyle t\in \mathbb {T} }$ ${\displaystyle \omega \in \Omega _{Z,[t_{l},t_{u}]}}$

単位イベントセグメントがヌルイベントセグメントである 場合、すなわち${\displaystyle \omega }$ ${\displaystyle \omega =\epsilon _{[t,t+dt]}}$

${\displaystyle (q,\omega ,(s,t_{s},t_{e}+dt))\in \Delta .}$

ユニットイベントセグメントが 入力イベントである時間指定イベントである場合、${\displaystyle \omega }$ ${\displaystyle \omega =(x,t)}$ ${\displaystyle x\in X}$

${\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 }$ ${\displaystyle \omega =(y,t)}$ ${\displaystyle y\in Y^{\phi }}$

${\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 ]}によって導入され、全状態と${\displaystyle q=(s,t_{e})\in Q}$

${\displaystyle \,ta(s)=\sigma }$

ここで残り時間は^{[ 23 ] [ 22 ]}である。言い換えれば、部分状態の集合は実際には状態集合である。DEVSモデルが入力イベントを受信すると、view1は経過時間をゼロにリセットする。DEVSモデルが寿命制御の観点から無視する必要がある場合、モデル作成者は残り時間を更新する必要がある。${\displaystyle \sigma }$ ${\displaystyle S=\{(d,\sigma )|d\in S',\sigma \in \mathbb {T} ^{\infty }\}}$ ${\displaystyle S'}$ ${\displaystyle x\in X}$ ${\displaystyle t_{e}}$ ${\displaystyle x}$

${\displaystyle \,\sigma =\sigma -t_{e}}$

外部状態遷移関数はモデル作成者の責任です。 ${\displaystyle \delta _{ext}}$

の取り得る値の数は、DEVSモデルに入力される可能性のあるイベントの数と同じなので、無限です。したがって、状態の数も無限であり、これがview2が提案された理由です。 ${\displaystyle \sigma }$ ${\displaystyle s=(d,\sigma )\in S}$

DEVSモデルの有限頂点到達可能性グラフを気にしないのであれば、view1は、DEVSモデルに入力イベントが到着するたびに経過時間を扱うという単純さという利点があります。しかし、DEVSのモデラーは上記のように処理する方法を知っておく必要があるという欠点があります。これは、それ自体では明示的に説明されていませんが、で説明されています。 ${\displaystyle t_{e}=0}$ ${\displaystyle \sigma }$ ${\displaystyle \delta _{ext}}$ ${\displaystyle \Delta }$

view2の特徴

View2はHwangとZeiglerによって導入された^{[ 24 ] [ 25 ]。}これは、合計状態が与えられた場合、残り時間は次のように計算される。${\displaystyle q=(s,t_{s},t_{e})\in Q}$ ${\displaystyle \sigma }$

${\displaystyle \,\sigma =t_{s}-t_{e}.}$

DEVSモデルが入力イベント を受信すると、view2は の場合にのみ経過時間をゼロにリセットします。DEVSモデルが寿命制御の観点から を無視する必要がある場合、モデラーは を使用できます。 ${\displaystyle x\in X}$ ${\displaystyle t_{e}}$ ${\displaystyle \delta _{ext}(q,x)=(s',1)}$ ${\displaystyle x}$ ${\displaystyle \delta _{ext}(q,x)=(s',0)}$

ビュー1とは異なり、残り時間は本質的にの要素ではないため、状態の数、つまり状態数が有限であれば、有限頂点（およびエッジ）の状態遷移図を描くことができます。^{[ 24 ] [ 25 ]}その結果、SP-DEVSやFD-DEVSなどのDEVSクラスのネットワークの振る舞いを、到達可能性グラフと呼ばれる有限頂点グラフとして抽象化することができます。^{[ 24 ] [ 25 ]}${\displaystyle \sigma }$ ${\displaystyle S}$ ${\displaystyle |S|}$

結合されたDEVS

DEVSは結合に関して閉じている。^{[ 3 ] [ 26 ]}言い換えれば、結合DEVSモデルが与えられた場合、その動作は原子DEVSモデルとして記述される。与えられた結合DEVSに対して、同等の原子DEVSが与えられれば、その動作は時間イベントシステムに基づく原子DEVSの挙動を参照することができる。 ${\displaystyle N}$ ${\displaystyle M}$ ${\displaystyle N}$ ${\displaystyle M}$ ${\displaystyle M}$

アトミック DEVS の動作と同様に、結合 DEVS クラスの動作は、全体の状態セットの定義とその処理に応じて次のように説明されます。

ビュー1: 合計状態 = 状態 * 経過時間

結合DEVSモデルが与えられた場合、その動作は原子DEVSモデルとして記述される。${\displaystyle N=<X,Y,D,\{M_{i}\},C_{xx},C_{yx},C_{yy},Select>}$ ${\displaystyle M=<X,Y,S,s_{0},ta,\delta _{ext},\delta _{int},\lambda >}$

どこ

• ${\displaystyle X}$ およびは、それぞれ入力イベント セットと出力イベント セットです。${\displaystyle Y}$
• ${\displaystyle S={\underset {i\in D}{\times }}Q_{i}}$ は部分状態セットであり、はコンポーネントの全体状態セットです( DEVS の動作のビュー 1を参照)。は非負の実数セットです。${\displaystyle Q_{i}=\{(s_{i},t_{ei})|s_{i}\in S_{i},t_{ei}\in (\mathbb {T} \cap [0,ta_{i}(s_{i})])\}}$ ${\displaystyle i\in D}$ ${\displaystyle \mathbb {T} =[0,\infty )}$
• ${\displaystyle s_{0}={\underset {i\in D}{\times }}q_{0i}}$ は初期状態セットであり、はコンポーネントの合計初期状態です。${\displaystyle q_{0i}=(s_{0i},0)}$ ${\displaystyle i\in D}$
• ${\displaystyle ta:S\rightarrow \mathbb {T} ^{\infty }}$ は時間進行関数であり、非負の実数と無限大の集合である。${\displaystyle \mathbb {T} ^{\infty }=[0,\infty ]}$ ${\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}$ は外部状態関数である。全体の状態が与えられ、入力イベントが与えられた場合、次の状態は次のように与えられる。${\displaystyle q=(s,t_{e})}$ ${\displaystyle s=(\ldots ,(s_{i},t_{ei}),\ldots ),t_{e}\in (\mathbb {T} \cap [0,ta(s)])}$ ${\displaystyle x\in X}$
  ${\displaystyle \delta _{ext}(q,x)=s'=(\ldots ,(s_{i}',t_{ei}'),\ldots )}$

どこ

${\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}}}$

部分状態 が与えられたとき、 は切迫したコンポーネントの集合を表すものとする。内部状態遷移と出力イベントをトリガーする発火コンポーネントは、次のように決定される。${\displaystyle s=(\ldots ,(s_{i},t_{ei}),\ldots )\in S}$ ${\displaystyle IMM(s)=\{i\in D|ta_{i}(s_{i})=ta(s)\}}$ ${\displaystyle i^{*}\in D}$

${\displaystyle i^{*}=Select(IMM(s)).}$

• ${\displaystyle \delta _{int}:S\rightarrow S}$ は内部状態関数である。部分状態 が与えられた場合、次の状態は次のように与えられる。${\displaystyle s=(\ldots ,(s_{i},t_{ei}),\ldots )}$
  ${\displaystyle \delta _{int}(s)=s'=(\ldots ,(s_{i}',t_{ei}'),\ldots )}$

どこ

${\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}}}$

• ${\displaystyle \lambda :S\rightarrow Y^{\phi }}$ は出力関数である。部分状態が与えられると、${\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}}}$

ビュー2: 合計状態 = 状態 * 寿命 * 経過時間

結合DEVSモデルが与えられた場合、その動作は原子DEVSモデルとして記述される。${\displaystyle N=<X,Y,D,\{M_{i}\},C_{xx},C_{yx},C_{yy},Select>}$ ${\displaystyle M=<X,Y,S,s_{0},ta,\delta _{ext},\delta _{int},\lambda >}$

どこ

• ${\displaystyle X}$ およびは、それぞれ入力イベント セットと出力イベント セットです。${\displaystyle Y}$
• ${\displaystyle S={\underset {i\in D}{\times }}Q_{i}}$ は部分的な状態セットで、はコンポーネントの全体の状態セットです( DEVS セクションの動作のビュー 2を参照)。${\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}])\}}$ ${\displaystyle i\in D}$
• ${\displaystyle s_{0}={\underset {i\in D}{\times }}q_{0i}}$ は初期状態セットであり、はコンポーネントの合計初期状態です。${\displaystyle q_{0i}=(s_{0i},ta_{i}(s_{0i}),0)}$ ${\displaystyle i\in D}$
• ${\displaystyle ta:S\rightarrow \mathbb {T} ^{\infty }}$ は時間進行関数である。${\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\}}$ は外部状態関数である。全体の状態が与えられ、入力イベントが与えられた場合、次の状態は次のように与えられる。${\displaystyle q=(s,t_{s},t_{e})}$ ${\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}])}$ ${\displaystyle x\in X}$
  ${\displaystyle \delta _{ext}(q,x)=((\ldots ,(s_{i}',t_{si}',t_{ei}'),\ldots ),b)}$

どこ

${\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}}}$

そして

${\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}}}$

部分状態 が与えられたとき、 は切迫したコンポーネントの集合を表すものとする。内部状態遷移と出力イベントをトリガーする発火コンポーネントは、次のように決定される。${\displaystyle s=(\ldots ,(s_{i},t_{si},t_{ei}),\ldots )\in S}$ ${\displaystyle IMM(s)=\{i\in D|t_{si}-t_{ei}=ta(s)\}}$ ${\displaystyle i^{*}\in D}$

${\displaystyle i^{*}=Select(IMM(s)).}$

• ${\displaystyle \delta _{int}:S\rightarrow S}$ は内部状態関数である。部分状態 が与えられた場合、次の状態は次のように与えられる。${\displaystyle s=(\ldots ,(s_{i},t_{si},t_{ei}),\ldots )}$
  ${\displaystyle \delta _{int}(s)=s'=(\ldots ,(s_{i}',t_{si}',t_{ei}'),\ldots )}$

どこ

${\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}}}$

• ${\displaystyle \lambda :S\rightarrow Y^{\phi }}$ は出力関数である。部分状態が与えられると、${\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}}}$

時間の経過

空でないサブコンポーネントを持つ結合 DEVS モデル、つまり、経過時間をトレースするクロックの数は倍数であるため、モデルの時間経過が顕著になります。 ${\displaystyle |D|>0}$

ビュー1

全体の状態が与えられ、${\displaystyle q=(s,t_{e})\in Q}$ ${\displaystyle s=(\ldots ,(s_{i},t_{ei}),\ldots )}$

単位イベントセグメントがヌルイベントセグメントである 場合、すなわち、時間制限イベントシステムにおける状態軌跡は、${\displaystyle \omega }$ ${\displaystyle \omega =\epsilon _{[t,t+dt]}}$

${\displaystyle \Delta (q,\omega )=((\ldots ,(s_{i},t_{ei}+dt),\ldots ),t_{e}+dt).}$

ビュー2の場合

全体の状態が与えられ、${\displaystyle q=(s,t_{s},t_{e})\in Q}$ ${\displaystyle s=(\ldots ,(s_{i},t_{si},t_{ei}),\ldots )}$

単位イベントセグメントがヌルイベントセグメントである 場合、すなわち、時間制限イベントシステムにおける状態軌跡は、${\displaystyle \omega }$ ${\displaystyle \omega =\epsilon _{[t,t+dt]}}$

${\displaystyle \Delta (q,\omega )=((\ldots ,(s_{i},t_{si},t_{ei}+dt),\ldots ),t_{s},t_{e}+dt).}$

シミュレーションアルゴリズム

アトミック開発者

原子DEVSモデル が与えられた場合、シミュレーションアルゴリズムは、モデルの正当な動作、すなわち不正な状態に到達しない軌跡を生成する手法である。（DEVSの動作を参照）。Zeiglerは、寿命 と経過時間に関連する時間変数を扱うアルゴリズムを、前回のイベント時間、、次回のイベント時間という2つの時間変数を導入し、以下の関係式で表すことにより初めて導入した。^{[ 3 ]}${\displaystyle t_{s}\in [0,\infty ]}$ ${\displaystyle t_{e}\in [0,\infty )}$ ${\displaystyle t_{l}\in [0,\infty )}$ ${\displaystyle t_{n}\in [0,\infty ]}$

${\displaystyle \,t_{e}=t-t_{l}}$

そして

${\displaystyle \,t_{s}=t_{n}-t_{l}}$

ここで、 は現在時刻を表します。そして残り時間 は、${\displaystyle t\in [0,\infty )}$

${\displaystyle \,t_{r}=t_{s}-t_{e}}$

は次のように計算される。

${\displaystyle \,t_{r}=t_{n}-t}$

、 どうやら。 ${\displaystyle t_{r}\in [0,\infty ]}$

特定の原子 DEVS モデルの動作は、全体の状態と外部遷移関数に応じて 2 つの異なるビューで定義できるため ( DEVS の動作セクションを参照)、シミュレーション アルゴリズムも以下のように 2 つの異なるビューで導入されます。

共通部品

全体の状態の 2 つの異なるビューに関係なく、初期化および内部遷移ケースのアルゴリズムは一般的に以下のように定義されます。

DEVSシミュレータ 変数: 親 // 親コーディネーター ${\displaystyle t_{l}}$ // 最後のイベントの時刻 // 次のイベントの時刻 // 関連するAtomic DEVSモデル${\displaystyle t_{n}}$ ${\displaystyle A=(X,Y,S,ta,\delta _{ext},\delta _{int},\lambda )}$  init-message を受信したとき(Time ) star-message を受信したとき(Time )${\displaystyle t}$ ${\displaystyle t_{l}\leftarrow t;}$ ${\displaystyle t_{n}\leftarrow t_{l}+ta(s);}$ ${\displaystyle t}$  もしそうなら${\displaystyle t\neq t_{n}}$  エラー: 同期が不正です。 ${\displaystyle y\leftarrow \lambda (s);}$  y-message( ) を親に送信します。 ${\displaystyle y,t}$ ${\displaystyle s\leftarrow \delta _{int}(s)}$ ${\displaystyle t_{l}\leftarrow t;}$ ${\displaystyle t_{n}\leftarrow t_{l}+ta(s);}$ 

ビュー1: 合計状態 = 状態 * 経過時間

アトミック DEVS の動作セクションで説明したように、DEVS が入力イベントを受信すると、最後のイベント時間である の呼び出し権が現在の時間 によって設定され、 のため経過時間は0 になります。 ${\displaystyle \delta _{ext}}$ ${\displaystyle t_{l}}$ ${\displaystyle t}$ ${\displaystyle t_{e}}$ ${\displaystyle t_{e}=t-t_{l}}$

x-message( , Time )を受信するとき${\displaystyle x\in X}$ ${\displaystyle t}$  かつ== false の場合${\displaystyle (t_{l}\leq t}$ ${\displaystyle t\leq t_{n})}$  エラー: 同期が不正です。 ${\displaystyle s\leftarrow \delta _{ext}(s,t-t_{l},x)}$ ${\displaystyle t_{l}\leftarrow t;}$ ${\displaystyle t_{n}\leftarrow t_{l}+ta(s);}$ 

視点2: 総状態数 = 状態数 * 寿命 * 経過時間

アトミック DEVS の動作セクションで説明されているように、による戻り値、最後のイベント時間、および次のイベント時間に応じて、経過時間、および寿命が更新される ( の場合) か、または保持される ( の場合) ことに注意してください。 ${\displaystyle b}$ ${\displaystyle \delta _{ext}}$ ${\displaystyle t_{l}}$ ${\displaystyle t_{n}}$ ${\displaystyle t_{e}}$ ${\displaystyle t_{n}}$ ${\displaystyle b=1}$ ${\displaystyle b=0}$

x-message( , Time )を受信するとき${\displaystyle x\in X}$ ${\displaystyle t}$  かつ== false の場合${\displaystyle (t_{l}\leq t}$ ${\displaystyle t\leq t_{n})}$  エラー: 同期が不正です。 ${\displaystyle (s,b)\leftarrow \delta _{ext}(s,t-t_{l},x)}$  もしそうなら ${\displaystyle b=1}$ ${\displaystyle t_{l}\leftarrow t;}$ ${\displaystyle t_{n}\leftarrow t_{l}+ta(s);}$ 

結合されたDEVS

結合DEVSモデルが与えられた場合、シミュレーションアルゴリズムはモデルの合法的な動作、つまり不正な状態に到達しない軌跡のセットを生成する方法です。（結合DEVSモデルの動作を参照）。Zeiglerは当初、寿命 と経過時間に関連する時間変数を処理するアルゴリズムを、最後のイベント時間、、および次のイベント時間という2つの時間変数を導入し、次の関係を導入しました。^{[ 3 ]}${\displaystyle t_{s}\in [0,\infty ]}$ ${\displaystyle t_{e}\in [0,\infty )}$ ${\displaystyle t_{l}\in [0,\infty )}$ ${\displaystyle t_{n}\in [0,\infty ]}$

${\displaystyle \,t_{e}=t-t_{l}}$

そして

${\displaystyle \,t_{s}=t_{n}-t_{l}}$

ここで、 は現在時刻を表します。そして残り時間 は、${\displaystyle t\in [0,\infty )}$

${\displaystyle \,t_{r}=t_{s}-t_{e}}$

は次のように計算される。

${\displaystyle \,t_{r}=t_{n}-t,}$

どうやら。これらの関係に基づいて、特定の結合されたDEVSの動作をシミュレートするアルゴリズムは次のように記述されます。 ${\displaystyle t_{r}\in [0,\infty ]}$

アルゴリズムDEVS コーディネーター 変数: 親 // 親コーディネーター ${\displaystyle t_{l}}$ : // 最後のイベントの時間 : // 次のイベントの時間 // 関連する結合DEVSモデル${\displaystyle t_{n}}$ ${\displaystyle N=(X,Y,D,\{M_{i}\},C_{xx},C_{yx},C_{yy},Select)}$ それぞれの init-message(Time t ) を受信すると、子に init-message( t )を送信します。 ${\displaystyle i\in D}$ ${\displaystyle i}$ ${\displaystyle t_{l}\leftarrow \max\{t_{li}:i\in D\}}$ ${\displaystyle t_{n}\leftarrow \min\{t_{ni}:i\in D\}}$  スターメッセージを受信したとき(時刻t ) ${\displaystyle t\neq t_{n}}$  エラー: 同期が不正です。 ${\displaystyle i^{*}\leftarrow Select(\{i\in D:t_{ni}=t_{n}\});}$  スターメッセージ( t )を; ;に送信します。${\displaystyle i^{*}}$ ${\displaystyle t_{l}\leftarrow \max\{t_{li}:i\in D\}}$ ${\displaystyle t_{n}\leftarrow \min\{t_{ni}:i\in D\}}$  x-message( , Time t ) を受信したとき、 and == falseの場合${\displaystyle x\in X}$ ${\displaystyle (t_{l}\leq t}$ ${\displaystyle t\leq t_{n})}$  エラー: 同期が不正です。 それぞれに対して、 x -message( , t ) を子に送信します。 ${\displaystyle (x,x_{i})\in C_{xx}}$ ${\displaystyle x_{i}}$ ${\displaystyle i}$ ${\displaystyle t_{l}\leftarrow \max\{t_{li}:i\in D\}}$ ${\displaystyle t_{n}\leftarrow \min\{t_{ni}:i\in D\}}$ それぞれに対して y-message( , Time t ) を受信すると、子に x-message( , t ) を送信し、そうでない場合は親に y-message( , t ) を送信します。 ; ; ${\displaystyle y_{i}\in Y_{i}}$ ${\displaystyle (y_{i},x_{i})\in C_{yx}}$ ${\displaystyle x_{i}}$ ${\displaystyle i}$ ${\displaystyle C_{yy}(y_{i})\neq \phi }$ ${\displaystyle C_{yy}(y_{i})}$ ${\displaystyle t_{l}\leftarrow \max\{t_{li}:i\in 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つの制約があります。

1. 事象集合と状態集合の有限性、
2. 状態の寿命は有理数または無限大でスケジュールすることができ、
3. 内部スケジュールは入力イベントによって保存または更新されます。

3つ目の制約は、入力イベントによってスケジュールが常に保存されるSP-DEVSからの緩和とも言える。この緩和によりOPNA問題は解消されるが、SP-DEVSネットワークの経過時間を抽象化するために使用できるタイムライン抽象化がFD-DEVSネットワークではもはや役に立たないという制約も存在する^{[ 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

正式な定義

$${\displaystyle M=<X,Y,S,s_{0},\tau ,\delta _{x},\delta _{y}>}$$

どこ

• ${\displaystyle X}$ 入力イベントの有限集合です。
• ${\displaystyle Y}$ 出力イベントの有限集合です。
• ${\displaystyle S}$ は有限の状態集合である。
• ${\displaystyle s_{0}\in S}$ 初期状態です。
• ${\displaystyle \tau :S\rightarrow \mathbb {Q} _{[0,\infty ]}}$ は、非負の有理数と無限大の集合である状態の寿命を定義する時間前進関数です。${\displaystyle \mathbb {Q} _{[0,\infty ]}}$
• ${\displaystyle \delta _{x}:S\times X\rightarrow S\times \{0,1\}}$ は、入力イベントがシステムの状態とスケジュールをどのように変化させるかを定義する外部遷移関数である。状態の内部スケジュールは、の場合に によって更新され、それ以外の場合（すなわち の場合）はスケジュールが維持される。^{[ 29 ]}${\displaystyle s\in S}$ ${\displaystyle \tau (s')}$ ${\displaystyle \delta _{x}(s)=(s',1)}$ ${\displaystyle \delta _{x}(s)=(s',0)}$
• ${\displaystyle \delta _{y}:S\rightarrow Y^{\phi }\times S}$ は出力および内部遷移関数であり、 はサイレントイベントを表す。出力および内部遷移関数は、状態がどのように出力イベントを生成するか、同時に状態が内部的にどのように変化するかを定義する。^{[ 30 ]}${\displaystyle Y^{\phi }=Y\cup \{\phi \}}$ ${\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)。 ${\displaystyle M=<X,Y,S,s_{0},\tau ,\delta _{x},\delta _{y}>}$ ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle S}$ ${\displaystyle s_{0}}$ ${\displaystyle \tau }$ ${\displaystyle \tau }$ ${\displaystyle \infty }$ ${\displaystyle \delta _{x}}$ ${\displaystyle \delta _{x}}$ ${\displaystyle \delta _{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) です。 ${\displaystyle M=<X,Y,S,s_{0},\tau ,\delta _{x},\delta _{y}>}$ ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle S}$ ${\displaystyle s_{0}}$ ${\displaystyle \tau }$ ${\displaystyle \tau }$ ${\displaystyle \infty }$ ${\displaystyle \delta _{x}}$ ${\displaystyle \delta _{x}}$ ${\displaystyle \delta _{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); ${\displaystyle M=<X,Y,S,s_{0},\tau ,\delta _{x},\delta _{y}>}$ ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle S}$ ${\displaystyle s_{0}}$ ${\displaystyle \tau }$ ${\displaystyle \tau }$ ${\displaystyle \tau }$ ${\displaystyle \tau }$ ${\displaystyle \tau }$ ${\displaystyle \tau }$ ${\displaystyle \tau }$ ${\displaystyle \delta _{x}}$ ${\displaystyle \delta _{x}}$ ${\displaystyle \neq }$ ${\displaystyle \delta _{y}}$ ${\displaystyle \delta _{y}}$ ${\displaystyle \delta _{y}}$ ${\displaystyle \phi }$ ${\displaystyle \delta _{y}}$ ${\displaystyle \delta _{y}}$ ${\displaystyle \delta _{y}}$ ${\displaystyle \delta _{y}}$

FD-DEVSモデルの動作

図3. イベントセグメントとプレイヤーAの状態軌跡

FD-DEVSはDEVSのサブクラスである

FD-DEVSモデルは、DEVSが ${\displaystyle M=<X,Y,S,s_{0},\tau ,\delta _{x},\delta _{y}>}$ ${\displaystyle {\mathcal {M}}=<X,Y,S',s_{0}',ta,\delta _{ext},\delta _{int},\lambda >}$

• ${\displaystyle X,Y}$ のは の と同じです。${\displaystyle {\mathcal {M}}}$ ${\displaystyle M}$
• ${\displaystyle S'=\{(s,t_{s}):s\in S,t_{s}\in \mathbb {T} ^{\infty }\}}$
• ${\displaystyle s_{0}'=(s_{0},\tau (s_{0}))}$
• 状態が与えられた場合、${\displaystyle (s,t_{s})\in S'}$ ${\displaystyle ta(s,t_{s})=t_{s}.}$
• 状態と入力イベントが与えられると、${\displaystyle (s,t_{s})\in S'}$ ${\displaystyle x\in X}$

${\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}}}$

• 状態が与えられた場合、${\displaystyle (s,t_{s})\in S'}$ ${\displaystyle \delta _{int}(s,t_{s})=(s',\tau (s'))}$ ${\displaystyle \delta _{y}(s)=(y,s').}$
• 状態が与えられた場合、${\displaystyle (s,t_{s})\in S'}$ ${\displaystyle \lambda (s,t_{s})=y}$ ${\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」を行き来するこの循環的な状態遷移は永久に繰り返されます。 ${\displaystyle s,t_{s},t_{e}}$ ${\displaystyle t_{e}}$ ${\displaystyle t_{s}}$ ${\displaystyle 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)は全く変化しないことに注意してください。 ${\displaystyle s,t_{s},t_{e}}$ ${\displaystyle t_{e}}$ ${\displaystyle \delta _{x}}$

利点

図5. 2スロットトースターの到達可能性グラフ

タイムゾーン抽象化の適用性

有限数の状態とイベントとともに入力イベントによって保存または変更できる非負の有理値の寿命の特性は、経過時間の無限個の値をD. Dill教授によって導入された時間抽象化技術を使用して抽象化することにより、FD-DEVSネットワークの動作を等価な有限頂点到達可能性グラフとして抽象化できることを保証します。^{[ 28 ]}有限頂点到達可能性グラフ（RG）を生成するアルゴリズムはZeiglerによって導入されました。^{[ 25 ] [ 31 ]}

到達可能性グラフ

図5は、図2に示した2スロットトースターの到達可能性グラフを示している。到達可能性グラフでは、各頂点は独自の離散状態と時間帯を持ち、これらは範囲とである。例えば、図5のノード(6)の場合、離散状態情報は((E, ),(T,40))であり、時間帯はである。各有向アーチは、関連するイベントとリセットモデルの集合とともに、そのソース頂点がデスティネーション頂点に変化する様子を示している。例えば、遷移アーク(6)から(5)はpush1イベントによって引き起こされる。その時、アークの集合{1}は経過時間1（つまり、遷移(6)から(5)が起こると0にリセットされる）を示す。^{[ 25 ]}${\displaystyle t_{e1},t_{e2}}$ ${\displaystyle t_{e1}-t_{e2}}$ ${\displaystyle \infty }$ ${\displaystyle 0\leq t_{e1}\leq 40,0\leq t_{e2}\leq 40,-20\leq t_{e1}-t_{21}\leq 0}$ ${\displaystyle t_{e1}}$

安全性の決定可能性

定性的な特性として、FD-DEVSネットワークの安全性は、(1)与えられたネットワークのRGを生成し、(2)いくつかの悪い状態に到達可能かどうかを確認することによって決定できます。^{[ 24 ]}

生存の決定可能性

定性的な性質として、FD-DEVSネットワークの活性は、(1)与えられたネットワークのRGを生成すること、(2)RGから、頂点が強く連結された成分であるカーネル有向非巡回グラフ（KDAG）を生成すること、(3)KDAGの頂点に活性状態の集合を含む状態遷移サイクルが含まれているかどうかを確認することによって決定できる。^{[ 24 ]}

デメリット

非決定性を記述する表現力が弱い

FD-DEVS のすべての特性関数が決定論的であるという特徴は、非決定論的な振る舞いを持つシステムをモデル化する際、ある種の制約となる可能性があります。例えば、図1に示すピンポンゲームのプレイヤーが「送信」状態で確率的な寿命を持つ場合、FD-DEVS は非決定論的な振る舞いを効果的に捉えることができません。 ${\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つの制約が課されています。

1. 事象集合と状態集合の有限性、
2. 状態の寿命は有理数または無限大でスケジュールすることができ、
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つの要素から構成されるタプルです。$${\displaystyle M=<X,Y,S,s_{0},\tau ,\delta _{x},\delta _{y}>}$$

どこ

• ${\displaystyle X}$ 入力イベントの有限集合です。
• ${\displaystyle Y}$ 出力イベントの有限集合です。
• ${\displaystyle S}$ は有限の状態集合である。
• ${\displaystyle s_{0}\in S}$ 初期状態です。
• ${\displaystyle \tau :S\rightarrow \mathbb {Q} _{[0,\infty ]}}$ は、非負の有理数と無限大の集合である状態の寿命を定義する時間進行関数です。${\displaystyle \mathbb {Q} _{[0,\infty ]}}$
• ${\displaystyle \delta _{x}:S\times X\rightarrow S}$ 入力イベントがシステムの状態をどのように変化させるかを定義する外部遷移関数です。
• ${\displaystyle \delta _{y}:S\rightarrow Y^{\phi }\times S}$ は出力および内部遷移関数であり、 はサイレントイベントを表す。出力および内部遷移関数は、状態がどのように出力イベントを生成するか、同時に状態が内部的にどのように変化するかを定義する。^{[ 36 ]}${\displaystyle Y^{\phi }=Y\cup \{\phi \}}$ ${\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); ${\displaystyle M=<X,Y,S,s_{0},\tau ,\delta _{x},\delta _{y}>}$ ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle S}$ ${\displaystyle s_{0}}$ ${\displaystyle \tau }$ ${\displaystyle \tau }$ ${\displaystyle \tau }$ ${\displaystyle \tau }$ ${\displaystyle \tau }$ ${\displaystyle \tau }$ ${\displaystyle \tau }$ ${\displaystyle \delta _{x}}$ ${\displaystyle \delta _{x}}$ ${\displaystyle \neq }$ ${\displaystyle \delta _{y}}$ ${\displaystyle \delta _{y}}$ ${\displaystyle \delta _{y}}$ ${\displaystyle \phi }$ ${\displaystyle \delta _{y}}$ ${\displaystyle \delta _{y}}$ ${\displaystyle \delta _{y}}$ ${\displaystyle \delta _{y}}$

SP-DEVSモデルの動作

図3. SP-DEVSモデルのイベントセグメントとその状態軌跡

原子SP-DEVSのダイナミクスを捉えるには、時間に関連する2つの変数を導入する必要があります。1つは寿命、もう1つは最後のリセットからの経過時間です。は寿命を表します。寿命は連続的に増加するのではなく、離散イベントが発生したときに設定されます。 は経過時間を表します。経過時間は、リセットがない場合、時間の経過とともに連続的に増加します。 ${\displaystyle t_{s}\in \mathbb {Q} _{[0,\infty ]}}$ ${\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 で唯一の連続変数である経過時間の時間フローを示しています。 ${\displaystyle s\in S}$ ${\displaystyle (s,t_{s},t_{e})}$

SF-DEVSの興味深い特徴の1つは、外部イベント?pが発生したときに図3の時刻47に描かれているSP-DEVSの制約(3)のスケジュールが保存されることです。この瞬間、状態がGからGRに変化しても経過時間は変わらないため、線分は時刻47で途切れず、この例では30まで成長できます。入力イベントからのスケジュールのこの保存と、時間の進み方が非負の有理数に制限されているため(上記の制約(2)を参照)、SP-DEVSモデルでは、すべてののこぎりの高さは非負の有理数または無限大になります(図3の下部に示すように)。 ${\displaystyle t_{e}}$ ${\displaystyle t_{e}}$

SP-DEVSはDEVSのサブクラスである

SP-DEVSモデルは、DEVSにおいて ${\displaystyle M=<X,Y,S,s_{0},\tau ,\delta _{x},\delta _{y}>}$ ${\displaystyle {\mathcal {M}}=<X,Y,S',s_{0}',ta,\delta _{ext},\delta _{int},\lambda >}$

• ${\displaystyle X,Y}$ のは の と同じです。${\displaystyle {\mathcal {M}}}$ ${\displaystyle M}$
• ${\displaystyle S'=\{(s,t_{s}):s\in S,t_{s}\in \mathbb {T} ^{\infty }\}}$
• ${\displaystyle s_{0}'=(s_{0},\tau (s_{0}))}$
• 状態が与えられた場合、${\displaystyle (s,t_{s})\in S'}$ ${\displaystyle ta(s,t_{s})=t_{s}.}$
• 状態と入力イベントが与えられた場合${\displaystyle (s,t_{s})\in 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'.}$
• 状態が与えられた場合、${\displaystyle (s,t_{s})\in S'}$ ${\displaystyle \delta _{int}(s,t_{s})=(s',\tau (s')}$ ${\displaystyle \delta _{y}(s)=(y,s').}$
• 状態が与えられた場合、${\displaystyle (s,t_{s})\in S'}$ ${\displaystyle \lambda (s,t_{s})=y}$ ${\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 ]}

デメリット

• 表現力の低下：OPNA問題

の場合、 SP-DEVS モデルの全状態をパッシブにします。それ以外の場合は、アクティブにします。 ${\displaystyle (s,t_{s},t_{e})}$ ${\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関連記事

• イベントセグメント
• 時間制限付きイベントシステム
• パワーデブス

その他の形式主義

• オートマトン理論：状態遷移システムのための形式手法
• 有限状態機械: 有限のイベントと状態のセットを持つ状態遷移機械
• ペトリネット：状態と遷移関係のグラフィカルな表現
• マルコフ連鎖：未来が現在の状態によって決定される確率過程
• 仕様および記述言語: SDL は、シミュレーション モデルをグラフィカルに表現するための正式な完全かつ明確な言語です。

参考文献

1. ザイグラー、バーナード（1976年）『モデリングとシミュレーションの理論』（第1版）ニューヨーク：ワイリー・インターサイエンスISBN 0-12-778455-12012年6月21日時点のオリジナルよりアーカイブ。
2. Zeigler, Bernard (1968).オートマトンにおけるフィードバック複雑性について(Ph.D.). ミシガン大学.オートマトンとはザイグラー博士の博士論文の数学的モデルであった。
3. Zeigler, Bernard (1984).多面的モデリングと離散事象シミュレーション. ロンドン; オーランド: Academic Press. ISBN 978-0-12-778450-2。
4. Zeigler, Bernard (1987). 「オブジェクト指向環境における階層的かつモジュール化された離散イベントモデリング」.シミュレーション. 49 (5): 219– 230. doi : 10.1177/003754978704900506 . S2CID 62648626 . 
5. Zeigler, Bernard; Kim, Tag Gon; Praehofer, Herbert (2000). Theory of Modeling and Simulation (第2版). New York: Academic Press. ISBN 978-0-12-778455-7。
6. 外部遷移関数を と定義することもできます。ここで、全体状態 に対して部分状態 、は の寿命、の最終更新からの経過時間 となります。この関数の理解方法の詳細については、 「DEVS の動作」の記事を参照してください。${\displaystyle \delta _{ext}:Q\times X\rightarrow S\times \{0,1\}}$ ${\displaystyle Q=S\times \mathbb {T} ^{\infty }\times \mathbb {T} }$ ${\displaystyle (s,t_{s},t_{e})\in Q}$ ${\displaystyle s\in S}$ ${\displaystyle t_{s}\in \mathbb {T} ^{\infty }}$ ${\displaystyle s}$ ${\displaystyle t_{e}\in (\mathbb {T} \cap [0,t_{s}])}$ ${\displaystyle t_{s}}$
8. セリエ、フランソワ E. (1991)。継続的システム モデリング(第 1 版)。スプリンガー。ISBN 978-0-387-97502-3。
9. セリエ、フランソワ E.コフマン、アーネスト (2006)。連続システム シミュレーション(第 1 版)。スプリンガー。ISBN 978-0-387-26102-7。
10. Nutaro, James (2010). 『シミュレーションのためのソフトウェア構築：C++による理論、アルゴリズム、アプリケーション』（第1版）. Wiley. ISBN 978-0-470-41469-9。
11. 離散事象法を用いて連続システムをシミュレートするために量子化された値を用いることは、それより数年前、1990年代初頭に、あるフランス人エンジニアによって実験的に試みられていました。彼は当時、ヴァランシエンヌ大学からスピンオフした企業（現在はシュナイダーエレクトリック傘下。この量子化は、このエンジニアが構想者であり主要開発者でもあるシミュレーションソフトウェアの機能であり、 PLCプログラムのチェックやオペレータのトレーニングに使用されています
12. 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日非アクティブ).
13. Hwang, MH "43".有限およびリアルタイムDEVSネットワークの定性的検証. 2012年モデリング・シミュレーション理論シンポジウム - DEVS統合M&Sシンポジウム議事録.
14. Hwang, MH (2005年4月2日～8日).チュートリアル: スケジュール保存型DEVSに基づくリアルタイムシステムの検証. 2005年DEVSシンポジウム議事録. サンディエゴ. ISBN 1-56555-293-8。
15. Hwang, MH; Zeigler, BP 「有限かつ決定論的DEVSを用いたモジュラー検証フレームワーク」 2006年DEVSシンポジウム議事録。米国アラバマ州ハンツビル。pp.  57– 65。
16. Zeigler, Bernard (1976).モデリングとシミュレーションの理論（初版）. ニューヨーク: Wiley Interscience.
17. Zeigler, Bernard ; Kim, Tag Gon ; Praehofer, Herbert (2000). 『モデリングとシミュレーションの理論』（第2版）. ニューヨーク: Academic Press. ISBN 978-0-12-778455-7。
18. Hwang, Moon H. (2012).有限およびリアルタイムDEVSネットワークの定性的検証. Proceedings of 2012 TMS/DEVS. オーランド、フロリダ州、米国. pp. 43:1–43:8. ISBN 978-1-61839-786-7。
19. Giambiasi, N.; Escude, B.; Ghosh, S. (2001). 「動的システムの一般化離散イベントシミュレーション」. SCS Transactions: DEVS方法論の最近の進歩-パートII . 18 (4): 216– 229.
20. Zacharewicz, Gregory; Frydman, Claudia; Giambiasi, Norbert (2008). 「ワークフローの分散シミュレーションのためのG-DEVS/HLA環境」(PDF) .シミュレーション. 84 (5): 197– 213. doi : 10.1177/0037549708092833 .
21. ウェイナー、ガブリエル・A. (2009). 『離散事象モデリングとシミュレーション：実践者のためのアプローチ』（第1版）CRC Press. ISBN 978-1-4200-5336-4。
22. ザイグラー、バーナード、キム、タグ・ゴン、プレホファー、ハーバート (2000). 『モデリングとシミュレーションの理論』（第2版）. ニューヨーク: アカデミック・プレス. ISBN 978-0-12-778455-7。
23. Zeigler, Bernard (1984).多面的モデリングと離散事象シミュレーション. ロンドン; オーランド: Academic Press. ISBN 978-0-12-778450-2。
24. Hwang, MH; Zeigler, Bernard (2006). A Reachable Graph of Finite and Deterministic DEVS Networks . Proceedings of 2006 DEVS Symposium. Huntsville, Alabama, USA. pp.  48– 56. 2012年7月26日時点のオリジナルよりアーカイブ。
25. 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日非アクティブ).
26. Zeigler, Bernard; Kim, Tag Gon; Praehofer, Herbert (2000). 『モデリングとシミュレーションの理論』（第2版）. ニューヨーク: Academic Press. ISBN 978-0-12-778455-7。
27. Hwang, MH (2005年8月).再構成可能な自動化システムの有限状態グローバル動作の生成：DEVSアプローチ. Proceedings of 2005 IEEE-CASE. エドモントン、カナダ. 2012年12月8日時点のオリジナルよりアーカイブ。
28. Dill, DL (1989).有限状態並行システムのタイミング仮定と検証. 有限状態システムのコンピュータ支援検証手法に関するワークショップ議事録. グルノーブル, フランス. pp.  197– 212.
29. Hwang, MH (2005年8月). 「再構成可能な自動化システムの有限状態グローバル動作の生成：DEVSアプローチ」 2005年IEEE-CASE会議論文集. エドモントン、カナダ. 2012年12月8日時点のオリジナルよりアーカイブ。（注：は と の2 つの機能に分けられます）${\displaystyle \delta _{x}}$ ${\displaystyle \rho :S\times X\rightarrow \{0,1\}}$ ${\displaystyle \delta _{x}:S\times X\rightarrow S}$
30. Zeigler, Bernard ; Kim, Tag Gon ; Praehofer, Herbert (2000). 『モデリングとシミュレーションの理論』（第2版）. ニューヨーク: Academic Press. ISBN 978-0-12-778455-7。（注：は と の2 つの機能に分けられます）${\displaystyle \delta _{y}}$ ${\displaystyle \lambda :S\rightarrow Y^{\phi }}$ ${\displaystyle \delta _{int}:S\rightarrow S}$
31. Hwang, MH; Zeigler, Bernard (2006). 「有限かつ決定論的DEVSを用いたモジュラー検証フレームワーク」 2006年DEVSシンポジウム議事録. アラバマ州ハンツビル. pp.  57– 65. 2012年7月26日時点のオリジナルよりアーカイブ。
32. “DEVSsharp” . 2025年4月13日閲覧。
33. 「XSY」。
34. Mittal, Saurabh. 「xFDDEVS」. 2025年4月13日閲覧。
35. 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 .
36. Zeigler, Bernard ; Kim, Tag Gon ; Praehofer, Herbert (2000). 『モデリングとシミュレーションの理論』（第2版）. ニューヨーク: Academic Press. ISBN 978-0-12-778455-7。（注：は と の2 つの機能に分けられます）${\displaystyle \delta _{y}}$ ${\displaystyle \lambda :S\rightarrow Y^{\phi }}$ ${\displaystyle \delta _{int}:S\rightarrow S}$
37. Hwang, MH (2005年4月2日～8日).チュートリアル: スケジュール保存型DEVSに基づくリアルタイムシステムの検証. 2005年DEVSシンポジウム議事録. サンディエゴ. ISBN 978-1-56555-293-7。
38. Hwang, MH; Cho, SK; Zeigler, Bernard ; Lin, F. (2007).スケジュール保持型DEVSの処理時間境界（レポート）. ACIMS. 2012年7月26日時点のオリジナルよりアーカイブ。 2008年3月18日閲覧。
39. Hwang, MH (2005年8月1～2日).再構成可能な自動化システムの有限状態グローバル動作の生成：DEVSアプローチ. 2005 IEEE-CASE Proceedings of 2005 IEEE-CASE. エドモントン、カナダ.