Information about Finite Model Theory
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 Los-Tarski preservation theorem, the Downward Löwenheim-Skolem 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 if a given string is in the language in polynomial time (see P). 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 checked in polynomial time: it either approaches one or approaches zero. 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.
..... Click the link for more information.
..... Click the link for more information.
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 Los-Tarski preservation theorem, the Downward Löwenheim-Skolem 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 if a given string is in the language in polynomial time (see P). 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 checked in polynomial time: it either approaches one or approaches zero. 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
References
1. ^ Immerman, Neil (1999). Descriptive Complexity. New York: Springer-Verlag, 6. ISBN 0-387-98600-6.
- This article discusses model theory as a mathematical discipline and not the informally used term mathematical model as used in other parts of mathematics and science.
..... Click the link for more information.
First-order logic (FOL) is a formal deductive system used by mathematicians, philosophers, linguists, and computer scientists. It goes by many names, including: first-order predicate calculus (FOPC), the lower predicate calculus,
..... Click the link for more information.
..... Click the link for more information.
In mathematics, a finite group is a group which has finitely many elements. Some aspects of the theory of finite groups were investigated in great depth in the twentieth century, in particular the local theory, and the theory of solvable groups and nilpotent groups.
..... Click the link for more information.
..... Click the link for more information.
graph is the basic object of study in graph theory. Informally speaking, a graph is a set of objects called points, nodes, or vertices connected by links called lines or edges.
..... Click the link for more information.
..... Click the link for more information.
database is a structured collection of records or data that is stored in a computer system so that a computer program or person using a query language can consult it to answer queries. The records retrieved in answer to queries are information that can be used to make decisions.
..... Click the link for more information.
..... Click the link for more information.
An abstract machine, also called an abstract computer, is a theoretical model of a computer hardware or software system used in Automata theory. Abstraction of computing processes is used in both the computer science and computer engineering disciplines and usually assumes
..... Click the link for more information.
..... Click the link for more information.
Discrete mathematics, also called finite mathematics or Decision Maths, is the study of mathematical structures that are fundamentally discrete, in the sense of not supporting or requiring the notion of continuity.
..... Click the link for more information.
..... Click the link for more information.
Complexity theory may refer to:
..... Click the link for more information.
- the study of any complex system
- chaos theory
- Computational complexity theory, a field in theoretical computer science and mathematics dealing with the resources required during computation to solve a given problem
..... Click the link for more information.
Database theory encapsulates a broad range of topics related to the study and research of the theoretical realm of databases and database management systems.
..... Click the link for more information.
Subtopics in database theory
- Precedence graphs
See Also
- Database
- Temporal database
..... Click the link for more information.
In mathematical logic, the compactness theorem states that a (possibly infinite) set of first-order sentences has a model, iff every finite subset of it has a model. There is a generalization of compactness for languages that are of higher order than first-order ones.
..... Click the link for more information.
..... Click the link for more information.
Depending on the type of logic being considered, the definition of Craig interpolation varies. It was first proved in 1957 for first-order logic by William Craig. Propositional Craig interpolation can be defined as follows:
If
..... Click the link for more information.
If
..... Click the link for more information.
Gödel's completeness theorem is an important theorem in mathematical logic which was first proved by Kurt Gödel in 1929. It states, in its most familiar form, that in first-order logic every logically valid formula is provable.
..... Click the link for more information.
..... Click the link for more information.
transitive closure of a binary relation R on a set X is the smallest transitive relation on X that contains R.
For example, if X is the set of humans (alive or dead) and R
..... Click the link for more information.
For example, if X is the set of humans (alive or dead) and R
..... Click the link for more information.
In order theory, a branch of mathematics, the least fixed point (lfp or LFP) of a function is the fixed point which is less than or equal to all other fixed points, according to some partial order.
..... Click the link for more information.
..... Click the link for more information.
For other uses, see Kolmogorov complexity.
Descriptive complexity is a branch of finite model theory, a subfield of computational complexity theory and mathematical logic, which seeks to characterize complexity classes by the type of logic needed to..... Click the link for more information.
Turing machines are extremely basic abstract symbol-manipulating devices which, despite their simplicity, can be adapted to simulate the logic of any computer that could possibly be constructed. They were described in 1936 by Alan Turing.
..... Click the link for more information.
..... Click the link for more information.
In computational complexity theory, P is the complexity class containing decision problems which can be solved by a deterministic Turing machine using a polynomial amount of computation time, or polynomial time.
..... Click the link for more information.
..... Click the link for more information.
In mathematics and computer science, connectivity is one of the basic concepts of graph theory. It is closely related to the theory of network flow problems. The connectivity of a graph is an important measure of its robustness as a network.
..... Click the link for more information.
..... Click the link for more information.
vertex (plural vertices) or node is the fundamental unit out of which graphs are formed: an undirected graph consists of a set of vertices and a set of edges (unordered pairs of vertices), while a directed graph consists of a set of vertices and a set of arcs (ordered
..... Click the link for more information.
..... Click the link for more information.
A randomized algorithm or probabilistic algorithm is an algorithm which employs a degree of randomness as part of its logic. In common practice, this means that the machine implementing the algorithm has access to a pseudorandom number generator.
..... Click the link for more information.
..... Click the link for more information.
Neil Immerman is one of the key developers of descriptive complexity, an approach he is currently applying to research in model checking, database theory, and computational complexity theory.
..... Click the link for more information.
..... Click the link for more information.
This article is copied from an article on Wikipedia.org - the free encyclopedia created and edited by online user community. The text was not checked or edited by anyone on our staff. Although the vast majority of the wikipedia encyclopedia articles provide accurate and timely information please do not assume the accuracy of any particular article. This article is distributed under the terms of GNU Free Documentation License.
Herod_Archelaus
