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

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

1 Citaat (Scopus)

Samenvatting

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
Pagina's31:1-31:16
Aantal pagina's16
ISBN van elektronische versie9783959772037
DOI's
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
Volume203
ISSN van geprinte versie1868-8969

Congres

Congres32nd International Conference on Concurrency Theory, CONCUR 2021
StadVirtual, Online
Periode24/08/2127/08/21

Bibliografische nota

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

Citeer dit