The complexity of computing a bisimilarity pseudometric on probabilistic automata

DOI10.1007/978-3-319-06880-0_10MaRDI QIDQ5418964zbMATH OpenOpenAlexFDO

Authors Franck van Breugel, James Worrell

Publication date 2 June 2014

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-319-06880-0_10

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Stochastic games, stochastic differential games (91A15) Applications of game theory (91A80)

Recommendations

• On the complexity of computing probabilistic bisimilarity
• Computing probabilistic bisimilarity distances for probabilistic automata
• Deciding probabilistic bisimilarity distance one for probabilistic automata
• Deciding probabilistic bisimilarity distance one for probabilistic automata
• On metrics for probabilistic systems: definitions and algorithms

Cites work

• A hierarchy of probabilistic system types
• A lattice-theoretical fixpoint theorem and its applications
• Algorithms for Game Metrics
• An introduction to metric semantics: Operational and denotational models for programming and specification languages
• Bisimulation for labelled Markov processes
• Bisimulation through probabilistic testing
• Computational aspects of equilibria
• Computing Game Metrics on Markov Decision Processes
• Equilibrium Points of Bimatrix Games
• Game Refinement Relations and Metrics
• Geometric approximation algorithms
• scientific article; zbMATH DE number 3134565 (Why is no real title available?)
• scientific article; zbMATH DE number 3964277 (Why is no real title available?)
• scientific article; zbMATH DE number 4089320 (Why is no real title available?)
• scientific article; zbMATH DE number 18531 (Why is no real title available?)
• scientific article; zbMATH DE number 1231637 (Why is no real title available?)
• scientific article; zbMATH DE number 1361128 (Why is no real title available?)
• scientific article; zbMATH DE number 1049043 (Why is no real title available?)
• scientific article; zbMATH DE number 1113628 (Why is no real title available?)
• scientific article; zbMATH DE number 1497869 (Why is no real title available?)
• scientific article; zbMATH DE number 1754609 (Why is no real title available?)
• scientific article; zbMATH DE number 794262 (Why is no real title available?)
• scientific article; zbMATH DE number 5585443 (Why is no real title available?)
• scientific article; zbMATH DE number 6783433 (Why is no real title available?)
• scientific article; zbMATH DE number 3068536 (Why is no real title available?)
• Introduction to coalgebra. Towards mathematics of states and observation
• Labelled Markov processes.
• Matrices
• Modal and temporal properties of processes
• Network flows. Theory, algorithms, and applications.
• On behavioural pseudometrics and closure ordinals
• On the complexity of computing probabilistic bisimilarity
• On the Complexity of Nash Equilibria and Other Fixed Points
• On the complexity of the parity argument and other inefficient proofs of existence
• On-the-fly exact computation of bisimilarity distances
• Probability and Computing
• Recursively defined metric spaces without contraction
• Reducibility among Fractional Stability Problems
• Stochastic Games
• Stochastic Games with Perfect Information and Time Average Payoff
• The Approximation of Fixed Points of a Continuous Mapping
• The complexity of stochastic games

Cited in

(16)

• On the computational complexity of approximating distributions by probabilistic automata
• Bisimulation metrics and norms for real-weighted automata
• Computing branching distances with quantitative games
• Deciding probabilistic bisimilarity distance one for probabilistic automata
• Expressiveness of probabilistic modal logics: a gradual approach
• Algorithms for game metrics
• On the complexity of computing probabilistic bisimilarity
• On the Complexity of the Equivalence Problem for Probabilistic Automata
• L_p DISTANCE AND EQUIVALENCE OF PROBABILISTIC AUTOMATA
• Deciding probabilistic bisimilarity distance one for probabilistic automata
• Bisimulation metrics for weighted automata
• Algorithms to compute probabilistic bisimilarity distances for labelled Markov chains
• Computing probabilistic bisimilarity distances for probabilistic automata
• Computing probabilistic bisimilarity distances for probabilistic automata
• Sound approximate and asymptotic probabilistic bisimulations for PCTL
• Computing bisimilarity metrics for probabilistic timed automata

This page was built for publication: The complexity of computing a bisimilarity pseudometric on probabilistic automata

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