確率的バイシミュレーション

理論計算機科学において、確率的双模倣は、 KG LarsenとA. Skouによって最初に説明された完全確率的遷移システムに対する双模倣の概念の拡張である。 ^[1]

離散確率遷移システムは、3つの

S=(\operatorname {St} ,\operatorname {Act} ,\tau :\operatorname {St} \times \operatorname {Act} \times \operatorname {St} \rightarrow [0,1])

ここで、は状態sから始まり、アクションa を実行して状態tで終了する確率を示します。状態のセットは可算であると想定されます。アクションに確率を割り当てる試みはありません。アクションは敵対者または環境によって非決定論的に選択されると想定されます。このタイプのシステムは完全に確率的であり、その他の不確定性はありません。 $\tau (s,a,t)$

システムS上の確率的双類似性の定義は、状態空間 St 上の同値関係 Rであり、St 内のs、tのすべてのペアとsRtに対して、Act 内のすべてのアクションaに対して、およびRのすべての同値クラスCに対して、2 つの状態を関連付けるR が存在する場合、それらの状態は確率的に双類似性があると言われます。 $\tau(s,a,C)=\tau(t,a,C).$

マルコフ連鎖に適用した場合、確率的双模倣は集中可能性と同じ概念である。^[2]^[3] 確率的双模倣は重み付き双模倣に自然に拡張される。^[4]

参考文献

^ KG Larsen と A. Skou が執筆し、 Information and Computation 誌第 94 巻、1-28 ページ、1991 年に掲載された論文「Bisimulation through Probabilistic Testing」に掲載されました。
^ 弱い確率的双模倣による確率的非干渉、ジェフリー・スミス著、第 16 回 IEEE コンピュータセキュリティ基礎ワークショップ (CSFW'03) の議事録、1063-6900/03
^ ケメニー、ジョン・G. ; スネル、J. ローリー (1976年7月) [1960]。ゲーリング、FW; ハルモス、PR (編)。有限マルコフ連鎖(第2版)。ニューヨークベルリンハイデルベルク東京:シュプリンガー出版社。p. 224。ISBN 978-0-387-90192-3。
^ Oliveira, JN (2013). 「行列のカテゴリにおけるコ代数としての重み付きオートマトン」. Int. J. Found. Comput. Sci. 24 (6): 709–728. doi :10.1142/S0129054113400145. hdl : 1822/24651 .

[1] ^ KG Larsen と A. Skou が執筆し、 Information and Computation 誌第 94 巻、1-28 ページ、1991 年に掲載された論文「Bisimulation through Probabilistic Testing」に掲載されました。

[2] 弱い確率的双模倣による確率的非干渉、ジェフリー・スミス著、第 16 回 IEEE コンピュータセキュリティ基礎ワークショップ (CSFW'03) の議事録、1063-6900/03

[3] ケメニー、ジョン・G. ; スネル、J. ローリー (1976年7月) [1960]。ゲーリング、FW; ハルモス、PR (編)。有限マルコフ連鎖(第2版)。ニューヨークベルリンハイデルベルク東京:シュプリンガー出版社。p. 224。ISBN 978-0-387-90192-3。

[4] Oliveira, JN (2013). 「行列のカテゴリにおけるコ代数としての重み付きオートマトン」. Int. J. Found. Comput. Sci. 24 (6): 709–728. doi :10.1142/S0129054113400145. hdl : 1822/24651 .