# Tree algebras and bisimulation-invariant MSO on finite graphs

arXiv: https://arxiv.org/abs/2407.12677 · HTML: https://mlsanity.com/paper/2407.12677/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 Jul 2024.

## Built on by (most cited first, 2 of 2)

- [Halting Recurrent GNNs and the Graded μ-Calculus](https://mlsanity.com/paper/2505.11050/) (2025)
- [Recurrent Graph Neural Networks with Set-Based Aggregation](https://mlsanity.com/paper/2609.15932/) (2026)

## Abstract (arXiv)

We establish that the bisimulation invariant fragment of MSO over finite transition systems is expressively equivalent over finite transition systems to modal mu-calculus, a question that had remained open for several decades. The proof goes by translating the question to an algebraic framework, and showing that the languages of regular trees that are recognized by finitary tree algebras are the regular ones, ie. the ones expressible in mu-calculus. This corresponds for trees to a weak form of the key translation of Wilke algebras to omega-semigroup over infinite words, and was also a missing piece in the algebraic theory of regular languages of infinite trees for twenty years.