| dbo:abstract
|
- Finite model theory is a subarea of model theory. Model theory is the branch of logic which deals with the relation between a formal language (syntax) and its interpretations (semantics). Finite model theory is a restriction of model theory to interpretations on finite structures, which have a finite universe. Since many central theorems of model theory do not hold when restricted to finite structures, finite model theory is quite different from model theory in its methods of proof. Central results of classical model theory that fail for finite structures under finite model theory include the compactness theorem, Gödel's completeness theorem, and the method of ultraproducts for first-order logic (FO). While model theory has many applications to mathematical algebra, finite model theory became an "unusually effective" instrument in computer science. In other words: "In the history of mathematical logic most interest has concentrated on infinite structures. [...] Yet, the objects computers have and hold are always finite. To study computation we need a theory of finite structures." Thus the main application areas of finite model theory are: descriptive complexity theory, database theory and formal language theory. (en)
- La théorie des modèles finis est un sous-domaine de la théorie des modèles. Cette dernière est une branche de la logique mathématique qui traite de la relation entre un langage formel (la syntaxe) et ses interprétations (ses sémantiques). La théorie des modèles finis est la restriction de la théorie des modèles aux interprétations de structures finies, donc qui sont définies sur un ensemble (un univers) fini. Ses applications principales sont la théorie des bases de données, la complexité descriptive et la théorie des langages formels. (fr)
- 有限モデル理論（英: Finite model theory）とは、モデル理論の一種であり、一階述語論理などの論理言語を有限構造（有限群、グラフ、データベース、多くの計算模型など）に適用したときの属性に着目した理論である。論理言語と計算の関係に特に注目し、離散数学や計算複雑性理論やとも密接に関連する。 一階述語論理と古典モデル理論の重要な成果の多くは、有限構造に制限されると成り立たない。例えば、コンパクト性定理、クレイグの補間定理、レーヴェンハイム-スコーレムの定理、ゲーデルの完全性定理などである。このような文脈では、一階述語論理の表現能力が十分とは言えない点が根本的な問題である。このため、一階述語論理に推移閉包や最小不動点の作用素を追加したり、二階述語論理の一部を使ったりして、有限構造での属性を表現できる新たな論理体系を構築する。 有限モデル理論の一分野として重要な理論に記述計算量がある。これは、様々な抽象機械の能力と論理言語の表現能力を結びつけるものである。ある言語が一階述語論理に最小不動点作用素を追加したもので表せる場合、チューリングマシンにある文字列を与えたとき、その文字列がその言語に属するかどうかを判定するには多項式時間を要する（P）。記述計算量の考え方によって、計算複雑性理論と数理論理学の成果の交流が可能となり、標準的な複雑性クラスが「自然」なものであるという証拠も与える。Neil Immerman は、「数理論理学の歴史の中でも、有限構造に関する研究が最も興味深く…さらに言えば、コンピュータ上のオブジェクトは常に有限である。計算の研究には、有限構造の理論が必要である」と述べている。 また、有限モデル理論の重要な帰結の一つに、対象 x の性質 P(x) はほとんどの対象において当てはまるものであるか、ほとんどの対象において当てはまらないものであるかに分類されるという法則(Zero-One Law)がある。たとえば、サイズが n 以下のグラフの性質について考えるとき、対象が連結グラフである確率は n が無限大に近づくにつれて 1 に近づく。逆に、対象が孤立点を含んでいる確率は 0 に近づく。Zero-One Lawは、多項式時間でチェック可能な任意のグラフの性質について、性質を満たす対象の比率が 1 か 0 のどちらかに近づいていくことを主張する。この法則は、大規模な有限構造についての乱択アルゴリズムに影響を及ぼす。 有限モデル理論では、論理の有限な制限についても研究する。例えば、変項数を k 個に制限された一階述語論理などである。 (ja)
- Teoria dos modelos finitos (TMF) é uma subárea da Teoria dos modelos (TM). A TM é um ramo da Lógica matemática que lida com a relação entre a linguagem formal (sintaxe) e suas interpretações (semântica). A TMF é uma restrição da TM para a interpretação de estruturas que tem um universo finito.
* Como muitos teoremas centrais da TM são inconsistentes quando restritos a estruturas finitas, a TMF é bem diferente da TM em seus métodos de prova. Os resultados desses teoremas centras da Teoria dos Modelos clássica que falham para estruturas finitas incluem o Teorema da compacidade, Teorema da completude de Gödel, e o método do para a Lógica de primeira ordem (LPO).
* Como a TM está muito relacionada à álgebra, a TMF se tornou um "efetivo mas não usual" instrumento na Ciência da computação. Em outras palavras: "Na história da Lógica matemática, sempre houve mais interesse nas estruturas infinitas... No entanto, os objetos que os computadores tratam são sempre finitos. Para estudar computação, nós precisamos de uma teoria de estruturas finitas." Assim, as principais áreas de aplicação da TMF são: Teoria da complexidade descritiva, Teoria do banco de dados (Banco de dados relacional) e teoria da linguagem formal.
* A TMF trata da separação de estruturas. A pergunta de motivação usual é se uma dada classe de estruturas pode ser descrita em uma linguagem dada. Por exemplo, todos os grafos cíclicos podem ser separados (dos não cíclicos) através de uma sentença da LPO? Isso também pode ser escrito como: A propriedade "cíclico" de um grafo é expressável na LPO? (pt)
|
| dbo:thumbnail
| |
| dbo:wikiPageExternalLink
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 22407 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:date
| |
| dbp:url
| |
| dbp:wikiPageUsesTemplate
| |
| dcterms:subject
| |
| rdfs:comment
|
- La théorie des modèles finis est un sous-domaine de la théorie des modèles. Cette dernière est une branche de la logique mathématique qui traite de la relation entre un langage formel (la syntaxe) et ses interprétations (ses sémantiques). La théorie des modèles finis est la restriction de la théorie des modèles aux interprétations de structures finies, donc qui sont définies sur un ensemble (un univers) fini. Ses applications principales sont la théorie des bases de données, la complexité descriptive et la théorie des langages formels. (fr)
- Finite model theory is a subarea of model theory. Model theory is the branch of logic which deals with the relation between a formal language (syntax) and its interpretations (semantics). Finite model theory is a restriction of model theory to interpretations on finite structures, which have a finite universe. (en)
- 有限モデル理論（英: Finite model theory）とは、モデル理論の一種であり、一階述語論理などの論理言語を有限構造（有限群、グラフ、データベース、多くの計算模型など）に適用したときの属性に着目した理論である。論理言語と計算の関係に特に注目し、離散数学や計算複雑性理論やとも密接に関連する。 一階述語論理と古典モデル理論の重要な成果の多くは、有限構造に制限されると成り立たない。例えば、コンパクト性定理、クレイグの補間定理、レーヴェンハイム-スコーレムの定理、ゲーデルの完全性定理などである。このような文脈では、一階述語論理の表現能力が十分とは言えない点が根本的な問題である。このため、一階述語論理に推移閉包や最小不動点の作用素を追加したり、二階述語論理の一部を使ったりして、有限構造での属性を表現できる新たな論理体系を構築する。 有限モデル理論では、論理の有限な制限についても研究する。例えば、変項数を k 個に制限された一階述語論理などである。 (ja)
- Teoria dos modelos finitos (TMF) é uma subárea da Teoria dos modelos (TM). A TM é um ramo da Lógica matemática que lida com a relação entre a linguagem formal (sintaxe) e suas interpretações (semântica). A TMF é uma restrição da TM para a interpretação de estruturas que tem um universo finito. (pt)
|
| rdfs:label
|
- Finite model theory (en)
- Théorie des modèles finis (fr)
- 有限モデル理論 (ja)
- Teoria de modelos finitos (pt)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:depiction
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:academicDiscipline
of | |
| is dbo:wikiPageDisambiguates
of | |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is dbp:field
of | |
| is foaf:primaryTopic
of | |
