Probabilistic weak simulation is decidable in polynomial time
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. (C) 2003 Elsevier B.V. All rights reserved.
simulation preorder markov chains algorithms computational complexity performance evaluation