Loading article…
コンピュータサイエンスにおいて、well-founded semantics は論理プログラミングのための3 値 semanticsであり、一般的な論理プログラムに正確な意味を与えます。
歴史
ウェルファウンド意味論は1988年にヴァン・ゲルダーらによって定義されました。[1] [2] PrologシステムXSBは1997年からウェルファウンド意味論を実装しています。[3] [4]
3値論理
十分に根拠のある意味論は、あらゆる一般論理プログラムに固有のモデルを割り当てます。ただし、命題に trueまたはfalse を割り当てるだけでなく、無知を表す 3 番目の値unknownを追加します。[1]
簡単な例として、 aと という2 つの命題をエンコードする論理プログラムがありますb。が真でない
a 場合は必ず真となり、その逆も同様です。b
a :- ( b )ではない。b :- ( a )ではない。
も もa真bでも偽でもありませんが、両方とも真理値は不明です。 2 値安定モデル意味論aでは、が真で が偽である安定モデルとb、 がb真で がa偽である安定モデルが 2 つあります。
階層化論理プログラムは2値のwell-foundedモデルを持ち、すべての命題は真か偽のいずれかである。これはプログラムの唯一の安定モデルと一致する。well-founded意味論は安定モデル意味論の3値バージョンと見なすことができる。[5]
複雑
1989年、ヴァン・ゲルダーは命題論理プログラムのwell-founded semanticsを計算するアルゴリズムを提案した。このアルゴリズムの時間計算量はプログラムのサイズの2乗である。[6] 2001年時点では、この問題に対する[アップデート]一般的な準2乗アルゴリズムは知られていなかった。 [7]
参考文献
- ^ ab Van Gelder, Allen; Ross, Kenneth A.; Schlipf, John S. (1991 年 7 月). 「一般論理プログラムのための well-founded セマンティクス」. Journal of the ACM . 38 (3): 619–649. doi :10.1145/116825.116838. ISSN 0004-5411.
- ^ Van Gelder, Allen; Ross, Kenneth; Schlipf, John S. (1988). 「一般論理プログラムのための非基礎集合と十分に基礎づけられた意味論」。データベースシステムの原理に関する第 7 回 ACM SIGACT-SIGMOD-SIGART シンポジウムの議事録。ニューヨーク、ニューヨーク、米国: ACM プレス。pp. 221–230。doi : 10.1145 / 308386.308444。ISBN 0897912632。
- ^ ケルナー、フィリップ;ロイシェル、マイケル。バルボサ、ジョアン。コスタ、ビトール・サントス。ダール、ベロニカ。エルメネジルド、マヌエル V.モラレス、ホセ F.ヤン・ヴィーレメーカー;ディアス、ダニエル。アブレウ、サルバドール。シアット、ジョバンニ（2022年11月）。 「プロローグの50年とその先へ」。論理プログラミングの理論と実践。22 (6): 776–858。土井：10.1017/S1471068422000102。hdl : 10174/33387。ISSN 1471-0684。
- ^ Rao, Prasad; Sagonas, Konstantinos; Swift, Terrance; Warren, David S.; Freire, Juliana (1997), Dix, Jürgen; Furbach, Ulrich; Nerode, Anil (eds.)、「XSB: 十分に根拠のあるセマンティクスを効率的に計算するためのシステム」、Logic Programming And Nonmonotonic Reasoning、vol. 1265、ベルリン、ハイデルベルク: Springer Berlin Heidelberg、pp. 430–440、doi :10.1007/3-540-63255-7_33、ISBN 978-3-540-63255-9、2023-11-17取得
- ^ Przymusinski, Teodor. Well-founded Semantics Coincides with Three-Valued Stable Semantics . Fundamenta Informaticae XIII pp. 445-463, 1990.
- ^ Van Gelder, A. ( 1989). 否定を伴う論理プログラムの交互不動点。データベースシステムの原理に関する第 8 回 ACM SIGACT- SIGMOD -SIGART シンポジウムの議事録。ACM Press。pp. 1–10。doi : 10.1145/ 73721.73722。ISBN 978-0-89791-308-9。
- ^ Lonc, Zbigniew; Truszczyński, Mirosław (2001). 「well-founded semantics の計算問題について」.論理プログラミングの理論と実践. 1 (5): 591–609. arXiv : cs/0101014 . doi :10.1017/S1471068401001053. ISSN 1471-0684.