{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,31]],"date-time":"2025-10-31T07:13:52Z","timestamp":1761894832871,"version":"3.41.2"},"reference-count":0,"publisher":"Centre pour la Communication Scientifique Directe (CCSD)","license":[{"start":{"date-parts":[[2008,11,11]],"date-time":"2008-11-11T00:00:00Z","timestamp":1226361600000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/arxiv.org\/licenses\/nonexclusive-distrib\/1.0"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"abstract":"<jats:p>Strong and weak simulation relations have been proposed for Markov chains,\nwhile strong simulation and strong probabilistic simulation relations have been\nproposed for probabilistic automata. However, decision algorithms for strong\nand weak simulation over Markov chains, and for strong simulation over\nprobabilistic automata are not efficient, which makes it as yet unclear whether\nthey can be used as effectively as their non-probabilistic counterparts. This\npaper presents drastically improved algorithms to decide whether some\n(discrete- or continuous-time) Markov chain strongly or weakly simulates\nanother, or whether a probabilistic automaton strongly simulates another. The\nkey innovation is the use of parametric maximum flow techniques to amortize\ncomputations. We also present a novel algorithm for deciding strong\nprobabilistic simulation preorders on probabilistic automata, which has\npolynomial complexity via a reduction to an LP problem. When extending the\nalgorithms for probabilistic automata to their continuous-time counterpart, we\nretain the same complexity for both strong and strong probabilistic\nsimulations.<\/jats:p>","DOI":"10.2168\/lmcs-4(4:6)2008","type":"journal-article","created":{"date-parts":[[2009,1,9]],"date-time":"2009-01-09T10:25:13Z","timestamp":1231496713000},"source":"Crossref","is-referenced-by-count":21,"title":["Flow Faster: Efficient Decision Algorithms for Probabilistic Simulations"],"prefix":"10.46298","volume":"Volume 4, Issue 4","author":[{"given":"Lijun","family":"Zhang","sequence":"first","affiliation":[]},{"given":"Holger","family":"Hermanns","sequence":"additional","affiliation":[]},{"given":"Friedrich","family":"Eisenbrand","sequence":"additional","affiliation":[]},{"given":"David N.","family":"Jansen","sequence":"additional","affiliation":[]}],"member":"25203","published-online":{"date-parts":[[2008,11,11]]},"container-title":["Logical Methods in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/lmcs.episciences.org\/989\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/lmcs.episciences.org\/989\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,4,11]],"date-time":"2023-04-11T20:00:47Z","timestamp":1681243247000},"score":1,"resource":{"primary":{"URL":"https:\/\/lmcs.episciences.org\/989"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,11,11]]},"references-count":0,"URL":"https:\/\/doi.org\/10.2168\/lmcs-4(4:6)2008","relation":{"is-same-as":[{"id-type":"arxiv","id":"0808.3651","asserted-by":"subject"},{"id-type":"doi","id":"10.48550\/arXiv.0808.3651","asserted-by":"subject"}]},"ISSN":["1860-5974"],"issn-type":[{"type":"electronic","value":"1860-5974"}],"subject":[],"published":{"date-parts":[[2008,11,11]]},"article-number":"989"}}