Online Version - Last Updated - 20 Jan 2012 |
 |
| Home |
| |
| Procedures and Resources for Authors |
|
| Information and Resources for Volume Editors |
| |
| Orders and Subscriptions |
| |
| Published Articles |
|
| Upcoming Volumes |
| |
| Contact Us |
| |
| Useful External Links |
| |
| CRPIT Site Search |
Finite Model Theory and its Origins
Fagin, R.
Finite model theory is a study of the logical properties
of finite mathematical structures. This talk gives
an overview of how finite model theory arose, and of
some work that sprang from that. This includes:
1. Differences between the model theory of finite
structures and infinite structures. Most of the
classical theorems of logic fail for finite structures,
which gives us a challenge to develop new
concepts and tools, appropriate for finite structures.
2. The relationship between finite model theory and
complexity theory. Surprisingly enough, it turns
out that in some cases, we can characterize complexity
classes (such as NP) in terms of logic,
without using any notion of machine, computation,
or time.
3. Zero-one laws. There is a remarkable phenomenon,
which says that certain properties
(such as those expressible in first-order logic) are
either almost surely true or almost surely false.
4. Descriptive complexity. Here we consider how
complex a formula must be to express a given
property.
The goal of this talk is to introduce the audience
to the fascinating area of finite model theory.
Cite as: Fagin, R. (2009). Finite Model Theory and its Origins. In Proc. Sixth Asia-Pacific Conference on Conceptual Modelling (APCCM 2009), Wellington, New Zealand. CRPIT, 96. Kirchberg, M. and Link, S., Eds. ACS. 3.
(from crpit.com)
(local if available)
