Fast Coalgebraic Bisimilarity Minimization

on YouTube ↗26m

" summary

Minimizes coalgebras (DFAs, transition systems, probabilistic/weighted automata) by repeatedly refining states via computed signatures and reusing unchanged results, making at most O(m log n) functor calls where n is states and m transitions and with an extra factor for the functor action cost. It works for arbitrary computable functors (needs predecessors and a signature routine), often uses low memory usage in benchmarks, and the implementation Bora frequently beats specialized tools despite losing a small asymptotic factor.

AI-written summary · about

" chapters (15)

1. 0:00Introduction
2. 1:26Paper contributions
3. 3:14Automata and functor specs
4. 4:17Automata as coalgebras
5. 6:44Bisimilarity minimization explained
6. 7:47Algorithm sketch
7. 9:55Algorithm walkthrough
8. 11:40Complexity analysis
9. 13:47Data structures overhead
10. 14:30Comparison with prior work
11. 15:57Benchmark results
12. 17:42Cost of generality
13. 19:26Future work
14. 20:28Rust generics optimization
15. 20:48Q&A