An O(m log n) algorithm for branching bisimilarity on labelled transition systems

DOI10.1007/978-3-030-45237-7_1zbMath1483.68232OpenAlexW2980227841MaRDI QIDQ5164166

Jan Friso Groote, David N. Jansen, Jeroen J. A. Keiren, Anton Wijs

Publication date: 10 November 2021

Published in: Tools and Algorithms for the Construction and Analysis of Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-030-45237-7_1

zbMATH Keywords

algorithmlabelled transition systemsbranching bisimilarity

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

Related Items

Lowerbounds for Bisimulation by Partition Refinement, Equivalence checking 40 years after: a review of bisimulation tools, Apartness and distinguishing formulas in Hennessy-Milner logic, Minimisation of spatial models using branching bisimilarity, Team equivalences for finite-state machines with silent moves, Causal Semantics for BPP Nets with Silent Moves, Unnamed Item

Cites Work

• CCS expressions, finite state processes, and three problems of equivalence
• A calculus of communicating systems
• An \(O(m\log n)\) algorithm for stuttering equivalence and branching bisimulation
• Bisimilarity Minimization in O(m logn) Time
• Three Partition Refinement Algorithms
• Three logics for branching bisimulation
• Branching time and abstraction in bisimulation semantics
• Efficient Minimization of DFAs with Partial Transition Functions
• An O ( m log n ) Algorithm for Computing Stuttering Equivalence and Branching Bisimulation
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item