---
res:
bibo_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.@eng
bibo_authorlist:
- foaf_Person:
foaf_givenName: Laurent
foaf_name: Doyen, Laurent
foaf_surname: Doyen
- foaf_Person:
foaf_givenName: Thomas A
foaf_name: Thomas Henzinger
foaf_surname: Henzinger
foaf_workInfoHomepage: http://www.librecat.org/personId=40876CD8-F248-11E8-B48F-1D18A9856A87
orcid: 0000−0002−2985−7724
- foaf_Person:
foaf_givenName: Jean
foaf_name: Raskin, Jean-François
foaf_surname: Raskin
bibo_doi: '10.1142/S0129054108005814 '
bibo_issue: '3'
bibo_volume: 19
dct_date: 2008^xs_gYear
dct_publisher: World Scientific Publishing@
dct_title: Equivalence of labeled Markov chains@
...