Algorithms to compute probabilistic bisimilarity distances for labelled Markov chains

DOI10.4230/LIPICS.CONCUR.2017.27zbMATH Open1442.68152MaRDI QIDQ5111641FDOQ5111641

Qiyi Tang, Franck van Breugel

Publication date: 27 May 2020

Recommendations

• Deciding probabilistic bisimilarity distance one for labelled Markov chains
• Computing probabilistic bisimilarity distances via policy iteration
• On the complexity of computing probabilistic bisimilarity
• Computing probabilistic bisimilarity distances for probabilistic automata
• Deciding probabilistic bisimilarity distance one for probabilistic automata

zbMATH Keywords

policy iterationpseudometricprobabilistic bisimilaritylabelled Markov chain

Mathematics Subject Classification ID

Computational methods in Markov chains (60J22) 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)

Cites Work

• The complexity of stochastic games
• Title not available (Why is that?)
• Stochastic Games
• A polynomial time primal network simplex algorithm for minimum cost flows
• A lattice-theoretical fixpoint theorem and its applications
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Bisimulation through probabilistic testing
• A calculus of communicating systems
• Labelled Markov processes.
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• The Distribution of a Product from Several Sources to Numerous Localities
• Title not available (Why is that?)
• On Nonterminating Stochastic Games
• On the Complexity of Computing Probabilistic Bisimilarity
• Approximating a Behavioural Pseudometric without Discount for Probabilistic Systems
• The Complexity of Computing a Bisimilarity Pseudometric on Probabilistic Automata
• On-the-Fly Exact Computation of Bisimilarity Distances
• Computing Probabilistic Bisimilarity Distances via Policy Iteration

Cited In (8)

• Relative approximate bisimulations for fuzzy picture automata
• Sound approximate and asymptotic probabilistic bisimulations for PCTL
• Explainability of probabilistic bisimilarity distances for labelled Markov chains
• Deciding probabilistic bisimilarity distance one for labelled Markov chains
• On the metric-based approximate minimization of Markov chains
• Title not available (Why is that?)
• A monoidal view on fixpoint checks
• Computing bisimilarity metrics for probabilistic timed automata

This page was built for publication: Algorithms to compute probabilistic bisimilarity distances for labelled Markov chains

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