This HTML5 document contains 53 embedded RDF statements represented using HTML+Microdata notation.

The embedded RDF content will be recognized by any processor of HTML5 Microdata.

Namespace Prefixes

PrefixIRI
dcthttp://purl.org/dc/terms/
template-jahttp://ja.dbpedia.org/resource/Template:
dbohttp://dbpedia.org/ontology/
foafhttp://xmlns.com/foaf/0.1/
n15http://www.almaden.ibm.com/cs/people/fagin/
dbpedia-wikidatahttp://wikidata.dbpedia.org/resource/
rdfshttp://www.w3.org/2000/01/rdf-schema#
n8http://www.math.helsinki.fi/logic/people/jouko.vaananen/
freebasehttp://rdf.freebase.com/ns/
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
n9http://www-mgi.informatik.rwth-aachen.de/FMT/
owlhttp://www.w3.org/2002/07/owl#
n7http://ja.dbpedia.org/resource/Category:
wikipedia-jahttp://ja.wikipedia.org/wiki/
provhttp://www.w3.org/ns/prov#
xsdhhttp://www.w3.org/2001/XMLSchema#
dbpedia-jahttp://ja.dbpedia.org/resource/
prop-jahttp://ja.dbpedia.org/property/

Statements

Subject Item
dbpedia-wikidata:Q5450405
owl:sameAs
dbpedia-ja:有限モデル理論
Subject Item
dbpedia-ja:モデル理論
dbo:wikiPageWikiLink
dbpedia-ja:有限モデル理論
Subject Item
dbpedia-ja:ロナルド・フェイギン
dbo:wikiPageWikiLink
dbpedia-ja:有限モデル理論
prop-ja:field
dbpedia-ja:有限モデル理論
Subject Item
dbpedia-ja:形式的検証
dbo:wikiPageWikiLink
dbpedia-ja:有限モデル理論
Subject Item
dbpedia-ja:形式言語の階層
dbo:wikiPageWikiLink
dbpedia-ja:有限モデル理論
Subject Item
dbpedia-ja:有限モデル理論
rdfs:label
有限モデル理論
rdfs:comment
有限モデル理論（英: Finite model theory）とは、モデル理論の一種であり、一階述語論理などの論理言語を有限構造（有限群、グラフ、データベース、多くの計算模型など）に適用したときの属性に着目した理論である。論理言語と計算の関係に特に注目し、離散数学や計算複雑性理論やとも密接に関連する。 一階述語論理と古典モデル理論の重要な成果の多くは、有限構造に制限されると成り立たない。例えば、コンパクト性定理、クレイグの補間定理、レーヴェンハイム-スコーレムの定理、ゲーデルの完全性定理などである。このような文脈では、一階述語論理の表現能力が十分とは言えない点が根本的な問題である。このため、一階述語論理に推移閉包や最小不動点の作用素を追加したり、二階述語論理の一部を使ったりして、有限構造での属性を表現できる新たな論理体系を構築する。 有限モデル理論では、論理の有限な制限についても研究する。例えば、変項数を k 個に制限された一階述語論理などである。
owl:sameAs
freebase:m.05vtjb
dct:subject
n7:数学に関する記事 n7:数理論理学 n7:モデル理論
dbo:wikiPageID
1354725
dbo:wikiPageRevisionID
73882345
dbo:wikiPageWikiLink
dbpedia-ja:離散数学 dbpedia-ja:計算模型 dbpedia-ja:ゲーデルの完全性定理 dbpedia-ja:コンパクト性定理 dbpedia-ja:モデル理論 dbpedia-ja:推移閉包 n7:モデル理論 dbpedia-ja:乱択アルゴリズム dbpedia-ja:抽象機械 dbpedia-ja:最小不動点 dbpedia-ja:グラフ理論 dbpedia-ja:二階述語論理 dbpedia-ja:データベース dbpedia-ja:群_(数学) dbpedia-ja:チューリングマシン dbpedia-ja:複雑性クラス dbpedia-ja:英語 dbpedia-ja:計算複雑性理論 dbpedia-ja:データベース理論 dbpedia-ja:連結グラフ dbpedia-ja:P_(計算複雑性理論) dbpedia-ja:一階述語論理 dbpedia-ja:クレイグの補間定理 dbpedia-ja:記述計算量 n7:数学に関する記事 n7:数理論理学 dbpedia-ja:レーヴェンハイム-スコーレムの定理
dbo:wikiPageExternalLink
n8:shortcourse.pdf n9: n15:tcs93.pdf n15:
prop-ja:wikiPageUsesTemplate
template-ja:Mathlogic-stub template-ja:Reflist
foaf:isPrimaryTopicOf
wikipedia-ja:有限モデル理論
dbo:abstract
有限モデル理論（英: Finite model theory）とは、モデル理論の一種であり、一階述語論理などの論理言語を有限構造（有限群、グラフ、データベース、多くの計算模型など）に適用したときの属性に着目した理論である。論理言語と計算の関係に特に注目し、離散数学や計算複雑性理論やとも密接に関連する。 一階述語論理と古典モデル理論の重要な成果の多くは、有限構造に制限されると成り立たない。例えば、コンパクト性定理、クレイグの補間定理、レーヴェンハイム-スコーレムの定理、ゲーデルの完全性定理などである。このような文脈では、一階述語論理の表現能力が十分とは言えない点が根本的な問題である。このため、一階述語論理に推移閉包や最小不動点の作用素を追加したり、二階述語論理の一部を使ったりして、有限構造での属性を表現できる新たな論理体系を構築する。 有限モデル理論の一分野として重要な理論に記述計算量がある。これは、様々な抽象機械の能力と論理言語の表現能力を結びつけるものである。ある言語が一階述語論理に最小不動点作用素を追加したもので表せる場合、チューリングマシンにある文字列を与えたとき、その文字列がその言語に属するかどうかを判定するには多項式時間を要する（P）。記述計算量の考え方によって、計算複雑性理論と数理論理学の成果の交流が可能となり、標準的な複雑性クラスが「自然」なものであるという証拠も与える。Neil Immerman は、「数理論理学の歴史の中でも、有限構造に関する研究が最も興味深く…さらに言えば、コンピュータ上のオブジェクトは常に有限である。計算の研究には、有限構造の理論が必要である」と述べている。 また、有限モデル理論の重要な帰結の一つに、対象 x の性質 P(x) はほとんどの対象において当てはまるものであるか、ほとんどの対象において当てはまらないものであるかに分類されるという法則(Zero-One Law)がある。たとえば、サイズが n 以下のグラフの性質について考えるとき、対象が連結グラフである確率は n が無限大に近づくにつれて 1 に近づく。逆に、対象が孤立点を含んでいる確率は 0 に近づく。Zero-One Lawは、多項式時間でチェック可能な任意のグラフの性質について、性質を満たす対象の比率が 1 か 0 のどちらかに近づいていくことを主張する。この法則は、大規模な有限構造についての乱択アルゴリズムに影響を及ぼす。 有限モデル理論では、論理の有限な制限についても研究する。例えば、変項数を k 個に制限された一階述語論理などである。
dbo:wikiPageLength
2514
prov:wasDerivedFrom
wikipedia-ja:有限モデル理論?oldid=73882345&ns=0
Subject Item
dbpedia-ja:記述計算量
dbo:wikiPageWikiLink
dbpedia-ja:有限モデル理論
Subject Item
wikipedia-ja:有限モデル理論
foaf:primaryTopic
dbpedia-ja:有限モデル理論