# Approximate Bisimulation Minimisation

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

## Key facts

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

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

- [Computing Fixpoints of Learned Functions: Chaotic Iteration and Simple Stochastic Games](https://mlsanity.com/paper/2601.16142/) (2026)
- [Approximate Homomorphisms and Convergent Representations in Transducers](https://mlsanity.com/paper/2608.20428/) (2026)

## Abstract (arXiv)

We propose polynomial-time algorithms to minimise labelled Markov chains whose transition probabilities are not known exactly, have been perturbed, or can only be obtained by sampling. Our algorithms are based on a new notion of an approximate bisimulation quotient, obtained by lumping together states that are exactly bisimilar in a slightly perturbed system. We present experiments that show that our algorithms are able to recover the structure of the bisimulation quotient of the unperturbed system.