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

DOI10.1007/978-3-030-45237-7_1MaRDI QIDQ5164166zbMATH OpenOpenAlexFDO

Authors David N. Jansen, Jan Friso Groote, 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)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

algorithmbranching bisimilaritylabelled transition systems

Mathematics Subject Classification ID

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

Recommendations

• An O(m n) algorithm for computing stuttering equivalence and branching bisimulation
• Bisimilarity Minimization in O(m logn) Time
• Simple bisimilarity minimization in O(m n) time
• An implementation of an efficient algorithm for bisimulation equivalence
• An \(O(m\log n)\) algorithm for stuttering equivalence and branching bisimulation

Cites work

• A calculus of communicating systems
• An O(m n) algorithm for computing stuttering equivalence and branching bisimulation
• An \(O(m\log n)\) algorithm for stuttering equivalence and branching bisimulation
• Bisimilarity Minimization in O(m logn) Time
• Branching time and abstraction in bisimulation semantics
• CCS expressions, finite state processes, and three problems of equivalence
• Distributed branching bisimulation reduction of state spaces
• Efficient minimization of DFAs with partial transition
• scientific article; zbMATH DE number 177845 (Why is no real title available?)
• scientific article; zbMATH DE number 3460178 (Why is no real title available?)
• scientific article; zbMATH DE number 1306878 (Why is no real title available?)
• Three logics for branching bisimulation
• Three Partition Refinement Algorithms

Cited in

(24)

• Essential transitions to bisimulation equivalences
• Team equivalences for finite-state machines with silent moves
• An \(O(m\log n)\) algorithm for stuttering equivalence and branching bisimulation
• An algorithm for reducing binary branchings
• Simple bisimilarity minimization in O(m n) time
• Bisimilarity Minimization in O(m logn) Time
• scientific article; zbMATH DE number 177845 (Why is no real title available?)
• scientific article; zbMATH DE number 7559464 (Why is no real title available?)
• Causal Semantics for BPP Nets with Silent Moves
• An O(m n) algorithm for computing stuttering equivalence and branching bisimulation
• Operational Determinism and Fast Algorithms
• 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
• Branching bisimulation semantics enables noninterference analysis of reversible systems
• CRYSTAL framework: cybersecurity assurance for cyber-physical systems
• Compositional verification of priority systems using sharp bisimulation
• Positive Hennessy-Milner logic for branching bisimulation
• The reachable simulation problem
• Minimal depth distinguishing formulas without until for branching bisimulation
• Noninterference analysis of reversible systems: an approach based on branching bisimilarity
• Title not available (Why is no real title available?)
• An implementation of an efficient algorithm for bisimulation equivalence

This page was built for publication: An \(O(m \log n)\) algorithm for branching bisimilarity on labelled transition systems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5164166)