Probabilistic weak simulation is decidable in polynomial time

DOI10.1016/J.IPL.2003.10.001zbMATH Open1183.68703DBLPjournals/ipl/BaierHK04OpenAlexW2006889545WikidataQ57801956 ScholiaQ57801956MaRDI QIDQ1029062FDOQ1029062

Authors: Christel Baier, Holger Hermanns, 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

Recommendations

• Deciding probabilistic automata weak bisimulation in polynomial time
• Decidability of weak simulation on one-counter nets
• Deciding probabilistic automata weak bisimulation: theory and practice
• scientific article; zbMATH DE number 1759621
• Weak bisimulation for probabilistic timed automata
• Probabilistic polynomial time is closed under parity reductions
• Pseudodeterministic algorithms and the structure of probabilistic time
• Deciding Simulations on Probabilistic Automata
• Computing weak consistency in polynomial time (extended abstract)
• The complexity of probabilistic verification

zbMATH Keywords

algorithmscomputational complexityperformance evaluationMarkov chainssimulation preorder

Mathematics Subject Classification ID

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Characterizing finite Kripke structures in propositional temporal logic
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Three Partition Refinement Algorithms
• Exact and ordinary lumpability in finite Markov chains
• Title not available (Why is that?)
• CONCUR 2003 - Concurrency Theory
• Deciding bisimilarity and similarity for probabilistic processes.
• Title not available (Why is that?)
• Branching time and abstraction in bisimulation semantics
• Optimal state-space lumping in Markov chains
• Revisiting interactive Markov chains
• Finite Continuous Time Markov Chains
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (11)

• Formal Verification of Differential Privacy for Interactive Systems (Extended Abstract)
• Lumpability abstractions of rule-based systems
• A space-efficient simulation algorithm on probabilistic automata
• A probabilistic calculus of cyber-physical systems
• Quantitative simulations by matrices
• Deciding probabilistic bisimilarity over infinite-state probabilistic systems
• Flow Faster: Efficient Decision Algorithms for Probabilistic Simulations
• Bisimulation and Simulation Relations for Markov Chains
• Comparative branching-time semantics for Markov chains
• Compositional weak metrics for group key update
• Title not available (Why is that?)

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

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