{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T17:09:52Z","timestamp":1760202592920,"version":"3.41.2"},"reference-count":0,"publisher":"Centre pour la Communication Scientifique Directe (CCSD)","license":[{"start":{"date-parts":[[2008,9,11]],"date-time":"2008-09-11T00:00:00Z","timestamp":1221091200000},"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>We consider two-player games played over finite state spaces for an infinite\nnumber of rounds. At each state, the players simultaneously choose moves; the\nmoves determine a successor state. It is often advantageous for players to\nchoose probability distributions over moves, rather than single moves. Given a\ngoal, for example, reach a target state, the question of winning is thus a\nprobabilistic one: what is the maximal probability of winning from a given\nstate?\n  On these game structures, two fundamental notions are those of equivalences\nand metrics. Given a set of winning conditions, two states are equivalent if\nthe players can win the same games with the same probability from both states.\nMetrics provide a bound on the difference in the probabilities of winning\nacross states, capturing a quantitative notion of state similarity.\n  We introduce equivalences and metrics for two-player game structures, and we\nshow that they characterize the difference in probability of winning games\nwhose goals are expressed in the quantitative mu-calculus. The quantitative\nmu-calculus can express a large set of goals, including reachability, safety,\nand omega-regular properties. Thus, we claim that our relations and metrics\nprovide the canonical extensions to games, of the classical notion of\nbisimulation for transition systems. We develop our results both for\nequivalences and metrics, which generalize bisimulation, and for asymmetrical\nversions, which generalize simulation.<\/jats:p>","DOI":"10.2168\/lmcs-4(3:7)2008","type":"journal-article","created":{"date-parts":[[2009,1,9]],"date-time":"2009-01-09T10:22:49Z","timestamp":1231496569000},"source":"Crossref","is-referenced-by-count":19,"title":["Game Refinement Relations and Metrics"],"prefix":"10.46298","volume":"Volume 4, Issue 3","author":[{"given":"Luca","family":"de Alfaro","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rupak","family":"Majumdar","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Vishwanath","family":"Raman","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mari\u00eblle","family":"Stoelinga","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"25203","published-online":{"date-parts":[[2008,9,11]]},"container-title":["Logical Methods in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/lmcs.episciences.org\/781\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/lmcs.episciences.org\/781\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,4,11]],"date-time":"2023-04-11T19:55:46Z","timestamp":1681242946000},"score":1,"resource":{"primary":{"URL":"https:\/\/lmcs.episciences.org\/781"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,9,11]]},"references-count":0,"URL":"https:\/\/doi.org\/10.2168\/lmcs-4(3:7)2008","relation":{"is-same-as":[{"id-type":"arxiv","id":"0806.4956","asserted-by":"subject"},{"id-type":"doi","id":"10.48550\/arXiv.0806.4956","asserted-by":"subject"}],"is-referenced-by":[{"id-type":"arxiv","id":"1610.08169","asserted-by":"subject"},{"id-type":"doi","id":"10.4204\/eptcs.227.4","asserted-by":"subject"},{"id-type":"doi","id":"10.48550\/arxiv.1610.08169","asserted-by":"subject"}]},"ISSN":["1860-5974"],"issn-type":[{"type":"electronic","value":"1860-5974"}],"subject":[],"published":{"date-parts":[[2008,9,11]]},"article-number":"781"}}