On the Complexity of Computing Probabilistic Bisimilarity

DOI10.1007/978-3-642-28729-9_29zbMath1352.68096OpenAlexW176827812MaRDI QIDQ2892788

Di Chen, James Worrell, Franck Van Breugel

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

Analysis of algorithms and problem complexity (68Q25) Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.) (60J20) 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)

Related Items (20)

Converging from branching to linear metrics on Markov chains ⋮ Unnamed Item ⋮ Addendum to ``Recursively defined metric spaces without contraction ⋮ Explainability of probabilistic bisimilarity distances for labelled Markov chains ⋮ A Hemimetric Extension of Simulation for Semi-Markov Decision Processes ⋮ Convex lattice equation systems ⋮ Sound approximate and asymptotic probabilistic bisimulations for PCTL ⋮ Unnamed Item ⋮ On the Relationship Between Bisimulation and Trace Equivalence in an Approximate Probabilistic Context ⋮ On Computing the Total Variation Distance of Hidden Markov Models. ⋮ Asymmetric Distances for Approximate Differential Privacy ⋮ (Metric) Bisimulation Games and Real-Valued Modal Logics for Coalgebras ⋮ Polynomial-time algorithms for computing distances of fuzzy transition systems ⋮ The Complexity of Computing a Bisimilarity Pseudometric on Probabilistic Automata ⋮ Bisimulation for Markov Decision Processes through Families of Functional Expressions ⋮ Unnamed Item ⋮ Unnamed Item ⋮ On the metric-based approximate minimization of Markov chains ⋮ Unnamed Item ⋮ Deciding probabilistic bisimilarity distance one for probabilistic automata

This page was built for publication: On the Complexity of Computing Probabilistic Bisimilarity