Finite model theory: Difference between revisions
Removing stub tag(s) |
No edit summary |
||
| Line 5: | Line 5: | ||
One important subfield of finite model theory, [[descriptive complexity]], connects the expressivity of various logical languages with the capabilities of various abstract machines. For example, if a language can be expressed in first-order logic with a least fixed point operator added, a [[Turing machine]] can determine in polynomial time (see [[P (complexity)|P]]) whether a given string is in the language. Descriptive complexity allows results to be transferred between computational complexity and mathematical logic and gives additional evidence that the standard complexity classes are "natural." Neil Immerman states "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."<ref name=Immerman_history>{{cite book | last = Immerman | first = Neil | authorlink = Neil Immerman | title = Descriptive Complexity | year = 1999 | publisher = Springer-Verlag | location = New York | isbn = 0-387-98600-6 | page = 6}}</ref> |
One important subfield of finite model theory, [[descriptive complexity]], connects the expressivity of various logical languages with the capabilities of various abstract machines. For example, if a language can be expressed in first-order logic with a least fixed point operator added, a [[Turing machine]] can determine in polynomial time (see [[P (complexity)|P]]) whether a given string is in the language. Descriptive complexity allows results to be transferred between computational complexity and mathematical logic and gives additional evidence that the standard complexity classes are "natural." Neil Immerman states "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."<ref name=Immerman_history>{{cite book | last = Immerman | first = Neil | authorlink = Neil Immerman | title = Descriptive Complexity | year = 1999 | publisher = Springer-Verlag | location = New York | isbn = 0-387-98600-6 | page = 6}}</ref> |
||
Another important result of finite model theory are the zero-one laws, which establish that many types of logical formulas hold for either almost all or almost no finite structures. For example, the proportion of graphs of size ''n'' that are [[connected graph|connected]] approaches one as ''n'' approaches infinity, while the proportion that contain an [[isolated vertex]] approaches zero. In fact the same is true of any graph property that can be defined in first-order logic: it either approaches one or approaches zero.{{ |
Another important result of finite model theory are the zero-one laws, which establish that many types of logical formulas hold for either almost all or almost no finite structures. For example, the proportion of graphs of size ''n'' that are [[connected graph|connected]] approaches one as ''n'' approaches infinity, while the proportion that contain an [[isolated vertex]] approaches zero. In fact the same is true of any graph property that can be defined in first-order logic: it either approaches one or approaches zero.<ref name=Immerman_history>{{cite book | last = Immerman | first = Neil | authorlink = Neil Immerman | title = Descriptive Complexity | year = 1999 | publisher = Springer-Verlag | location = New York | isbn = 0-387-98600-6 | page = 6}}</ref> This has ramifications for [[randomized algorithm]]s on large finite structures. |
||
Finite model theory also studies finite restrictions of logic, such as first-order logic with only a fixed limit of ''k'' variables. |
Finite model theory also studies finite restrictions of logic, such as first-order logic with only a fixed limit of ''k'' variables. |
||
Revision as of 21:49, 29 April 2010
Finite model theory is a subfield of model theory that focuses on properties of logical languages, such as first-order logic, over finite structures, such as finite groups, graphs, databases, and most abstract machines. It focuses in particular on connections between logical languages and computation, and is closely associated with discrete mathematics, complexity theory, and database theory.
Many important results of first-order logic and classical model theory fail when restricted to finite structures, including the compactness theorem, the Craig interpolation lemma, the Łoś-Tarski preservation theorem, and Gödel's completeness theorem. The essential problem is that in this context, first-order logic is not sufficiently expressive. By extending first-order logic with operators such as transitive closure and least fixed point, and by using fragments of second-order logic, we obtain new logics that have more interesting properties over finite structures.
One important subfield of finite model theory, descriptive complexity, connects the expressivity of various logical languages with the capabilities of various abstract machines. For example, if a language can be expressed in first-order logic with a least fixed point operator added, a Turing machine can determine in polynomial time (see P) whether a given string is in the language. Descriptive complexity allows results to be transferred between computational complexity and mathematical logic and gives additional evidence that the standard complexity classes are "natural." Neil Immerman states "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."[1]
Another important result of finite model theory are the zero-one laws, which establish that many types of logical formulas hold for either almost all or almost no finite structures. For example, the proportion of graphs of size n that are connected approaches one as n approaches infinity, while the proportion that contain an isolated vertex approaches zero. In fact the same is true of any graph property that can be defined in first-order logic: it either approaches one or approaches zero.[1] This has ramifications for randomized algorithms on large finite structures.
Finite model theory also studies finite restrictions of logic, such as first-order logic with only a fixed limit of k variables.
External links
- 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, including a list of open problems
- Finite Model Theory References, a database of references related to finite model theory
- Introductory chapter on Finite Model Theory in Wikibook Logic for Computer Scientists
References
- ^ a b Immerman, Neil (1999). Descriptive Complexity. New York: Springer-Verlag. p. 6. ISBN 0-387-98600-6.