Probabilistic weak simulation is decidable in polynomial time

Christel BaierChristel Baier, Holger HermannsHolger Hermanns, Joost-Pieter KatoenJoost-Pieter Katoen

DOI Link

Christel Baier, Holger Hermanns, Joost-Pieter Katoen
Probabilistic weak simulation is decidable in polynomial time
Information Processing Letters, 89(3):123--130, 2004

Details
Bibtex

KurzfassungAbstract
This paper considers a weak simulation preorder for Markov chains that allows for stuttering. Despite the second-order quantification in its definition, we present a polynomial-time algorithm to compute the weak simulation preorder of a finite Markov chain.
Forschungsgruppe:Research Group: Verifikation und formale quantitative Analyse„Verifikation und formale quantitative Analyse“ befindet sich nicht in der Liste (Computational Logic, Automatentheorie, Wissensverarbeitung, Knowledge-Based Systems, Knowledge Systems, Wissensbasierte Systeme, Logische Programmierung und Argumentation, Algebra und Diskrete Strukturen, Knowledge-aware Artificial Intelligence, Algebraische und logische Grundlagen der Informatik) zulässiger Werte für das Attribut „Forschungsgruppe“.Algebraic and Logical Foundations of Computer Science

@article{BHK2004,
  author  = {Christel Baier and Holger Hermanns and Joost-Pieter Katoen},
  title   = {Probabilistic weak simulation is decidable in polynomial time},
  journal = {Information Processing Letters},
  volume  = {89},
  number  = {3},
  year    = {2004},
  pages   = {123--130},
  doi     = {10.1016/j.ipl.2003.10.001}
}