An O(m n) algorithm for branching bisimilarity on labelled transition systems
DOI10.1007/978-3-030-45237-7_1zbMATH Open1483.68232OpenAlexW2980227841MaRDI QIDQ5164166FDOQ5164166
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)
Full work available at URL: https://doi.org/10.1007/978-3-030-45237-7_1
Recommendations
- An \(\mathcal O(m\log n)\) algorithm for computing stuttering equivalence and branching bisimulation
- Bisimilarity Minimization in O(m logn) Time
- Simple bisimilarity minimization in \(O(m \log n)\) time
- An implementation of an efficient algorithm for bisimulation equivalence
- An \(O(m\log n)\) algorithm for stuttering equivalence and branching bisimulation
Analysis of algorithms (68W40) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)
Cites Work
- Three Partition Refinement Algorithms
- A calculus of communicating systems
- CCS expressions, finite state processes, and three problems of equivalence
- Branching time and abstraction in bisimulation semantics
- Title not available (Why is that?)
- Three logics for branching bisimulation
- Bisimilarity Minimization in O(m logn) Time
- Efficient minimization of DFAs with partial transition
- Title not available (Why is that?)
- Title not available (Why is that?)
- An \(O(m\log n)\) algorithm for stuttering equivalence and branching bisimulation
- An \(\mathcal O(m\log n)\) algorithm for computing stuttering equivalence and branching bisimulation
- Distributed branching bisimulation reduction of state spaces
Cited In (18)
- CRYSTAL framework: cybersecurity assurance for cyber-physical systems
- Compositional verification of priority systems using sharp bisimulation
- Lowerbounds for Bisimulation by Partition Refinement
- Apartness and distinguishing formulas in Hennessy-Milner logic
- Equivalence checking 40 years after: a review of bisimulation tools
- An \(O(m\log n)\) algorithm for stuttering equivalence and branching bisimulation
- An algorithm for reducing binary branchings
- Simple bisimilarity minimization in \(O(m \log n)\) time
- Team equivalences for finite-state machines with silent moves
- Title not available (Why is that?)
- Causal Semantics for BPP Nets with Silent Moves
- Operational Determinism and Fast Algorithms
- An implementation of an efficient algorithm for bisimulation equivalence
- Branching bisimulation semantics enables noninterference analysis of reversible systems
- Title not available (Why is that?)
- Minimisation of spatial models using branching bisimilarity
- Bisimilarity Minimization in O(m logn) Time
- An \(\mathcal O(m\log n)\) algorithm for computing stuttering equivalence and branching bisimulation
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)
