Bisimulation by Partitioning Is Ω((m+n) logn)

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

3 Citaten (Scopus)


An asymptotic lowerbound of Ω((m+n)logn) is established for partition refinement algorithms that decide bisimilarity on labeled transition systems. The lowerbound is obtained by subsequently analysing two families of deterministic transition systems - one with a growing action set and another with a fixed action set. For deterministic transition systems with a one-letter action set, bisimilarity can be decided with fundamentally different techniques than partition refinement. In particular, Paige, Tarjan, and Bonic give a linear algorithm for this specific situation. We show, exploiting the concept of an oracle, that the approach of Paige, Tarjan, and Bonic is not of help to develop a generic algorithm for deciding bisimilarity on labeled transition systems that is faster than the established lowerbound of Ω((m+n)logn).

Originele taal-2Engels
Titel32nd International Conference on Concurrency Theory, CONCUR 2021
RedacteurenSerge Haddad, Daniele Varacca
UitgeverijSchloss Dagstuhl - Leibniz-Zentrum für Informatik
Aantal pagina's16
ISBN van elektronische versie9783959772037
StatusGepubliceerd - 1 aug. 2021
Evenement32nd International Conference on Concurrency Theory, CONCUR 2021 - Virtual, Online
Duur: 24 aug. 202127 aug. 2021

Publicatie series

NaamLeibniz International Proceedings in Informatics, LIPIcs
ISSN van geprinte versie1868-8969


Congres32nd International Conference on Concurrency Theory, CONCUR 2021
StadVirtual, Online

Bibliografische nota

Publisher Copyright:
© 2021 Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. All rights reserved.


Duik in de onderzoeksthema's van 'Bisimulation by Partitioning Is Ω((m+n) logn)'. Samen vormen ze een unieke vingerafdruk.

Citeer dit