The automata method for the MSO theory of order
Jeudi 30 avril 2026, 14:00 à 15:00
salle de séminaire du département d'informatique
(Université de Kaiserslautern-Landau)
In this talk, I will survey how automata and games can be used to obtain decidability results for the logic MSO. I will review classic results such as Büchi's and Rabin's theorems on the decidability of MSO over the naturals, rationals and the full binary tree. In contrast, in 1975, Shelah proved that the MSO theory of the reals is undecidable. He left open whether decidability can be recovered by restricting quantifications to Borel sets. I will discuss recent advances on this question, including a joint work with Mikołaj Bojańczyk, Sven Manthe and Paweł Parys where we introduce an automata model for Borel-MSO over infinite trees.