BisPy: a Python package for the computation of the maximum bisimulation of directed graphs.

In this thesis I analyse three algorithms for the computation of maximum bisimulation, which I also implemented in the Python package BisPy (available here).

The PDF file is available here italian only. The slides which I used during the discussion of the thesis are here.

This is a reduced version of the list of references which I consulted:

• Saha, Diptikalyan. "An incremental bisimulation algorithm." International Conference on Foundations of Software Technology and Theoretical Computer Science. Springer, Berlin, Heidelberg, 2007. DOI
• Dovier, Agostino, Carla Piazza, and Alberto Policriti. "A fast bisimulation algorithm." International Conference on Computer Aided Verification. Springer, Berlin, Heidelberg, 2001. DOI
• Gentilini, Raffaella, Carla Piazza, and Alberto Policriti. "From bisimulation to simulation: Coarsest partition problems." Journal of Automated Reasoning 31.1 (2003): 73-103. DOI
• Paige, Robert, and Robert E. Tarjan. "Three partition refinement algorithms." SIAM Journal on Computing 16.6 (1987): 973-989. DOI
• Hopcroft, John. "An n log n algorithm for minimizing states in a finite automaton." Theory of machines and computations. Academic Press, 1971. 189-196.
• Aczel, Peter. "Non-well-founded sets." (1988).
• Kanellakis, Paris C., and Scott A. Smolka. "CCS expressions, finite state processes, and three problems of equivalence." Information and computation 86.1 (1990): 43-68. DOI
• Sharir, Micha. "A strong-connectivity algorithm and its applications in data flow analysis." Computers & Mathematics with Applications 7.1 (1981): 67-72. DOI
• Cormen, Thomas H., et al. Introduction to algorithms. MIT press, 2009. (ISBN: 9780262533058)