An implementation of an efficient algorithm for bisimulation equivalence
type: Item
instance of: scholarly article
title: An implementation of an efficient algorithm for bisimulation equivalence
zbMATH Open document ID: 0711.68058
DOI: 10.1016/0167-6423(90)90071-K
author: Jean-Claude Fernandez
published in: Science of Computer Programming
publication date: 1990-01-01T00:00:00Z
review text: The standard bisimulation equivalence test is O(mn) for a labelled transition system with m transitions and n states. \textit{R. Paige} and \textit{R. Tarjan} [SIAM J. Comput. 16, 973-989 (1987; Zbl 0654.68072)] gives an O(m log n) algorithm for the relational coarsest partition problem. The author defines the bisimulation equivalent in terms of the relational coarsest partition problem and modifies the Paige-Tarjan algorithm to be used for bisimulation equivalence.
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68Q85
zbMATH DE Number: 4170103
reviewed by: Ryszard Janicki
MaRDI profile type: Publication
full work available at URL: 0167-6423(90)90071-k
OpenAlex ID: W1973642705
description: scientific article; zbMATH DE number 4170103