Probabilistic weak simulation is decidable in polynomial time

DOI10.1016/J.IPL.2003.10.001MaRDI QIDQ1029062zbMATH OpenOpenAlexDBLPWikidataFDO

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

zbMATH Keywords

algorithmscomputational complexityMarkov chainsperformance evaluationsimulation preorder

Mathematics Subject Classification ID

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

Cites work

• Branching time and abstraction in bisimulation semantics
• Characterizing finite Kripke structures in propositional temporal logic
• CONCUR 2003 - Concurrency Theory
• Deciding bisimilarity and similarity for probabilistic processes.
• Exact and ordinary lumpability in finite Markov chains
• Finite Continuous Time Markov Chains
• scientific article; zbMATH DE number 1701760 (Why is no real title available?)
• scientific article; zbMATH DE number 1705168 (Why is no real title available?)
• scientific article; zbMATH DE number 4179422 (Why is no real title available?)
• scientific article; zbMATH DE number 4089320 (Why is no real title available?)
• scientific article; zbMATH DE number 42752 (Why is no real title available?)
• scientific article; zbMATH DE number 149518 (Why is no real title available?)
• scientific article; zbMATH DE number 1219584 (Why is no real title available?)
• scientific article; zbMATH DE number 1306878 (Why is no real title available?)
• scientific article; zbMATH DE number 1325007 (Why is no real title available?)
• scientific article; zbMATH DE number 700091 (Why is no real title available?)
• scientific article; zbMATH DE number 2080064 (Why is no real title available?)
• scientific article; zbMATH DE number 1927572 (Why is no real title available?)
• scientific article; zbMATH DE number 1927574 (Why is no real title available?)
• scientific article; zbMATH DE number 1512606 (Why is no real title available?)
• scientific article; zbMATH DE number 1759621 (Why is no real title available?)
• Optimal state-space lumping in Markov chains
• Revisiting interactive Markov chains
• Three Partition Refinement Algorithms

Cited in

(11)

• A probabilistic calculus of cyber-physical systems
• Comparative branching-time semantics for Markov chains
• Deciding probabilistic bisimilarity over infinite-state probabilistic systems
• A space-efficient simulation algorithm on probabilistic automata
• Lumpability abstractions of rule-based systems
• Equational reasonings in wireless network gossip protocols
• Compositional weak metrics for group key update
• Bisimulation and Simulation Relations for Markov Chains
• Formal verification of differential privacy for interactive systems (extended abstract)
• Flow Faster: Efficient Decision Algorithms for Probabilistic Simulations
• Quantitative simulations by matrices

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)