This is a thoroughly revised and enlarged second edition (the first edition was published in the "Perspectives in Mathematical Logic" series in 1995) that presents the main results of descriptive complexity theory, that is, the connections between axiomatizability of classes of finite structures and their complexity with respect to time and space bounds. The logics that are important in this context include fixed-point logics, transitive closure logics, and also certain infinitary languages; their model theory is studied in full detail. The book is written in such a way that the respective parts on model theory and descriptive complexity theory may be read independently.
Author(s): Heinz-Dieter Ebbinghaus, Jörg Flum
Series: Springer Monographs in Mathematics
Edition: 2nd
Publisher: Springer
Year: 2005
Language: English
Pages: 362
Preface......Page 4
Contents......Page 8
A. Structures......Page 11
B. Syntax and semantics of first-order logic......Page 14
C. Some classical results of first-order logic......Page 18
D. Model classes and global relations......Page 20
E. Relational databases and query languages......Page 22
1. Elementary classes......Page 23
2. Ehrenfeucht's theorem......Page 25
3. Examples and Fraisse's theorem......Page 30
4. Hanf's theorem......Page 36
5. Gaifman's theorem......Page 40
1. Second-order logic......Page 46
2. Infinitary logic: the logics L_{∞ω_1} and L_{ω_1ω}......Page 49
3. The logics FO^s and L^s_{∞ω}......Page 55
1. Pebble games......Page 58
2. The s-invariant of a structure......Page 63
3. Scott formulas......Page 65
4. Logics with counting quantifiers......Page 67
5. Failure of classical theorems in the finite......Page 71
1. 0-1 laws for F) and L^ω_{∞ω}......Page 79
2. Parametric classes......Page 82
3. Unlabeled 0-1 laws......Page 85
4. Examples and consequences......Page 92
5. Probabilities of monadic second order properties......Page 96
1. Finite model property of FO^2......Page 102
2. Finite model property of ∀^2∃*-sentences......Page 106
1. Languages accepted by automata......Page 111
2. Word models......Page 114
3. Examples and applications......Page 117
4. First-order definability......Page 120
7. Descriptive Complexity Theory......Page 124
1. Some extensions of first-order logic......Page 125
2. Turing machines and complexity classes......Page 129
1. Digression: Trahtenbrot's theorem......Page 132
2. Structures as inputs......Page 134
3. Logical descriptions of computations......Page 138
4. The complexity of the satisfaction relation......Page 152
5. The main theorem and some consequences......Page 156
1. Appendix......Page 167
1. Inflationary and least fixed-points......Page 170
2. Simultaneous induction and transitivity......Page 182
3. Partial fixed-point logic......Page 196
4. Fixed-point logics and L^ω_{∞ω}......Page 203
1. The logic FO(PFP_PTIME)......Page 210
2. Fixed-point logic with counting......Page 212
5. Fixed-point logics and second-order logic......Page 215
1. Digression: implicit definability......Page 222
6. Transitive closure logic......Page 225
1. FO(DTC) < FO(TC)......Page 226
2. FO(posTC) and normal forms......Page 229
3. FO(TC) < FO(LFP)......Page 234
7. Bounded fixed-point logic......Page 240
1. DATALOG......Page 244
2. I-DATALOG and P-DATALOG......Page 250
3. A preservation theorem......Page 255
4. Normal forms for fixed-point logics......Page 258
5. An application of negative fixed-point logic......Page 268
6. Hierarchies of fixed-point logics......Page 273
1. Polynomially bounded optimization problems......Page 279
2. Approximable optimization problems......Page 284
11. Logics for PTIME......Page 290
1. Logics and invariants......Page 291
2. PTIME on classes of structures......Page 298
12. Quantifiers and Logical Reductions......Page 310
1. Lindström quantifiers......Page 311
2. PTIME and quantifiers......Page 317
3. Logical reductions......Page 323
4. Quantifiers and oracles......Page 333
References......Page 342
Index......Page 351
