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

DOI10.1007/978-3-030-45237-7_1MaRDI QIDQ5164166zbMATHOpenAlexFDO

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

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)

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

Cites work

• 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?)
• A calculus of communicating systems
• 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
• 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
• Three Partition Refinement Algorithms
• Three logics for branching bisimulation

Cited in

(18)

• Apartness and distinguishing formulas in Hennessy-Milner logic
• Equivalence checking 40 years after: a review of bisimulation tools
• Causal Semantics for BPP Nets with Silent Moves
• Lowerbounds for Bisimulation by Partition Refinement
• Minimisation of spatial models using branching bisimilarity
• Bisimilarity Minimization in O(m logn) Time
• An algorithm for reducing binary branchings
• An \(\mathcal O(m\log n)\) algorithm for computing stuttering equivalence and branching bisimulation
• scientific article; zbMATH DE number 177845 (Why is no real title available?)
• An implementation of an efficient algorithm for bisimulation equivalence
• Branching bisimulation semantics enables noninterference analysis of reversible systems
• An \(O(m\log n)\) algorithm for stuttering equivalence and branching bisimulation
• scientific article; zbMATH DE number 7559464 (Why is no real title available?)
• Team equivalences for finite-state machines with silent moves
• Compositional verification of priority systems using sharp bisimulation
• Operational Determinism and Fast Algorithms
• CRYSTAL framework: cybersecurity assurance for cyber-physical systems
• Simple bisimilarity minimization in \(O(m \log n)\) time

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)