Finite Model Theory and Its Applications

Front Cover
Springer Science & Business Media, Jun 4, 2007 - Computers - 440 pages
0 Reviews
Finite model theory,as understoodhere, is an areaof mathematicallogic that has developed in close connection with applications to computer science, in particular the theory of computational complexity and database theory. One of the fundamental insights of mathematical logic is that our understanding of mathematical phenomena is enriched by elevating the languages we use to describe mathematical structures to objects of explicit study. If mathematics is the science of patterns, then the media through which we discern patterns, as well as the structures in which we discern them, command our attention. It isthis aspect oflogicwhichis mostprominentin model theory,“thebranchof mathematical logic which deals with the relation between a formal language and its interpretations”. No wonder, then, that mathematical logic, and ?nite model theory in particular, should ?nd manifold applications in computer science: from specifying programs to querying databases, computer science is rife with phenomena whose understanding requires close attention to the interaction between language and structure. This volume gives a broadoverviewof some central themes of ?nite model theory: expressive power, descriptive complexity, and zero–one laws, together with selected applications to database theory and arti?cial intelligence, es- cially constraint databases and constraint satisfaction problems. The ?nal chapter provides a concise modern introduction to modal logic,which emp- sizes the continuity in spirit and technique with ?nite model theory.
 

What people are saying - Write a review

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

Contents

I
1
III
2
V
4
VI
7
VII
8
IX
10
X
11
XI
12
XCII
241
XCIII
242
XCIV
243
XCV
244
XCVI
246
XCVII
247
XCVIII
249
XCIX
251

XII
13
XIII
16
XIV
18
XV
20
XVI
22
XVII
26
XX
28
XXI
34
XXII
50
XXIV
51
XXV
54
XXVI
59
XXVII
60
XXVIII
64
XXIX
74
XXX
79
XXXI
82
XXXII
86
XXXIII
87
XXXIV
89
XXXV
97
XXXVII
99
XXXVIII
104
XXXIX
106
XL
107
XLI
109
XLII
116
XLIII
119
XLIV
125
XLVII
126
XLVIII
128
XLIX
129
L
132
LI
135
LII
138
LIV
144
LV
145
LVI
149
LVII
151
LVIII
152
LIX
153
LX
155
LXI
157
LXII
160
LXIII
165
LXIV
169
LXV
170
LXVI
174
LXVII
177
LXVIII
180
LXIX
186
LXX
187
LXXI
188
LXXII
190
LXXIII
193
LXXV
194
LXXVI
198
LXXVII
203
LXXVIII
205
LXXIX
206
LXXX
210
LXXXI
213
LXXXII
216
LXXXIII
222
LXXXIV
225
LXXXV
231
LXXXVIII
234
LXXXIX
235
XC
237
XCI
239
C
253
CI
254
CII
255
CIII
257
CVI
258
CVIII
262
CIX
266
CX
267
CXI
269
CXIII
272
CXIV
273
CXV
274
CXVI
276
CXVII
277
CXVIII
278
CXIX
280
CXX
285
CXXI
287
CXXII
288
CXXIII
289
CXXIV
290
CXXV
292
CXXVI
295
CXXVII
298
CXXVIII
299
CXXIX
301
CXXXI
303
CXXXII
305
CXXXIII
307
CXXXIV
308
CXXXV
309
CXXXVI
311
CXXXVII
316
CXXXVIII
319
CXXXIX
321
CXL
322
CXLI
323
CXLII
326
CXLIII
330
CXLIV
334
CXLV
338
CXLVIII
340
CXLIX
344
CL
347
CLI
350
CLII
352
CLIII
355
CLIV
357
CLV
362
CLVI
367
CLVII
371
CLX
373
CLXI
378
CLXII
388
CLXIII
389
CLXIV
390
CLXV
395
CLXVI
397
CLXVII
404
CLXVIII
405
CLXIX
406
CLXX
408
CLXXI
410
CLXXII
412
CLXXIII
413
CLXXV
418
CLXXVI
425
CLXXVII
426
CLXXVIII
431
Copyright

Other editions - View all

Common terms and phrases

Popular passages

Page 367 - References [1] S. Abiteboul, R. Hull and V. Vianu, Foundations of Databases, Addison- Wesley, Reading, MA, 1995.
Page 367 - Part of this work was done while the second author was visiting the Department of Computer and Information Sciences, University of California, Santa-Cruz, supported by NSF grant IRI-9123692.
Page 429 - M. Vardi. Why is modal logic so robustly decidable? In DIM ACS Series in Discrete Mathematics and Theoretical Computer Science 31, pages 149-184. American Math. Society, 1997.

About the author (2007)

Erich Graedel is a Professor of Mathematical Foundations of Computer Science at the University of Technology Aachen. His research interests include algorithms, complexity, and logic in computer science.

Phokion G. Kolaitis is a professor of computer science at the University of California, Santa Cruz. His current research interests include logic in computer science, computational complexity, and database theory. He earned a Diploma in Mathematics from the University of Athens, Greece in 1973, and a Ph.D. in Mathematics from the University of California, Los Angeles in 1978. Before joining UC Santa Cruz in 1988, he served as an L.E. Dickson Instructor of Mathematics at the University of Chicago, a faculty member at Occidental College, a visiting faculty member at Stanford University, and a visiting scientist at the IBM Almaden Research Center. Kolaitis was awarded a Guggenheim Fellowship during 1993-94. In 1995, he received an Excellence in Teaching Award by the graduating computer science and computer engineering students at UC Santa Cruz.

Leonid Libkin received his PhD from the University of Pennsylvania and is currently Professor of Computer Science at the University of Toronto. His main research interests include databases and applications of logic in computer science.

Maarten Marx is an associate professor at the Vrije Universiteit Amsterdam. His research interests are in modal and algebraic logic.

Joel Spencer is a Professor of Mathematics and Computer Scienceat the Courant Institute, New York University. His research interests lie in interface between Discrete Mathematics and Theoretical Computer Science, most particularly with the Probabilistic Method as developed by Paul Erdos.

Moshe Y. Vardi is a Noah Harding Professor of Computer Science and Chair of Computer Science at Rice University. Prior to joining Rice in 1993, he was at the IBM Almaden Research Center, where he managed the Mathematics and Related Computer Science Department. His research interests include database systems, computational-complexity theory, multi-agent systems, and design specification and verification. Vardi received his Ph.D. from the Hebrew University of Jerusalem in 1981. He is the author and co-author of over 120 technical papers, as well as a book titled "Reasoning about Knowledge". Vardi is the recipient of 3 IBM Outstanding Innovation Awards. He is an editor of several international journals and is a Fellow of the Association of Computing Machinery.

Yde Venema studied mathematics; in 1992, he received a PhD in Logic with the dissertation `Many-Dimensional Modal Logic'. He is currently a Research Fellow of the Royal Netherlands Academy of Arts and Sciences and an assistant professor at the Institute for Logic, Language and Computation of the University of Amsterdam. His research interests include modal and temporal logic, algebraic logic, and applications of logic in linguistics and computer science.

Scott Weinstein is Professor of Computer Science, Mathematics, and Philosophy at the University of Pennsylvania. His research interests include logic in computer science and the philosphy of mathematics.