Modal_%CE%BC-calculus
理論的なコンピューター サイエンスでは、モーダル μ-計算法( Lμ、L μ、時には単にμ-計算法、これはより一般的な意味を持つ場合もあります) は、最小不動点演算子を追加することによる命題 モーダル論理(多くのモダリティを含む) の拡張です。 μ と最大固定小数点演算子 ν、したがって固定小数点論理.(命題、モーダル) μ 計算は、Dana ScottとJaco de Bakker に端を発し、 Dexter Kozen によって現在最も使用されているバージョンにさらに発展しました。ラベル付けされた遷移システムのプロパティを記述し、これらのプロパティを検証するために使用されます。CTL*とその広く使用されているフラグメント(線形時相論理と計算ツリー論理) を含む、多くの時相論理を μ 計算でエンコードできます。
代数的な見方は、それを完全な格子上の単調関数の代数と見なすことであり、演算子は関数合成と最小および最大の不動点演算子で構成されます。この観点から、モーダル μ 計算はべき集合代数の格子上に μ-calculusのゲームセマンティクスは、完全情報を持つ2 人用ゲーム、特に無限パリティ ゲームに関連しています。
コンテンツ
1 構文
2 表示意味論
2.1 例
3 意思決定の問題
4 こちらもご覧ください
5 ノート
6 参考文献
7 外部リンク
構文
P (命題) とA (アクション) を記号の 2 つの有限集合とし、Var を変数の可算無限集合とする。(命題、モーダル) μ計算の式のセットは、次のように定義されます。
各命題と各変数は公式です。
もしも φ { phi }
と ψ { psi}
は数式であり、φ ∧ ψ
{ phi wedge psi }
式です。
もしも φ { phi }
は式です。¬ φ
{ neg phi }
式です。
もしも φ { phi }
は式であり、 a { a}
はアクションです。 φ { phi }
式です。(次のいずれかで発音します。 a { a}
箱 φ { phi }
またはその後 a { a}
必要な φ { phi }
)
もしも φ { phi }
は式であり、 Z { Z}
変数、次にν Z . φ
{ nu Z.phi }
は式です。ただし、 Z { Z}
φ
{ phi }
つまり、偶数個の否定の範囲内で発生します。(自由変数と束縛変数の概念は通常どおりです。 ν { nu }
が唯一の結合演算子です。)
上記の定義を考えると、構文を次のように充実させることができます。φ ∨ ψ
{ phi lor psi }
味 ¬( ¬φ ∧ ¬ ψ )
{ neg (neg phi land neg psi )}
⟨ a ⟩ φ
{ langle arangle phi }
(次のいずれかで発音します。 a { a}
ダイヤモンド φ { phi }
またはその後 a { a}
おそらく φ { phi }
） 意味¬ ¬ φ
{ neg neg phi }
μ Z . φ
{ mu Z.phi }
味 ¬ ν Z . ¬ φ [ Z :=¬ Z ]
{ neg nu Z.neg phi }
、 どこ φ [ Z
:=¬ Z ]
{ phi }
置換することを意味します¬ Z
{ neg Z}
に Z
{ Z}
のすべての自由な出現で Z { Z}
φ
{ phi }
. 最初の 2 つの公式は、古典的な命題計算とそれぞれ最小多峰性論理 Kからのよく知られたものです。
表記μ Z . φ
{ mu Z.phi }
(およびその双対) は、ラムダ計算から着想を得ています。意図は、式の最小 (およびそれぞれ最大) の不動点を示すことです φ { phi }
「最小化」（およびそれぞれ「最大化」）は変数にあります Z { Z}
、ラムダ計算のようにλ Z . φ
{ lambda Z.phi }
式を持つ関数です φ { phi }
境界変数内 Z { Z}
; 詳細については、以下の表示のセマンティクスを参照して
表示意味論(命題) μ 計算のモデルは、ラベル付き遷移システムとして与えられます。( S R Ⅴ ) { (S，R，V)}
どこ： S { S}
状態のセットです。 R { R}
各ラベルにマップ a { a}
二項関係 S { S}
;Ⅴ : P 2 S
{ V:Pto 2^{S}}
、各命題をマップしますp ε P
{ pin P}
命題が真である状態のセットに。
ラベル付き遷移システムが与えられた場合( S R Ⅴ ) { (S，R，V)}
そして解釈 I { i}
変数の Z { Z}
μ
{ mu}
-微積分、
[ ] I :φ 2 S
{ [!!]_{i}:phi to 2^{S}}
、次の規則によって定義される関数です。
[ ]I = Ⅴ( p ) { _{i}=V(p)}
; [ ]I = I( Z ) { _{i}=i(Z)}
; [ [ φ∧ ψ ] ] I =
[ ]I ∩
[ ] I { [![phi wedge psi ]!]_{i}=[!!]_{i}cap [!!]_{私}}
; [ [ ¬φ ] ] I = S ∖
[ ] I { [!!]_{i}=Ssmallsetminus [!!]_{i}}
; [ [ φ] ] I = { s ε S ∣∀ t ε
S ( s t) ε R a t ε
[ ]I }
{ [!!]_{i}={sin Smid forall tin S，(s，t)in R_{a}rightarrow t in [!!]_{i}}}
; [ [ νZ . φ ] ] I = ⋃ {T ⊆ S ∣ T ⊆
[ ] I [ Z
:=T ] }
{ [!!]_{i}=bigcup {Tsubseteq Smid Tsubseteq [!!]_{i}}}
、 どこ I [ Z
:=T ]
{ i}
マップ Z { Z}
T
{ T}
のマッピングを維持しながら I { i}
他のどこでも。
双対性により、他の基本式の解釈は次のようになります。
[ [ φ∨ ψ ] ] I =
[ ]I ∪
[ ] I { [!!]_{i}=[!!]_{i}cup [!!]_{私}}
; [ [ ⟨a ⟩ φ ] ] I = { sε S ∣ ∃ t ε
S ( s t) ε R a ∧ t ε
[ ]I }
{ [![langle arangle phi ]!]_{i}={sin Smid exists tin S，(s，t)in R_{a}ウェッジ tin [!!]_{i}}}
; [ [ μZ . φ ] ] I = ⋂ {T ⊆ S ∣
[ ] I [ Z
:=T ] ⊆ T }
{ [!!]_{i}=bigcap {Tsubseteq Smid [!!]_{i}subseteq T}}
形式的には、これは、特定の移行システムについて、次のことを意味します。( S R Ⅴ ) { (S，R，V)}
: p
{ p}
状態のセットで保持 Ⅴ ( p ) { V(p)}
;φ ∧ ψ
{ phi wedge psi }
すべての州で保持されます φ { phi }
と ψ { psi}
両方が保持されます。¬ φ
{ neg phi }
すべての州で保持されます φ { phi }
保持しません。 φ { phi }
状態で保持 s { s}
もし毎に a { a}
– からの遷移 s { s}
状態につながる φ { phi }
保持します。⟨ a ⟩ φ
{ langle arangle phi }
状態で保持 s { s}
存在する場合 a { a}
– からの遷移 s { s}
それは次の状態につながります φ { phi }
保持します。ν Z . φ
{ nu Z.phi }
任意のセットの任意の状態で保持 T { T}
そのように、変数が Z { Z}
に設定されています T { T}
、 それから φ { phi }
のすべてに当てはまります T { T}
. ( Knaster–Tarski の定理から、
[ [ νZ . φ ] ] I
{ [!!]_{i}}
の最大不動点です。
[ ] I [ Z
:=T ]
{ [!!]_{i}}
、 と
[ [ μZ . φ ] ] I
{ [!!]_{i}}
その最小不動点。)
の解釈 φ { phi }
と ⟨ a ⟩ φ
{ langle arangle phi }
実際には、動的ロジックの「古典的な」ものです。さらに、オペレーターは μ { mu}
liveness (「最終的に何か良いことが起こる」) と解釈でき、 ν { nu }
レスリー・ランポートの非公式な分類では、安全(「悪いことは決して起こらない」) として。
例ν Z . φ ∧ Z
{ nu Z.phi wedge Z}
“”と解釈されます。 φ { phi }
は、すべての aパスに沿って真です。考え方は、”” φ { phi }
はすべてのパスに沿って真です」は、その (最も弱い) 文として公理的に定義できます。 Z { Z}
これは意味する φ { phi }
これは、aラベルを処理した後も true のままです。μ Z . φ ∨ ⟨ a ⟩ Z
{ mu Z.phi vee langle arangle Z}
は、ある状態への遷移に沿ったパスの存在として解釈されます。 φ { phi }
保持します。
状態がデッドロックフリーである、つまりその状態からのパスが行き止まりに到達しないという特性は、式で表されます。ν Z .( ⋁a ε あ
⟨a ⟩ ⊤ ∧
⋀a ε あ Z )
{ nu Z.left(bigvee _{ain A}langle arangle top wedge bigwedge _{ain A}Zright)}
意思決定の問題
モーダル μ 計算式の充足可能性はEXPTIME-completeです。線形時相論理と同様に、線形モーダル μ 計算のモデル チェック、充足可能性、妥当性の問題はPSPACE 完全です。
こちらもご覧ください
有限モデル理論
交互作用のないモーダルμ計算
ノート
^ スコット、ダナ; バッカー、ヤコブス (1969)。「プログラムの理論」。未発表原稿。
^ コーゼン、デクスター (1982)。「命題μ計算の結果」。オートマトン、言語、プログラミング。ILP。巻。140. pp. 348–359. ドイ: 10.1007/BFb0012782 . ISBN 978-3-540-11576-2.
^ クラーク p.108、定理 6。エマーソン P. 196
^ Arnold and Niwiński、pp. viii-x および第 6 章
^ Arnold and Niwiński， pp. viii-x and chapter 4
^ アーノルドとニウィンスキー、p. 14
^ ブラッドフィールドとスターリング、p. 731
^ ブラッドフィールドとスターリング、p. 6
^ エーリッヒ・グレーデル; フォキオン G. コライティス; レオニード・リブキン; マルテン・マルクス; ジョエル・スペンサー; モシェ・Y・ヴァルディ イデ・ベネマ; スコット・ワインスタイン （2007)。有限モデル理論とその応用。スプリンガー。p。159.ISBN _ 978-3-540-00428-8.
^ クラウス・シュナイダー （2004)。リアクティブ システムの検証: 形式的な方法とアルゴリズム。スプリンガー。p。521.ISBN _ 978-3-540-00296-3.
^ AP州シストラ。クラーク、EM (1985-07-01)。「命題線形時相論理の複雑さ」。J.ACM。32 (3): 733–749. ドイ: 10.1145/3828.3837 . ISSN 0004-5411 .
^ ヴァルディ、MY (1988-01-01)。「時間固定点微積分」。プログラミング言語の原理に関する第 15 回 ACM SIGPLAN-SIGACT シンポジウムの議事録。ポップル’88。米国ニューヨーク州ニューヨーク: ACM: 250–259. ドイ: 10.1145/73560.73582 . ISBN 0897912527.
参考文献
クラーク、エドモンド・M・ジュニア。オルナ・グランバーグ; ドロン・A・ペレド (1999)。モデルチェック。米国マサチューセッツ州ケンブリッジ：MITプレス。ISBN 0-262-03270-8.、第 7 章、μ 計算のモデル チェック、pp. 97–108
スターリング、コリン。（2001）。プロセスのモーダルおよび時間特性。ニューヨーク、ベルリン、ハイデルベルグ：Springer Verlag。ISBN 0-387-98717-7.、第 5 章、モーダル μ 計算、pp. 103–128
アンドレ・アーノルド。ダミアン・ニウィンスキー （2001)。μ-Calculus の初歩. エルゼビア。ISBN 978-0-444-50620-7.、第6章、パワーセット代数上のμ-計算、pp。141–153は、モーダルμ-計算についてです
Yde Venema （2008)モーダルμ計算に関する講義; 論理、言語、情報の第18回ヨーロッパサマースクールで発表されました
ブラッドフィールド、ジュリアン & スターリング、コリン （2006)。「モーダルムー計算」 . P.ブラックバーンで。J. van Benthem & F. Wolter (eds.)。モーダル ロジックのハンドブック。エルゼビア。pp.721–756。
エマーソン、E. アレン(1996)。「モデルチェックとミュー微積分」. 記述の複雑さと有限モデル。アメリカ数学会。pp.185–214。ISBN 0-8218-0517-7.
コーゼン、デクスター (1983)。「命題μ-微積分の結果」 . 理論計算機科学。27 (3): 333–354. ドイ：10.1016/0304-3975(82)90125-6 .
外部リンク
Sophie Pinchinat、Logic、Automata & Games ANU Logic Summer School ’09 での講義のビデオ録画”