モーダルロジックIK5の複雑さ

モーダル論理$ mathit {IK5}
$に対するローカル充足可能性問題の複雑さは何ですか?ここでは、逆モダリティで拡張されたユークリッド・フレームにわたるモーダル論理を$
IK5 $で示す。あなたはどんな参考資料も提供できますか?それは$ NP $ですか?

私はその話題について何を知っていますか?

$ IK5 $は$ ExpTime $にあります。   それを$ GF ^ 2
$(2変数のガード付きフラグメント   一次論理) – を参照してください。通常の文法論理の決定
  最初の注文ロジックによるコンバース

     

一方、通常の$ K5 $は$ NP $ -completeです。

     

等価な数式を$ FO ^ 1 $(1変数   一次論理の断片)、そのモデルは
  3つの部分:(1)始動世界$ w $、(2)$ w $の先物(3)   $ w
$のSucessorsのSucessors。削減例をさらに難しく   ロジック(段階的モダリティを含む$ K5
$)については、   段階的モーダル論理に対する満足度問題の複雑さ
  しかし、逆モダリティの存在下で我々は同じことをすることはできません   トリック –
簡単なアイデアは逆の世界が   後継者の数は異なります。

ベストアンサー

ロジックはEXP完結です。下界を証明する1つの方法は、普遍的なモダリティ、あるいはKTBのグローバルな結果関係を増強した論理KTBが、完全なものであることに注意することである(Chen
and Lin [1]; KTBをBと表記することに注意)。

接続されたIK5フレームの$(W、R、R ^ { – 1})$は単一の非再帰的な点であるか、反射的なクラスタ$ C
$と(恐らく空の)集合$ I $それぞれが($ R $で)$ C $の空でない部分集合を見ている非再帰的な点。このように、 $
R_s:= {(x、y) in C ^ 2:は、で存在する(R(z、x)土地R(z、y))} $$ $ C
$の対称関係です。 $ C $のすべての要素が$ I $の要素によって見られる場合、$ R_s
$も反射的です。逆に、このように反射的な対称的なフレームがすべて得られることは容易に理解できます。それに続く

{ mathrm {IK5}} Diamond ^ – top land Box ^ + Diamond
^ – Box ^ – { mathrm { bot 〜 phi ^ *、$$

ここで、変換$ phi ^ * $は命題結合で通勤し、

begin{align*}
(Boxphi)^*&=Box^-(Box^-bottoBox^+phi^*),\
(Aphi)^*&=Box^+phi^*. end{align*}

ここで、$ A $は、 mathrm {KTB} ^ U $の普遍的モダリティを表し、$ Box ^ + $および$
Box ^ – $はそれぞれIK5の順方向および逆方向モダリティを表す。

リファレンス:

[1] Cheng-Chia ChenとI-Peng
Lin、命題モーダル理論の複雑さと命題モーダル理論の一貫性の複雑さ:Proc。 LFCS 1994(Anil Nerode and
Yu。V. Matiyasevich編)、LNCS 813、Springer、pp。69-80、doi 10.1007/3-540-58140-5_8 をご覧ください。

返信を残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です