An efficient algorithm to determine probabilistic bisimulation

DOI10.3390/A11090131MaRDI QIDQ2633253zbMATH OpenOpenAlexWikidataFDO

Authors Jan Friso Groote, Jao Rivera Verduzco, Erik de Vink

Publication date 8 May 2019

Published in Algorithms (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.3390/a11090131

zbMATH Keywords

probabilistic bisimulationpartition-refinement algorithmprobabilistic labeled transition systemprobabilistic system with nondeterminism

Mathematics Subject Classification ID

Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Analysis of algorithms (68W40) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

Recommendations

• Deciding bisimilarity and similarity for probabilistic processes.
• Bisimulation and simulation algorithms on probabilistic transition systems by abstract interpretation
• Probabilistic bisimulation and simulation algorithms by abstract interpretation
• scientific article; zbMATH DE number 1927574
• An efficient algorithm for computing bisimulation equivalence

Cites work

• scientific article; zbMATH DE number 1927574 (Why is no real title available?)
• scientific article; zbMATH DE number 1754605 (Why is no real title available?)
• A logic for reasoning about time and reliability
• A space-efficient simulation algorithm on probabilistic automata
• An \(\mathcal O(m\log n)\) algorithm for computing stuttering equivalence and branching bisimulation
• An overview of the mCRL2 toolset and its recent advances
• Bisimulation Minimisation Mostly Speeds Up Probabilistic Model Checking
• Bisimulation and simulation algorithms on probabilistic transition systems by abstract interpretation
• Bisimulation through probabilistic testing
• CCS expressions, finite state processes, and three problems of equivalence
• Deciding bisimilarity and similarity for probabilistic processes.
• Exploring probabilistic bisimulations. I
• Flow Faster: Efficient Decision Algorithms for Probabilistic Simulations
• Modeling and analysis of communicating systems
• Optimal state-space lumping in Markov chains
• Polynomial time decision algorithms for probabilistic automata
• Problem solving using process algebra considered insightful
• SMT-based bisimulation minimisation of Markov models
• Simple \(O(m \log n)\) time Markov chain lumping
• Simple bisimilarity minimization in \(O(m \log n)\) time
• Stochastic model checking
• Three Partition Refinement Algorithms

Cited in

(12)

• Equivalence checking 40 years after: a review of bisimulation tools
• Bisimulation and simulation algorithms on probabilistic transition systems by abstract interpretation
• Lowerbounds for Bisimulation by Partition Refinement
• A Space-Efficient Probabilistic Simulation Algorithm
• An implementation of an efficient algorithm for bisimulation equivalence
• Probabilistic bisimulation and simulation algorithms by abstract interpretation
• Generic partition refinement and weighted tree automata
• scientific article; zbMATH DE number 1927574 (Why is no real title available?)
• scientific article; zbMATH DE number 7559464 (Why is no real title available?)
• From generic partition refinement to weighted tree automata minimization
• Efficient and modular coalgebraic partition refinement
• Explicit Hopcroft's trick in categorical partition refinement

Describes a project that uses

Uses Software

• mCRL2

This page was built for publication: An efficient algorithm to determine probabilistic bisimulation

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