Unifying Themes in Finite Model Theory / 1: |
Definability Theory / 1.1: |
Classification of Concepts in Terms of Definitional Complexity / 1.1.1: |
What More Do We Know When We Know a Concept Is L-Definable? / 1.1.2: |
Logics with Finitely Many Variables / 1.1.3: |
Distinguishing Structures: L-Equivalence and Comparison Games / 1.1.4: |
Random Graphs and 0-1 Laws / 1.1.5: |
Constraint Satisfaction Problems / 1.1.6: |
Descriptive Complexity / 1.2: |
Satisfaction / 1.2.1: |
What Is a Logic for PTIME? / 1.2.2: |
Finite Model Theory and Infinite Structures / 1.3: |
Tame Fragments and Tame Classes / 1.4: |
References |
On the Expressive Power of Logics on Finite Models / 2: |
Introduction / 2.1: |
Basic Concepts / 2.2: |
Ehrenfeucht-Fraisse Games for First-Order Logic / 2.3: |
Computational Complexity / 2.4: |
Complexity Classes / 2.4.1: |
The Complexity of Logic / 2.4.2: |
Ehrenfeucht-Fraisse Games for Existential Second-Order Logic / 2.5: |
Logics with Fixed-Point Operators / 2.6: |
Operators and Fixed Points / 2.6.1: |
Least Fixed-Point Logic / 2.6.2: |
Datalog and Datalog([NotEqual]) / 2.6.3: |
The Complementation Problem for LFP[subscript 1] and a Normal Form for LFP / 2.6.4: |
Partial Fixed-Point Logic / 2.6.5: |
Infinitary Logics with Finitely Many Variables / 2.7: |
The Infinitary Logic L[Characters not reproducible] / 2.7.1: |
Pebble Games and L[Characters not reproducible]-Definability / 2.7.2: |
0-1 Laws for L[Characters not reproducible] / 2.7.3: |
Definability and Complexity of L[Characters not reproducible]-Equivalence / 2.7.4: |
Least Fixed-Point Logic vs. Partial Fixed-Point Logic on Finite Structures / 2.7.5: |
Existential Infinitary Logics with Finitely Many Variables / 2.8: |
The Infinitary Logics [Characters not reproducible] and [Characters not reproducible] ([NotEqual]) / 2.8.1: |
Existential Pebble Games / 2.8.2: |
Descriptive Complexity of Fixed Subgraph Homeomorphism Queries / 2.8.3: |
Finite Model Theory and Descriptive Complexity / 3: |
Definability and Complexity / 3.1: |
Complexity Issues in Logic / 3.1.1: |
Model Checking for First-Order Logic / 3.1.2: |
The Strategy Problem for Finite Games / 3.1.3: |
Complexity of First-Order Model Checking / 3.1.4: |
Encoding Finite Structures by Words / 3.1.5: |
Capturing Complexity Classes / 3.2: |
Capturing NP: Fagin's Theorem / 3.2.1: |
Logics That Capture Complexity Classes / 3.2.2: |
Capturing Polynomial Time on Ordered Structures / 3.2.3: |
Capturing Logarithmic Space Complexity / 3.2.4: |
Transitive Closure Logics / 3.2.5: |
Fixed-Point Logics / 3.3: |
Some Fixed-Point Theory / 3.3.1: |
The Modal [mu]-Calculus / 3.3.2: |
Parity Games / 3.3.4: |
Model-Checking Games for Least Fixed-Point Logic / 3.3.5: |
Definability of Winning Regions in Parity Games / 3.3.6: |
Simultaneous Fixed-Point Inductions / 3.3.7: |
Inflationary Fixed-Point Logic / 3.3.8: |
Datalog and Stratified Datalog / 3.3.9: |
Logics with Counting / 3.4: |
Logics with Counting Terms / 3.4.1: |
Fixed-Point Logic with Counting / 3.4.2: |
Datalog with Counting / 3.4.3: |
Capturing PTIME via Canonization / 3.5: |
Definable Linear Orders / 3.5.1: |
Canonizations and Interpretations / 3.5.2: |
Capturing PTIME up to Bisimulation / 3.5.3: |
Is There a Logic for PTIME? / 3.5.4: |
Algorithmic Model Theory / 3.6: |
Beyond Finite Structures / 3.6.1: |
Finitely Presentable Structures / 3.6.2: |
Metafinite Structures / 3.6.3: |
Metafinite Spectra / 3.6.4: |
Descriptive Complexity over the Real Numbers / 3.6.5: |
Appendix: Alternating Complexity Classes / 3.7: |
Logic and Random Structures / 4: |
An Instructive Example / 4.1: |
Random Graphs / 4.2: |
Extension Statements / 4.3: |
Closure / 4.4: |
The Almost Sure Theory / 4.5: |
The Case p Constant / 4.6: |
Countable Models / 4.7: |
A Dynamic View / 4.8: |
Infinite Spectra via Almost Sure Encoding / 4.9: |
The Jump Condition / 4.10: |
The Complexity Condition / 4.11: |
Nonconvergence via Almost Sure Encoding / 4.12: |
No Almost Sure Representation of Evenness / 4.13: |
The Ehrenfeucht Game / 4.14: |
About the References / 4.15: |
Embedded Finite Models and Constraint Databases / 5: |
Organization / 5.1: |
Relational Databases and Embedded Finite Models / 5.2: |
Constraint Databases / 5.3: |
Collapse and Genericity: An Overview / 5.4: |
Approaches to Proving Expressivity Bounds / 5.4.1: |
Active-Generic Collapse / 5.5: |
The Ramsey Property / 5.5.1: |
Collapse Results / 5.5.2: |
Natural-Active Collapse / 5.6: |
Collapse: Failure and Success / 5.6.1: |
Good Structures vs. Bad Structures: O-minimality / 5.6.2: |
Collapse Theorem and Corollaries / 5.6.3: |
Collapse Algorithm: the Linear Case / 5.6.4: |
Collapse Algorithm: the General Case / 5.6.5: |
Collapse Without O-minimality / 5.6.6: |
Natural-Generic Collapse / 5.6.7: |
Model Theory and Collapse Results / 5.7: |
Pseudo-finite Homogeneity / 5.7.1: |
Finite Cover Property and Collapse / 5.7.2: |
Isolation and Collapse / 5.7.3: |
The VC Dimension and Collapse Results / 5.8: |
Random Graph and Collapse to MSO / 5.8.1: |
Complexity Bounds for Generic Queries / 5.8.2: |
Expressiveness of Constraint Query Languages / 5.9: |
Reductions to the Finite Case / 5.9.1: |
Topological Properties / 5.9.2: |
Linear vs. Polynomial Constraints / 5.9.3: |
Query Safety / 5.10: |
Finite and Infinite Query Safety / 5.10.1: |
Safe Translations / 5.10.2: |
Finite Query Safety: Characterization / 5.10.3: |
Infinite Query Safety: Reduction / 5.10.4: |
Deciding Safety / 5.10.5: |
Dichotomy Theorem for Embedded Finite Models / 5.10.6: |
Database Considerations / 5.11: |
Aggregate Operators / 5.11.1: |
Higher-Order Features / 5.11.2: |
Bibliographic Notes / 5.12: |
A Logical Approach to Constraint Satisfaction / 6: |
Preliminaries / 6.1: |
The Computational Complexity of Constraint Satisfaction / 6.3: |
Nonuniform Constraint Satisfaction / 6.4: |
Monotone Monadic SNP and Nonuniform Constraint Satisfaction / 6.5: |
Datalog and Nonuniform Constraint Satisfaction / 6.6: |
Datalog, Games, and Constraint Satisfaction / 6.7: |
Games and Consistency / 6.8: |
Uniform Constraint Satisfaction and Bounded Treewidth / 6.9: |
Local Variations on a Loose Theme: Modal Logic and Decidability / 7: |
Modal Systems and Bisimulations / 7.1: |
Basic Modal Logic / 7.3: |
Notes / 7.3.1: |
Some Variations / 7.4: |
Neither Locality nor Looseness: Grid Logics / 7.4.1: |
Universal Access: K / 7.4.2: |
Generalizing Looseness: the Until Operator / 7.4.3: |
Modal Complexity / 7.5: |
NP and the Polysize Model Property / 7.5.1: |
PSPACE and Polynomially Deep Paths / 7.5.2: |
EXPTIME and Exponentially Deep Paths / 7.5.3: |
NEXPTIME / 7.5.4: |
Modal Logic and First-Order Logic / 7.5.5: |
Guarded Fragments / 7.6.1: |
Decidability and Complexity / 7.6.2: |
Index / 7.6.3: |
Unifying Themes in Finite Model Theory / 1: |
Definability Theory / 1.1: |
Classification of Concepts in Terms of Definitional Complexity / 1.1.1: |