{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T17:08:53Z","timestamp":1760202533408,"version":"3.41.2"},"reference-count":0,"publisher":"Centre pour la Communication Scientifique Directe (CCSD)","license":[{"start":{"date-parts":[[2006,11,3]],"date-time":"2006-11-03T00:00:00Z","timestamp":1162512000000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/arxiv.org\/licenses\/assumed-1991-2003"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"abstract":"<jats:p>We study two-player games of infinite duration that are played on finite or\ninfinite game graphs. A winning strategy for such a game is positional if it\nonly depends on the current position, and not on the history of the play. A\ngame is positionally determined if, from each position, one of the two players\nhas a positional winning strategy.\n  The theory of such games is well studied for winning conditions that are\ndefined in terms of a mapping that assigns to each position a priority from a\nfinite set. Specifically, in Muller games the winner of a play is determined by\nthe set of those priorities that have been seen infinitely often; an important\nspecial case are parity games where the least (or greatest) priority occurring\ninfinitely often determines the winner. It is well-known that parity games are\npositionally determined whereas Muller games are determined via finite-memory\nstrategies.\n  In this paper, we extend this theory to the case of games with infinitely\nmany priorities. Such games arise in several application areas, for instance in\npushdown games with winning conditions depending on stack contents.\n  For parity games there are several generalisations to the case of infinitely\nmany priorities. While max-parity games over omega or min-parity games over\nlarger ordinals than omega require strategies with infinite memory, we can\nprove that min-parity games with priorities in omega are positionally\ndetermined. Indeed, it turns out that the min-parity condition over omega is\nthe only infinitary Muller condition that guarantees positional determinacy on\nall game graphs.<\/jats:p>","DOI":"10.2168\/lmcs-2(4:6)2006","type":"journal-article","created":{"date-parts":[[2006,11,23]],"date-time":"2006-11-23T09:29:19Z","timestamp":1164274159000},"source":"Crossref","is-referenced-by-count":5,"title":["Positional Determinacy of Games with Infinitely Many Priorities"],"prefix":"10.46298","volume":"Volume 2, Issue 4","author":[{"given":"Erich","family":"Graedel","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Igor","family":"Walukiewicz","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"25203","published-online":{"date-parts":[[2006,11,3]]},"container-title":["Logical Methods in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/lmcs.episciences.org\/2242\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/lmcs.episciences.org\/2242\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,4,11]],"date-time":"2023-04-11T20:10:30Z","timestamp":1681243830000},"score":1,"resource":{"primary":{"URL":"https:\/\/lmcs.episciences.org\/2242"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,11,3]]},"references-count":0,"URL":"https:\/\/doi.org\/10.2168\/lmcs-2(4:6)2006","relation":{"is-same-as":[{"id-type":"arxiv","id":"cs\/0610035","asserted-by":"subject"},{"id-type":"doi","id":"10.48550\/arXiv.cs\/0610035","asserted-by":"subject"}]},"ISSN":["1860-5974"],"issn-type":[{"type":"electronic","value":"1860-5974"}],"subject":[],"published":{"date-parts":[[2006,11,3]]},"article-number":"2242"}}