10.1142/S0129054108005814
Doyen, Laurent
Laurent
Doyen
Thomas Henzinger
Thomas A
Henzinger0000−0002−2985−7724
Raskin, Jean-François
Jean
Raskin
Equivalence of labeled Markov chains
World Scientific Publishing
2008
2018-12-11T12:09:20Z
2019-08-02T12:38:32Z
journal_article
https://research-explorer.app.ist.ac.at/record/4532
https://research-explorer.app.ist.ac.at/record/4532.json
We consider the equivalence problem for labeled Markov chains (LMCs), where each state is labeled with an observation. Two LMCs are equivalent if every finite sequence of observations has the same probability of occurrence in the two LMCs. We show that equivalence can be decided in polynomial time, using a reduction to the equivalence problem for probabilistic automata, which is known to be solvable in polynomial time. We provide an alternative algorithm to solve the equivalence problem, which is based on a new definition of bisimulation for probabilistic automata. We also extend the technique to decide the equivalence of weighted probabilistic automata.