Automata for MSO over Infinite Trees with Quantification over Borel Sets of Branches
Mikołaj Bojańczyk, Antonio Casares, Sven Manthe, Paweł Parys
cs.FL
Nov 6, 2026 · v1
cs.LO
TL;DR
Most of the paper's results on automata and prioritized Borel games were formalized in Lean using the Aristotle tool, provided as ancillary material.
Abstract
Rabin's Tree Theorem says that the MSO theory of the infinite binary tree $2^*$ is decidable. Shelah showed that MSO logic becomes undecidable if this tree is extended to $2^{\le ω}$, i.e. by allowing quantification over sets of infinite branches. A longstanding open problem is whether the decidability can be recovered in $2^{\le ω}$ by restricting set quantification to Borel sets. We make some progress in this direction, by identifying a suitable automaton model, and showing that most of the automata-theoretic approach to Rabin's Theorem can be extended to the new framework. The only missing part is a conjecture about finite-memory determinacy in certain games. This paper states and explores the conjecture. We prove it in some restricted cases, and give lower bounds on the memory required in those games.
Problem
Shelah conjectured that the MSO theory of 2^{≤ω} becomes decidable when set quantification is restricted to Borel sets. A proof would have to generalize Rabin's Tree Theorem to this extended tree.
Approach
The authors define nondeterministic Muller automata on Borel trees and extend the automata-theoretic approach to Rabin's Theorem to this setting. Complementation of these automata reduces to a conjecture on finite-memory determinacy of prioritized Borel games. Most of the results were formalized in Lean with the help of the Aristotle tool.
Results
Most of the automata-theoretic pipeline carries over to the new setting, conditional on the finite-memory determinacy conjecture. The conjecture is proved in restricted cases, and lower bounds on the required memory are given. The Lean formalization uncovered several minor errors in the paper.