Preface |
Preliminaries / 1: |
The Ehrenfeucht-Fraisse Method / 2: |
Elementary Classes / 2.1: |
Ehrenfeucht's Theorem / 2.2: |
Examples and Fraisse's Theorem / 2.3: |
Hanf's Theorem / 2.4: |
Gaifman's Theorem / 2.5: |
More on Games / 3: |
Second-Order Logic / 3.1: |
Infinitary Logic: The Logics L[subscript infinity omega] and L[subscript [omega]1[omega]] / 3.2: |
The Logics FO[superscript s] and L[superscript s subscript infinity omega] / 3.3: |
Pebble Games / 3.3.1: |
The s-Invariant of a Structure / 3.3.2: |
Scott Formulas / 3.3.3: |
Logics with Counting Quantifiers / 3.4: |
Failure of Classical Theorems in the Finite / 3.5: |
0-1 Laws / 4: |
0-1 Laws for FO and L[superscript omega subscript infinity omega] / 4.1: |
Parametric Classes / 4.2: |
Unlabeled 0-1 Laws / 4.3: |
Appendix / 4.3.1: |
Examples and Consequences / 4.4: |
Probabilities of Monadic Second Order Properties / 4.5: |
Satisfiability in the Finite / 5: |
Finite Model Property of FO[superscript 2] / 5.1: |
Finite Model Property of [characters not reproducible]-Sentences / 5.2: |
Finite Automata and Logic: A Microcosm of Finite Model Theory / 6: |
Languages Accepted by Automata / 6.1: |
Word Models / 6.2: |
Examples and Applications / 6.3: |
First-Order Definability / 6.4: |
Descriptive Complexity Theory / 7: |
Some Extensions of First-Order Logic / 7.1: |
Turing Machines and Complexity Classes / 7.2: |
Digression: Trahtenbrot's Theorem / 7.2.1: |
Structures as Inputs / 7.2.2: |
Logical Descriptions of Computations / 7.3: |
The Complexity of the Satisfaction Relation / 7.4: |
The Main Theorem and Some Consequences / 7.5: |
Logics with Fixed-Point Operators / 7.5.1: |
Inflationary and Least Fixed-Points / 8.1: |
Simultaneous Induction and Transitivity / 8.2: |
Partial Fixed-Point Logic / 8.3: |
Fixed-Point Logics and L[superscript omega subscript infinity omega] / 8.4: |
The Logic FO(PFP[subscript PTIME]) / 8.4.1: |
Fixed-Point Logic with Counting / 8.4.2: |
Fixed-Point Logics and Second-Order Logic / 8.5: |
Digression: Implicit Definability / 8.5.1: |
Transitive Closure Logic / 8.6: |
FO(DTC) < FO(TC) / 8.6.1: |
FO(posTC) and Normal Forms / 8.6.2: |
FO(TC) < FO(LFP) / 8.6.3: |
Bounded Fixed-Point Logic / 8.7: |
Logic Programs / 9: |
DATALOG / 9.1: |
I-DATALOG and P-DATALOG / 9.2: |
A Preservation Theorem / 9.3: |
Normal Forms for Fixed-Point Logics / 9.4: |
An Application of Negative Fixed-Point Logic / 9.5: |
Hierarchies of Fixed-Point Logics / 9.6: |
Optimization Problems / 10: |
Polynomially Bounded Optimization Problems / 10.1: |
Approximable Optimization Problems / 10.2: |
Logics for PTIME / 11: |
Logics and Invariants / 11.1: |
PTIME on Classes of Structures / 11.2: |
Quantifiers and Logical Reductions / 12: |
Lindstrom Quantifiers / 12.1: |
PTIME and Quantifiers / 12.2: |
Logical Reductions / 12.3: |
Quantifiers and Oracles / 12.4: |
References |
Index |
Preface |
Preliminaries / 1: |
The Ehrenfeucht-Fraisse Method / 2: |