We propose an efficient algorithmic solution to the problem of determining a Bisimulation Relation on a finite structure working both on the explicit and on the implicit (symbolic) representation. As far as the explicit case is concerned, 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 (SIAM J. Comput. 16(6) (1987) 973); its use in model-checking packages is also discussed and tested. For well-structured graphs our algorithm reaches a linear worst-case behaviour. The proposed algorithm is then re-elaborated to produce a symbolic version. © 2003 Elsevier B.V. All rights reserved.

An Efficient Algorithm for Computing Bisimulation Equivalence

DOVIER, Agostino;PIAZZA, Carla;POLICRITI, Alberto
2004

Abstract

We propose an efficient algorithmic solution to the problem of determining a Bisimulation Relation on a finite structure working both on the explicit and on the implicit (symbolic) representation. As far as the explicit case is concerned, 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 (SIAM J. Comput. 16(6) (1987) 973); its use in model-checking packages is also discussed and tested. For well-structured graphs our algorithm reaches a linear worst-case behaviour. The proposed algorithm is then re-elaborated to produce a symbolic version. © 2003 Elsevier B.V. All rights reserved.
File in questo prodotto:
File Dimensione Formato  
tcs04_dpp_ufficiale.pdf

non disponibili

Descrizione: Editorial version
Tipologia: Versione Editoriale (PDF)
Licenza: Non pubblico
Dimensione 612.54 kB
Formato Adobe PDF
612.54 kB Adobe PDF   Visualizza/Apri   Richiedi una copia
tcs959.pdf

accesso aperto

Descrizione: Post Print
Tipologia: Documento in Post-print
Licenza: Creative commons
Dimensione 457.48 kB
Formato Adobe PDF
457.48 kB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11390/877173
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 112
  • ???jsp.display-item.citation.isi??? 79
social impact