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-2 | Engels |
---|---|
Titel | 32nd International Conference on Concurrency Theory, CONCUR 2021 |
Redacteuren | Serge Haddad, Daniele Varacca |
Uitgeverij | Schloss Dagstuhl - Leibniz-Zentrum für Informatik |
Pagina's | 31:1-31:16 |
Aantal pagina's | 16 |
ISBN van elektronische versie | 9783959772037 |
DOI's | |
Status | Gepubliceerd - 1 aug. 2021 |
Evenement | 32nd International Conference on Concurrency Theory, CONCUR 2021 - Virtual, Online Duur: 24 aug. 2021 → 27 aug. 2021 |
Publicatie series
Naam | Leibniz International Proceedings in Informatics, LIPIcs |
---|---|
Volume | 203 |
ISSN van geprinte versie | 1868-8969 |
Congres
Congres | 32nd International Conference on Concurrency Theory, CONCUR 2021 |
---|---|
Stad | Virtual, Online |
Periode | 24/08/21 → 27/08/21 |
Bibliografische nota
Publisher Copyright:© 2021 Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. All rights reserved.