Finite Model Theory

Front Cover
Springer Science & Business Media, Aug 18, 1999 - Mathematics - 360 pages
0 Reviews
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.
 

What people are saying - Write a review

We haven't found any reviews in the usual places.

Contents

II
1
III
13
V
15
VI
20
VII
26
VIII
30
IX
37
XI
40
XLI
162
XLII
165
XLIV
177
XLV
191
XLVI
198
XLVII
205
XLVIII
207
XLIX
210

XII
46
XIII
49
XIV
54
XV
56
XVI
58
XVII
62
XVIII
71
XX
74
XXI
77
XXII
82
XXIII
84
XXIV
88
XXV
95
XXVII
99
XXVIII
105
XXX
108
XXXI
111
XXXII
114
XXXIII
119
XXXIV
120
XXXV
124
XXXVI
127
XXXVII
129
XXXVIII
133
XXXIX
147
XL
151
L
217
LI
220
LII
221
LIII
224
LIV
229
LV
235
LVI
239
LVIII
245
LIX
250
LX
253
LXI
263
LXII
268
LXIII
275
LXV
280
LXVI
287
LXVII
288
LXVIII
295
LXIX
307
LXX
308
LXXI
314
LXXII
320
LXXIII
330
LXXIV
339
LXXV
349
Copyright

Other editions - View all

Common terms and phrases

Popular passages

Page 344 - Society, 1989. [Kol90] Ph. G. Kolaitis. Implicit definability on finite structures and unambiguous computations. In Proc. 5th IEEE Symp. on Logic in Computer Science, pages 168-180, 1990.
Page 344 - Computation, 83:121-139, 1989. [Imm82] N. Immerman. Upper and lower bounds for first-order expressibility. Journal of Computer and System Sciences, 25:76-98, 1982.
Page 346 - L. Pacholski and W. Szwast, The 0-1 law fails for the class of existential second-order Godel sentences with equality, Proc.
Page 344 - December 1977. [Imm88] N. Immerman. Nondeterministic space is closed under complement. SIAM Journal ' on Computing, 17:935-938, 1988.
Page 345 - Ph. G. Kolaitis and MY Vardi. Fixpoint logic vs. infinitary logic in finite-model theory. In Proc. 7th IEEE Symp. on Logic in Computer Science, pages 46-57, 1992.

References to this book

All Book Search results »

About the author (1999)

Prof. Jvrg Flum, Abteilung f]r Mathematische Logik, Albert-Ludwigs-Universitdt Freiburg, Germany, http: //logik.mathematik.uni-freiburg.de/personen/Flum.html Prof. Martin Grohe, Institut f]r Informatik, Humboldt-Universitdt zu Berlin, Germany, http: //www.informatik.hu-berlin.de/~grohe/ The authors are very well qualified to write this book. In addition to their strong backgrounds in complexity, algorithms, etc., they have contributed a number of specific key results in parameterized complexity (e.g., http: //epubs.siam.org/sam-bin/dbq/article/42720). Jvrg Flum has coauthored two other Springer monographs: (i) "Mathematical Logic," Undergraduate Texts in Mathematics, 0-387-94258-0, 3rd printing since 1994, over 4000 copies sold, Heinz-Dieter Ebbinghaus, Jvrg Flum, Wolfgang Thomas, http: //www.springer.com/0-387-94258-0. (ii) "Finite Model Theory," Springer Monographs in Mathematics (was in series Perspectives in Mathematical Logic), printed in soft- and hardback, 1995, 2nd ed. in 1999, 2nd corr. print in 2006, Heinz-Dieter Ebbinghaus, Jvrg Flum, 3-540-28787-6, http: //www.springer.com/3-540-28787-6. In addition, Jvrg Flum coauthored the following LNM title: Vol. 769, "Topological Model Theory, 1980, 3-540-09732-5, Jvrg Flum, Martin Ziegler. And he coedited the following LNCS title: Vol. 1683, CSL 1999 conf. proc., Jvrg Flum, Mario Rodriguez-Artalejo, 1999, 3-540-66536-6. Prof. Martin Grohe has authored over 50 articles for refereed theoretical computer science journals and conference proceedings (http: //www.informatik.uni-trier.de/~ley/db/indices/a-tree/g/Grohe: Martin.html) in the areas of logic, complexity, algorithms, etc.

Bibliographic information