A Fast Bisimulation Algorithm

Agostino Dovier, Carla Piazza, and Alberto Policriti

To appear at 13th Conference on Computer-Aided Verification (CAV01), Paris, France, 18-22 July 2001


In this paper we propose an efficient algorithmic solution to the problem of determining a Bisimulation Relation on a finite structure. Starting from a set-theoretic point of view we propose an algorithm that optimizes the solution to the Relational Coarsest Partition problem given by Paige and Tarjan in 1987 and its use in model-checking packages is discussed and tested. Our algorithm reaches, in particular cases, a linear solution. Keywords: Bisimulation, Automata, Verification.

Server START Conference Manager
Update Time 28 Mar 2001 at 08:36:01
Maintainer www-cav01@lsv.ens-cachan.fr.
Start Conference Manager
Conference Systems