Probabilistic weak simulation is decidable in polynomial time

DOI10.1016/j.ipl.2003.10.001zbMath1183.68703OpenAlexW2006889545WikidataQ57801956 ScholiaQ57801956MaRDI QIDQ1029062

Holger Hermanns, Christel Baier, Joost-Pieter Katoen

Publication date: 9 July 2009

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2003.10.001

zbMATH Keywords

algorithmscomputational complexityMarkov chainsperformance evaluationsimulation preorder

Mathematics Subject Classification ID

Related Items (10)

A space-efficient simulation algorithm on probabilistic automata ⋮ Comparative branching-time semantics for Markov chains ⋮ Lumpability abstractions of rule-based systems ⋮ Deciding probabilistic bisimilarity over infinite-state probabilistic systems ⋮ Formal Verification of Differential Privacy for Interactive Systems (Extended Abstract) ⋮ Unnamed Item ⋮ Quantitative simulations by matrices ⋮ A probabilistic calculus of cyber-physical systems ⋮ Compositional weak metrics for group key update ⋮ Bisimulation and Simulation Relations for Markov Chains

Cites Work

• Optimal state-space lumping in Markov chains
• Characterizing finite Kripke structures in propositional temporal logic
• Deciding bisimilarity and similarity for probabilistic processes.
• Three Partition Refinement Algorithms
• Finite Continuous Time Markov Chains
• Exact and ordinary lumpability in finite Markov chains
• Branching time and abstraction in bisimulation semantics
• CONCUR 2003 - Concurrency Theory
• 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

This page was built for publication: Probabilistic weak simulation is decidable in polynomial time