The Complexity of Computing a Bisimilarity Pseudometric on Probabilistic Automata

DOI10.1007/978-3-319-06880-0_10zbMath1407.68267OpenAlexW199912135MaRDI QIDQ5418964

James Worrell, Franck Van Breugel

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) Applications of game theory (91A80) Formal languages and automata (68Q45) Stochastic games, stochastic differential games (91A15)

Related Items (8)

Unnamed Item ⋮ Expressiveness of probabilistic modal logics: a gradual approach ⋮ Sound approximate and asymptotic probabilistic bisimulations for PCTL ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Computing branching distances with quantitative games ⋮ Unnamed Item ⋮ Deciding probabilistic bisimilarity distance one for probabilistic automata

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On behavioural pseudometrics and closure ordinals
• Bisimulation through probabilistic testing
• The complexity of stochastic games
• On the complexity of the parity argument and other inefficient proofs of existence
• Recursively defined metric spaces without contraction
• Bisimulation for labelled Markov processes
• A lattice-theoretical fixpoint theorem and its applications
• Introduction to Coalgebra
• On the Complexity of Computing Probabilistic Bisimilarity
• On the Complexity of Nash Equilibria and Other Fixed Points
• Matrices
• Algorithms for Game Metrics
• Computing Game Metrics on Markov Decision Processes
• Game Refinement Relations and Metrics
• Computational Aspects of Equilibria
• Reducibility among Fractional Stability Problems
• On-the-Fly Exact Computation of Bisimilarity Distances
• Equilibrium Points of Bimatrix Games
• Probability and Computing
• The Approximation of Fixed Points of a Continuous Mapping
• Stochastic Games with Perfect Information and Time Average Payoff
• Stochastic Games
• An introduction to metric semantics: Operational and denotational models for programming and specification languages
• Modal and temporal properties of processes

This page was built for publication: The Complexity of Computing a Bisimilarity Pseudometric on Probabilistic Automata