{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T17:09:21Z","timestamp":1760202561195},"reference-count":7,"publisher":"World Scientific Pub Co Pte Lt","issue":"03","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2008,6]]},"abstract":"<jats:p> 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. <\/jats:p><jats:p> Then, we consider the equivalence problem for labeled Markov decision processes (LMDPs), which asks given two LMDPs whether for every scheduler (i.e. way of resolving the nondeterministic decisions) for each of the processes, there exists a scheduler for the other process such that the resulting LMCs are equivalent. The decidability of this problem remains open. We show that the schedulers can be restricted to be observation-based, but may require infinite memory. <\/jats:p>","DOI":"10.1142\/s0129054108005814","type":"journal-article","created":{"date-parts":[[2008,6,3]],"date-time":"2008-06-03T06:27:20Z","timestamp":1212474440000},"page":"549-563","source":"Crossref","is-referenced-by-count":32,"title":["EQUIVALENCE OF LABELED MARKOV CHAINS"],"prefix":"10.1142","volume":"19","author":[{"given":"LAURENT","family":"DOYEN","sequence":"first","affiliation":[{"name":"I&amp;C, \u00c9cole Polytechnique F\u00e9d\u00e9rale de Lausanne (EPFL), 1015 Lausanne, Switzerland"}]},{"given":"THOMAS A.","family":"HENZINGER","sequence":"additional","affiliation":[{"name":"I&amp;C, \u00c9cole Polytechnique F\u00e9d\u00e9rale de Lausanne (EPFL), EECS, University of California at Berkeley, USA"}]},{"given":"JEAN-FRAN\u00c7OIS","family":"RASKIN","sequence":"additional","affiliation":[{"name":"DI, Universit\u00e9 Libre de Bruxelles (ULB), Boulevard du Triomphe CP 212, 1050 Bruxelles, Belgium"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"reference":[{"key":"rf2","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(91)90030-6"},{"key":"rf3","series-title":"Computer Science and Applied Mathematics","volume-title":"Introduction to probabilistic automata","author":"Paz Azaria","year":"1971"},{"key":"rf4","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(63)90290-0"},{"key":"rf5","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(61)80020-X"},{"key":"rf6","doi-asserted-by":"publisher","DOI":"10.1137\/0221017"},{"key":"rf7","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2005.147"},{"key":"rf8","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2005.148"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054108005814","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T20:33:21Z","timestamp":1565123601000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054108005814"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,6]]},"references-count":7,"journal-issue":{"issue":"03","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[2008,6]]}},"alternative-id":["10.1142\/S0129054108005814"],"URL":"https:\/\/doi.org\/10.1142\/s0129054108005814","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,6]]}}}