Name
Abstract | ||
|---|---|---|
Classical objectives in two-player zero-sum games played on graphs often deal with limit behaviors of infinite plays: e.g., mean payoff and total-payoff in the quantitative setting, or parity in the qualitative one (a canonical way to encode co-regular properties). Those objectives offer powerful abstraction mechanisms and often yield nice properties such as memoryless determinacy. However, their very nature provides no guarantee on time bounds within which something good can be witnessed. In this work, we consider two approaches toward inclusion of time bounds in parity games. The first one, parity-response games, is based on the notion of finitary parity games [8] and parity games with costs [16, 29]. The second one, window parity games, is inspired by window mean payoff games [5]. We compare the two approaches and show that while they prove to be equivalent in some contexts, window parity games offer a more tractable alternative when the time bound is given as a parameter (P-c. vs. PS PACE-c.). In particular, it provides a conservative approximation of parity games computable in polynomial time. Furthermore, we extend both approaches to the multi-dimension setting. We give the full picture for both types of games with regard to complexity and memory bounds. |
Year | DOI | Venue |
|---|---|---|
2016 | 10.4204/EPTCS.226.10 | ELECTRONIC PROCEEDINGS IN THEORETICAL COMPUTER SCIENCE |
Field | DocType | Volume |
Discrete mathematics,Graph,Combinatorics,Abstraction,Algorithm,Chatterjee,Finitary,Time complexity,Parity (mathematics),Determinacy,Mathematics,Computation | Journal | abs/1606.01831 |
Issue | ISSN | Citations |
226 | 2075-2180 | 2 |
PageRank | References | Authors |
0.38 | 15 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Véronique Bruyère | 1 | 429 | 43.59 |
| Quentin Hautem | 2 | 2 | 0.38 |
| Mickael Randour | 3 | 74 | 8.36 |