Document Open Access Logo

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

Authors Jan Friso Groote , Jan Martens , Erik de Vink

PDF

File

Thumbnail PDF
PDF
LIPIcs.CONCUR.2021.31.pdf
  • Filesize: 0.77 MB
  • 16 pages

Document Identifiers

Subject Classification

ACM Subject Classification
  • Theory of computation
  • Theory of computation → Interactive computation
  • Theory of computation → Design and analysis of algorithms
Keywords
  • Bisimilarity
  • partition refinement
  • labeled transition system
  • lowerbound

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Abstract

An asymptotic lowerbound of Ω((m+n)log n) 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)log n).

Cite As Get BibTex

Jan Friso Groote, Jan Martens, and Erik de Vink. Bisimulation by Partitioning Is Ω((m+n)log n). In 32nd International Conference on Concurrency Theory (CONCUR 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 203, pp. 31:1-31:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.CONCUR.2021.31

Author Details

Jan Friso Groote
  • Eindhoven University of Technology, The Netherlands
Jan Martens
  • Eindhoven University of Technology, The Netherlands
Erik de Vink
  • Eindhoven University of Technology, The Netherlands

Funding

  • Martens, Jan: AVVA project NWO 612.001.751/TOP1.17.002.

Acknowledgements

We are grateful to the anonymous reviewers of CONCUR 2021 their thorough reading and constructive feedback.

References

  1. J. Balcázar, J. Gabarro, and M. Santha. Deciding bisimilarity is P-complete. Formal Aspects of Computing, 4(1):638-648, 1992. Google Scholar
  2. C. Berkholz, P. Bonsma, and M. Grohe. Tight lower and upper bounds for the complexity of canonical colour refinement. Theory of Computing Systems, 60(4):581-614, 2017. Google Scholar
  3. J. Berstel and O. Carton. On the complexity of Hopcroft’s state minimization algorithm. In M. Domaratzki et al., editor, Proc. CIAA 2004, pages 35-44. LNCS 3317, 2004. Google Scholar
  4. P. Buchholz. Exact performance equivalence: An equivalence relation for stochastic automata. Theoretical Computer Science, 215:263-287, 1999. URL: https://doi.org/10.1016/S0304-3975(98)00169-8.
  5. G. Castiglione, A. Restivo, and M. Sciortino. Hopcroft’s algorithm and cyclic automata. In C. Martín-Vide et al., editor, Proc. LATA 2008, pages 172-183. LNCS 5196, 2008. Google Scholar
  6. A. Dovier, C. Piazza, and A. Policriti. An efficient algorithm for computing bisimulation equivalence. Theoretical Computer Sciemce, 311:221-256, 2004. URL: https://doi.org/10.1016/S0304-3975(03)00361-X.
  7. J.F. Groote, H.J. Rivera Verduzco, and E.P. de Vink. An efficient algorithm to determine probabilistic bisimulation. Algorithms, 11(9):131,1-22, 2018. Google Scholar
  8. J. Hopcroft. An n log n algorithm for minimizing states in a finite automaton. In Z. Kohavi and A. Paz, editors, Theory of Machines and Computations, pages 189-196. Academic Press, 1971. Google Scholar
  9. J. Jájá and Kwan Woo Ryu. An efficient parallel algorithm for the single function coarsest partition problem. Theoretical Computer Science, 129(2):293-307, 1994. Google Scholar
  10. D.N. Jansen, J.F. Groote, J.J.A. Keiren, and A. Wijs. An O(m log n) algorithm for branching bisimilarity on labelled transition systems. In A. Biere and D. Parker, editors, Proc. TACAS, pages 3-20. LNCS 12079, 2020. URL: https://doi.org/10.1007/978-3-030-45237-7_1.
  11. P.C. Kanellakis and S.A. Smolka. CCS expressions, finite state processes, and three problems of equivalence. Information and Computation, 86(1):43-68, 1990. URL: https://doi.org/10.1016/0890-5401(90)90025-D.
  12. J. Martens, J.F. Groote, L. van de Haak, P. Hijma, and A. Wijs. A linear parallel algorithm to compute bisimulation and relational coarsest partitions. In preparation. Google Scholar
  13. R. Milner. A Calculus of Communicating Systems. LNCS 92, 1980. URL: https://doi.org/10.1007/3-540-10235-3.
  14. R. Paige and R.E. Tarjan. Three partition refinement algorithms. SIAM Journal on Computing, 16(6):973-989, 1987. Google Scholar
  15. R. Paige, R.E. Tarjan, and R. Bonic. A linear time solution to the single function coarsest partition problem. Theoretical Computer Science, 40:67-84, 1985. Google Scholar
  16. D.M.R. Park. Concurrency and automata on infinite sequences. In P. Deussen, editor, Proc. 5th GI-Conference on Theoretical Computer Science, pages 167-183. LNCS 104, 1981. URL: https://doi.org/10.1007/BFb0017309.
  17. S. Rajasekaran and I. Lee. Parallel algorithms for relational coarsest partition problems. IEEE Transactions on Parallel and Distrubuted Systems, 9(7):687-699, 1998. Google Scholar
  18. T. Wißmann, U. Dorsch, S. Milius, and L. Schröder. Efficient and modular coalgebraic partition refinement. Logical Methods Computer Science, 16(1), 2020. URL: https://doi.org/10.23638/LMCS-16(1:8)2020.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact