Christof Löding
Title: Definability questions
for MSO
Abstract:
A famous result by Rabin states that monadic second-order logic (MSO)
on the infinite binary tree is decidable. This result makes MSO on the
infinite binary tree an interesting logic and motivates the study of
its expressive power. In this talk we present natural objects that
cannot be defined in MSO, in particular choice functions and
well-orderings over the infinite binary tree, and we give some
examples how these generic results can be used for other definability
questions and to solve questions about automata on infinite trees.