Equivalence of labeled Markov chains

Doyen L, Henzinger TA, Raskin J. 2008. Equivalence of labeled Markov chains. International Journal of Foundations of Computer Science. 19(3), 549–563.

Download
No fulltext has been uploaded. References only!

Journal Article | Published
Author
Doyen, Laurent; Henzinger, Thomas AIST Austria ; Raskin, Jean-François
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.
Publishing Year
Date Published
2008-06-01
Journal Title
International Journal of Foundations of Computer Science
Volume
19
Issue
3
Page
549 - 563
IST-REx-ID

Cite this

Doyen L, Henzinger TA, Raskin J. Equivalence of labeled Markov chains. International Journal of Foundations of Computer Science. 2008;19(3):549-563. doi:10.1142/S0129054108005814
Doyen, L., Henzinger, T. A., & Raskin, J. (2008). Equivalence of labeled Markov chains. International Journal of Foundations of Computer Science. World Scientific Publishing. https://doi.org/10.1142/S0129054108005814
Doyen, Laurent, Thomas A Henzinger, and Jean Raskin. “Equivalence of Labeled Markov Chains.” International Journal of Foundations of Computer Science. World Scientific Publishing, 2008. https://doi.org/10.1142/S0129054108005814 .
L. Doyen, T. A. Henzinger, and J. Raskin, “Equivalence of labeled Markov chains,” International Journal of Foundations of Computer Science, vol. 19, no. 3. World Scientific Publishing, pp. 549–563, 2008.
Doyen L, Henzinger TA, Raskin J. 2008. Equivalence of labeled Markov chains. International Journal of Foundations of Computer Science. 19(3), 549–563.
Doyen, Laurent, et al. “Equivalence of Labeled Markov Chains.” International Journal of Foundations of Computer Science, vol. 19, no. 3, World Scientific Publishing, 2008, pp. 549–63, doi:10.1142/S0129054108005814 .

Link(s) to Main File(s)
Access Level
Restricted Closed Access

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar