← All papers
First page of Automata for MSO over Infinite Trees with Quantification over Borel Sets of Branches

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
Most of the paper's results on automata and prioritized Borel games were formalized in Lean using the Aristotle tool, provided as ancillary material.
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.

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.

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.

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.