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 briefly discussed and tested. Our algorithm reaches, in particular cases, a linear solution.
A Fast Bisimulation Algorithm
DOVIER, Agostino;PIAZZA, Carla;POLICRITI, Alberto
2001-01-01
Abstract
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 briefly discussed and tested. Our algorithm reaches, in particular cases, a linear solution.File in questo prodotto:
Non ci sono file associati a questo prodotto.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
