有限モデル理論
有限モデル理論（英: Finite model theory）とは、モデル理論の一種であり、一階述語論理などの論理言語を有限構造（有限群、グラフ、データベース、多くの計算模型など）に適用したときの属性に着目した理論である。論理言語と計算の関係に特に注目し、離散数学や計算複雑性理論やデータベース理論とも密接に関連する。
一階述語論理と古典モデル理論の重要な成果の多くは、有限構造に制限されると成り立たない。例えば、コンパクト性定理、クレイグの補間定理、レーヴェンハイム-スコーレムの定理、ゲーデルの完全性定理などである。このような文脈では、一階述語論理の表現能力が十分とは言えない点が根本的な問題である。このため、一階述語論理に推移閉包や最小不動点の作用素を追加したり、二階述語論理の一部を使ったりして、有限構造での属性を表現できる新たな論理体系を構築する。
有限モデル理論の一分野として重要な理論に記述計算量がある。これは、様々な抽象機械の能力と論理言語の表現能力を結びつけるものである。ある言語が一階述語論理に最小不動点作用素を追加したもので表せる場合、チューリングマシンにある文字列を与えたとき、その文字列がその言語に属するかどうかを判定するには多項式時間を要する（P）。記述計算量の考え方によって、計算複雑性理論と数理論理学の成果の交流が可能となり、標準的な複雑性クラスが「自然」なものであるという証拠も与える。Neil Immerman は、「数理論理学の歴史の中でも、有限構造に関する研究が最も興味深く…さらに言えば、コンピュータ上のオブジェクトは常に有限である。計算の研究には、有限構造の理論が必要である」と述べている[1]。
また、有限モデル理論の重要な帰結の一つに、対象 x の性質 P(x) はほとんどの対象において当てはまるものであるか、ほとんどの対象において当てはまらないものであるかに分類されるという法則(Zero-One Law)がある。たとえば、サイズが n 以下のグラフの性質について考えるとき、対象が連結グラフである確率は n が無限大に近づくにつれて 1 に近づく。逆に、対象が孤立点を含んでいる確率は 0 に近づく。Zero-One Lawは、多項式時間でチェック可能な任意のグラフの性質について、性質を満たす対象の比率が 1 か 0 のどちらかに近づいていくことを主張する。[2]この法則は、大規模な有限構造についての乱択アルゴリズムに影響を及ぼす。
有限モデル理論では、論理の有限な制限についても研究する。例えば、変項数を k 個に制限された一階述語論理などである。
脚注
- ↑ Immerman, Neil (1999年). Descriptive Complexity. New York: Springer-Verlag, 6. ISBN 0-387-98600-6.
- ↑ テンプレート:Cite paper Based on lectures from 1993-1994.
外部リンク
- R. Fagin. Finite model theory-a personal perspective. Theoretical Computer Science 116, 1993, pp. 3-31.
- Jouko Väänänen. A Short Course on Finite Model Theory. Department of Mathematics, University of Helsinki. Based on lectures from 1993-1994.
- Finite Model Theory Homepage at Aachen University of Technology, 未解決問題の一覧あり