Skip to main content

1995 | Buch

Finite Model Theory

Second Edition

verfasst von: Heinz-Dieter Ebbinghaus, Jörg Flum

Verlag: Springer Berlin Heidelberg

Buchreihe : Springer Monographs in Mathematics

insite
SUCHEN

Über dieses Buch

Finite model theory, the model theory of finite structures, has roots in clas­ sical model theory; however, its systematic development was strongly influ­ enced by research and questions of complexity theory and of database theory. Model theory or the theory of models, as it was first named by Tarski in 1954, may be considered as the part of the semantics of formalized languages that is concerned with the interplay between the syntactic structure of an axiom system on the one hand and (algebraic, settheoretic, . . . ) properties of its models on the other hand. As it turned out, first-order language (we mostly speak of first-order logic) became the most prominent language in this respect, the reason being that it obeys some fundamental principles such as the compactness theorem and the completeness theorem. These principles are valuable modeltheoretic tools and, at the same time, reflect the expressive weakness of first-order logic. This weakness is the breeding ground for the freedom which modeltheoretic methods rest upon. By compactness, any first-order axiom system either has only finite models of limited cardinality or has infinite models. The first case is trivial because finitely many finite structures can explicitly be described by a first-order sentence. As model theory usually considers all models of an axiom system, modeltheorists were thus led to the second case, that is, to infinite structures. In fact, classical model theory of first-order logic and its generalizations to stronger languages live in the realm of the infinite.

Inhaltsverzeichnis

Frontmatter
1. Preliminaries
Heinz-Dieter Ebbinghaus, Jörg Flum
2. The Ehrenfeucht-Fraïssé Method
Heinz-Dieter Ebbinghaus, Jörg Flum
3. More on Games
Heinz-Dieter Ebbinghaus, Jörg Flum
4. 0-1 Laws
Heinz-Dieter Ebbinghaus, Jörg Flum
5. Satisfiability in the Finite
Heinz-Dieter Ebbinghaus, Jörg Flum
6. Finite Automata and Logic: A Microcosm of Finite Model Theory
Heinz-Dieter Ebbinghaus, Jörg Flum
7. Descriptive Complexity Theory
Heinz-Dieter Ebbinghaus, Jörg Flum
8. Logics with Fixed-Point Operators
Heinz-Dieter Ebbinghaus, Jörg Flum
9. Logic Programs
Heinz-Dieter Ebbinghaus, Jörg Flum
10. Optimization Problems
Heinz-Dieter Ebbinghaus, Jörg Flum
11. Logics for PTIME
Heinz-Dieter Ebbinghaus, Jörg Flum
12. Quantifiers and Logical Reductions
Heinz-Dieter Ebbinghaus, Jörg Flum
Backmatter
Metadaten
Titel
Finite Model Theory
verfasst von
Heinz-Dieter Ebbinghaus
Jörg Flum
Copyright-Jahr
1995
Verlag
Springer Berlin Heidelberg
Electronic ISBN
978-3-540-28788-9
Print ISBN
978-3-540-28787-2
DOI
https://doi.org/10.1007/3-540-28788-4