Monadic Second-Order Model Theory

Fundamentals124
Logics124  and Their Expressive Powers124
Structures and logics
Simple translations between logics
Theories and back-and-forth arguments
Operations for monadic second-order logic
Operations for first-order logic
Finite Words124
Words and languages
Semigroups and Green\'s relations
Simon\'s Lemma
Regular languages of finite words
First-order logic
Infinite Words124
Ramsey theory
The theory of
-semigroups
-automata
Parity Games124
Positional games
Reachability games
Gale-Steward games
Regular games and parity games
The modal -calculus
Trees124
Composition theorems
Tree automata
The Muchnik Iteration
Löwenheim-Skolem theorems
The Cantor Topology
Counting quantifiers
Structure Theory
Linear Orders124
Dense and scattered orders
Partition theorems
Interpretations
Regular linear orders
Choice functions
Uniformisation
First-order logic
Sparse Structures124
Spanning forests
Sparse hypergraphs
Translating GSO into MSO
Sparse distributions
Tree-Width and Graph Minors124
Tree-decompositions
Minors
Brambles
The Excluded Grid Theorem
Branch-decompositions and tangles
Well-quasi-orderings
Crossing-Width
Partitions and ranks
Decompositions
Term
Tree-width and crossing-width
Interpretations
Non-standard crossing-width
Guarded Second-Order Transductions124
Transductions
Tree-decompositions
Trees of bounded height
The Transduction Hierarchy
Defining tree-decompositions
Applications124
Automatic Structures124
Automatic presentations
Interpretations
Closure properties
Undecidability
Injective presentations
Partition theorems
Counting quantifiers
Proving non-automaticity
Automatic groups
Automatic semirings
Automatic partial orders
Bibliography
Symbol Index
Index