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.
The book 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. Other topics include DATALOG languages, quantifiers and oracles, 0-1 laws, and optimization and approximation problems. The book is written in such a way that the respective parts on model theory and descriptive complexity theory may be read independently. This second edition is a thoroughly revised and enlarged version of the original text.
Author(s): Heinz-Dieter Ebbinghaus, Jörg Flum
Series: Springer Monographs in Mathematics
Edition: 2nd
Publisher: Springer
Year: 2005
Language: English
Pages: 363
City: New York, NY
Preface ......Page 5
Table of contents ......Page 9
1. Preliminaries ......Page 12
2.1 Elementary Classes ......Page 24
2.2 Ehrenfeucht’s Theorem ......Page 26
2.3 Examples and Fraïssé’s Theorem ......Page 31
2.4 Hanf’s Theorem ......Page 37
2.5 Gaifman’s Theorem ......Page 41
3.1 Second-Order Logic ......Page 47
3.2 Infinitary Logic: The Logics L∞ω, and Lω1ω ......Page 50
3.3 The Logics FO^s and L^s_∞ω ......Page 56
3.3.1 Pebble Games ......Page 59
3.3.2 The s-Invariant of a Structure ......Page 64
3.3.3 Scott Formulas ......Page 66
3.4 Logics with Counting Quantifiers ......Page 68
3.5 Failure of Classical Theorems in the Finite ......Page 72
4.1 0-1 Laws for FO and Lω∞ω ......Page 80
4.2 Parametric Classes ......Page 83
4.3 Unlabeled 0-1 Laws ......Page 86
4.3.1 Appendix ......Page 91
4.4 Examples and Consequences ......Page 93
4.5 Probabilities of Monadic Second Order Properties ......Page 97
5.1 Finite Model Property of FO2 ......Page 103
5.2 Finite Model Property of ∀∀∃*-Sentences ......Page 107
6.1 Languages Accepted by Automata ......Page 112
6.2 Word Models ......Page 115
6.3 Examples and Applications ......Page 118
6.4 First-Order Definability ......Page 121
7. Descriptive Complexity Theory ......Page 125
7.1 Some Extensions of First-Order Logic ......Page 126
7.2 Turing Machines and Complexity Classes ......Page 130
7.2.1 Digression: Trahtenbrot’s Theorem ......Page 133
7.2.2 Structures as Inputs ......Page 135
7.3 Logical Descriptions of Computations ......Page 139
7.4 The Complexity of the Satisfaction Relation ......Page 153
7.5 The Main Theorem and Some Consequences ......Page 157
7.5.1 Appendix ......Page 168
8.1 Inflationary and Least Fixed-Points ......Page 171
8.2 Simultaneous Induction and Transitivity ......Page 183
8.3 Partial Fixed-Point Logic ......Page 197
8.4 Fixed-Point Logics and Lω∞ω ......Page 204
8.4.1 The Logic FO(PFPptime) ......Page 211
8.4.2 Fixed-Point Logic with Counting ......Page 213
8.5 Fixed-Point Logics and Second-Order Logic ......Page 216
8.5.1 Digression: Implicit Definability ......Page 223
8.6 Transitive Closure Logic ......Page 226
8.6.1 FO(DTC) < FO(TC) ......Page 227
8.6.2 FO(posTC) and Normal Forms ......Page 230
8.6.3 FO(TC) < FO(LFP) ......Page 235
8.7 Bounded Fixed-Point Logic ......Page 241
9.1 DATALOG ......Page 245
9.2 I-DATALOG and P-DATALOG ......Page 251
9.3 A Preservation Theorem ......Page 256
9.4 Normal Forms for Fixed-Point Logics ......Page 259
9.5 An Application of Negative Fixed-Point Logic ......Page 269
9.6 Hierarchies of Fixed-Point Logics ......Page 274
10.1 Polynomially Bounded Optimization Problems ......Page 280
10.2 Approximable Optimization Problems ......Page 285
11. Logics for PTIME ......Page 291
11.1 Logics and Invariants ......Page 292
11.2 PTIME on Classes of Structures ......Page 299
12. Quantifiers and Logical Reductions ......Page 311
12.1 Lindström Quantifiers ......Page 312
12.2 PTIME and Quantifiers ......Page 318
12.3 Logical Reductions ......Page 324
12.4 Quantifiers and Oracles ......Page 334
References ......Page 343
Index ......Page 352
