Probabilistic weak simulation is decidable in polynomial time
From International Center for Computational Logic
Probabilistic weak simulation is decidable in polynomial time
Christel BaierChristel Baier, Holger HermannsHolger Hermanns, Joost-Pieter KatoenJoost-Pieter Katoen
Christel Baier, Holger Hermanns, Joost-Pieter Katoen
Probabilistic weak simulation is decidable in polynomial time
Information Processing Letters, 89(3):123--130, 2004
Probabilistic weak simulation is decidable in polynomial time
Information Processing Letters, 89(3):123--130, 2004
- 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: Algebraische und logische Grundlagen der InformatikAlgebraic 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}
}