Lowerbounds for Bisimulation by Partition Refinement

DOI10.46298/lmcs-19(2:10)2023arXiv2203.07158OpenAlexW4382475481MaRDI QIDQ6135758

Jan Martens, Jan Friso Groote, E. P. de Vink

Publication date: 26 August 2023

Published in: Logical Methods in Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2203.07158

zbMATH Keywords

labelled transition systempartition refinementbisimilaritylowerbound

Mathematics Subject Classification ID

Logic in computer science (03B70) Computer science (68-XX)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• CCS expressions, finite state processes, and three problems of equivalence
• A linear time solution to the single function coarsest partition problem
• A calculus of communicating systems
• Partitioning a graph in \(O(|A|\log_ 2|V|)\)
• Exact performance equivalence: An equivalence relation for stochastic automata
• An efficient parallel algorithm for the single function coarsest partition problem
• An efficient algorithm for computing bisimulation equivalence
• Tight lower and upper bounds for the complexity of canonical colour refinement
• An efficient algorithm to determine probabilistic bisimulation
• Simulation of Parallel Random Access Machines by Circuits
• Hopcroft’s Algorithm and Cyclic Automata
• Three Partition Refinement Algorithms
• Fast Pattern Matching in Strings
• An O(m log n) algorithm for branching bisimilarity on labelled transition systems
• Implementation and Application of Automata
• Bisimulation by Partitioning Is Ω((m+n)log n).