Equivalence of labeled Markov chains Journal Article


Author(s): Doyen, Laurent; Henzinger, Thomas A; Raskin, Jean-François
Article Title: Equivalence of labeled Markov chains
Affiliation
Abstract: 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.
Keywords: labeled Markov chain; Markov decision process; probabilistic automaton; equivalence; bisimulation; Finite-State Machines; Probabilistic-Automata
Journal Title: International Journal of Foundations of Computer Science
Volume: 19
Issue 3
ISSN: 0129-0541
Publisher: World Scientific Publishing  
Date Published: 2008-06-01
Start Page: 549
End Page: 563
URL:
DOI: 10.1142/S0129054108005814
Open access: no
IST Austria Authors
  1. Thomas A. Henzinger
    415 Henzinger
Related IST Austria Work