有限モデル理論
有限モデル理論(英: Finite model theory)とは、モデル理論の一種であり、一階述語論理などの論理言語を有限構造(有限群、グラフ、データベース、多くの計算模型など)に適用したときの属性に着目した理論である。論理言語と計算の関係に特に注目し、離散数学や計算複雑性理論やデータベース理論とも密接に関連する。
一階述語論理と古典モデル理論の重要な成果の多くは、有限構造に制限されると成り立たない。例えば、コンパクト性定理、クレイグの補間定理、レーヴェンハイム-スコーレムの定理、ゲーデルの完全性定理などである。このような文脈では、一階述語論理の表現能力が十分とは言えない点が根本的な問題である。このため、一階述語論理に推移閉包や最小不動点の作用素を追加したり、二階述語論理の一部を使ったりして、有限構造での属性を表現できる新たな論理体系を構築する。
有限モデル理論の一分野として重要な理論に記述計算量がある。これは、様々な抽象機械の能力と論理言語の表現能力を結びつけるものである。ある言語が一階述語論理に最小不動点作用素を追加したもので表せる場合、チューリングマシンにある文字列を与えたとき、その文字列がその言語に属するかどうかを判定するには多項式時間を要する(P)。