On the complexity of computing probabilistic bisimilarity

DOI10.1007/978-3-642-28729-9_29MaRDI QIDQ2892788zbMATH OpenOpenAlexFDO

Authors Di Chen, Franck van Breugel, James Worrell

Publication date 22 June 2012

Published in Foundations of Software Science and Computational Structures (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-28729-9_29

Mathematics Subject Classification ID

Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.) (60J20) Analysis of algorithms and problem complexity (68Q25) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Recommendations

• The complexity of computing a bisimilarity pseudometric on probabilistic automata
• Deciding probabilistic bisimilarity distance one for labelled Markov chains
• Computing probabilistic bisimilarity distances via policy iteration
• Algorithms to compute probabilistic bisimilarity distances for labelled Markov chains
• Deciding bisimilarity and similarity for probabilistic processes.

Cited in

(34)

• Polynomial-time algorithms for computing distances of fuzzy transition systems
• On the metric-based approximate minimization of Markov chains
• BPA bisimilarity is EXPTIME-hard
• Deciding probabilistic bisimilarity distance one for probabilistic automata
• Computing behavioral distances, compositionally
• On the relationship between bisimulation and trace equivalence in an approximate probabilistic context
• On Bisimilarity and Substitution in Presence of Replication
• Addendum to ``Recursively defined metric spaces without contraction
• Game characterization of probabilistic bisimilarity, and applications to pushdown automata
• scientific article; zbMATH DE number 6987095 (Why is no real title available?)
• Converging from branching to linear metrics on Markov chains
• Computing probabilistic bisimilarity distances via policy iteration
• On computing the total variation distance of hidden Markov models
• Deciding probabilistic bisimilarity distance one for probabilistic automata
• (Metric) bisimulation games and real-valued modal logics for coalgebras
• Algorithms to compute probabilistic bisimilarity distances for labelled Markov chains
• On-the-fly computation of bisimilarity distances
• On-the-fly exact computation of bisimilarity distances
• The complexity of computing a bisimilarity pseudometric on probabilistic automata
• Bisimulation for Markov decision processes through families of functional expressions
• Computing probabilistic bisimilarity distances for probabilistic automata
• Asymmetric Distances for Approximate Differential Privacy
• Computation of Kullback-Leibler divergence between labeled stochastic systems with non-identical state spaces
• Explainability of probabilistic bisimilarity distances for labelled Markov chains
• A Hemimetric Extension of Simulation for Semi-Markov Decision Processes
• Convex lattice equation systems
• BLOOM: bimodal lattice one-out-of-many proofs and applications
• Sound approximate and asymptotic probabilistic bisimulations for PCTL
• A monoidal view on fixpoint checks
• Computing bisimilarity metrics for probabilistic timed automata
• Comparing labelled Markov decision processes
• Minimising the probabilistic bisimilarity distance
• A monoidal view on fixpoint checks
• Explainability is a game for probabilistic bisimilarity distances

This page was built for publication: On the complexity of computing probabilistic bisimilarity

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