conference paper
Concurrent omega-regular games
published
yes
Luca
De Alfaro
author
Thomas A
Henzinger
author 40876CD8-F248-11E8-B48F-1D18A9856A870000−0002−2985−7724
LICS: Logic in Computer Science
We consider two-player games, which are played on a finite state space for an infinite number of rounds. The games are concurrent, that is, in each round, the two players choose their moves independently and simultaneously; the current state and the two moves determine a successor state. We consider omega-regular winning conditions on the resulting infinite state sequence. To model the independent choice of moves, both players are allowed to use randomization for selecting their moves. This gives rise to the following qualitative modes of winning, which can be studied without numerical considerations concerning probabilities: sure-win (player 1 can ensure winning with certainty), almost-sure-win (player 1 can ensure winning with probability 1), limit-win (player 1 can ensure winning with probability arbitrarily close to 1), bounded-win (player 1 can ensure winning with probability bounded away from 0), positive-win (player 1 can ensure winning with positive probability), and exist-win (player 1 can ensure that at least one possible outcome of the game satisfies the winning condition).We provide algorithms for computing the sets of winning states for each of these winning modes. In particular, we solve concurrent Rabin-chain games in n0 (m) time, where n is the size of the game structure and m is the number of pairs in the Rabin-chain condition. While this complexity is in line with traditional turn-based games, where in each state only one of the two players has a choice of moves, our algorithms are considerably more involved than those for turn-based games are. This is because concurrent games violate two of the most fundamental properties of turn-based games. First, concurrent games are not determined, but rather exhibit a more general duality property, which involves multiple modes of winning. Second, winning strategies for concurrent games may require infinite memory.
IEEE2000Santa Barbara, CA, USA
eng
Proceedings of the 15th Annual IEEE Symposium on Logic in Computer Science
076950725510.1109/LICS.2000.855763
141 - 154
yes
De Alfaro L, Henzinger TA. 2000. Concurrent omega-regular games. Proceedings of the 15th Annual IEEE Symposium on Logic in Computer Science. LICS: Logic in Computer Science, 141–154.
De Alfaro, Luca, and Thomas A Henzinger. “Concurrent Omega-Regular Games.” In <i>Proceedings of the 15th Annual IEEE Symposium on Logic in Computer Science</i>, 141–54. IEEE, 2000. <a href="https://doi.org/10.1109/LICS.2000.855763">https://doi.org/10.1109/LICS.2000.855763</a>.
De Alfaro L, Henzinger TA. Concurrent omega-regular games. In: <i>Proceedings of the 15th Annual IEEE Symposium on Logic in Computer Science</i>. IEEE; 2000:141-154. doi:<a href="https://doi.org/10.1109/LICS.2000.855763">10.1109/LICS.2000.855763</a>
De Alfaro, Luca, and Thomas A. Henzinger. “Concurrent Omega-Regular Games.” <i>Proceedings of the 15th Annual IEEE Symposium on Logic in Computer Science</i>, IEEE, 2000, pp. 141–54, doi:<a href="https://doi.org/10.1109/LICS.2000.855763">10.1109/LICS.2000.855763</a>.
L. De Alfaro, T.A. Henzinger, in:, Proceedings of the 15th Annual IEEE Symposium on Logic in Computer Science, IEEE, 2000, pp. 141–154.
L. De Alfaro and T. A. Henzinger, “Concurrent omega-regular games,” in <i>Proceedings of the 15th Annual IEEE Symposium on Logic in Computer Science</i>, Santa Barbara, CA, USA, 2000, pp. 141–154.
De Alfaro, L., & Henzinger, T. A. (2000). Concurrent omega-regular games. In <i>Proceedings of the 15th Annual IEEE Symposium on Logic in Computer Science</i> (pp. 141–154). Santa Barbara, CA, USA: IEEE. <a href="https://doi.org/10.1109/LICS.2000.855763">https://doi.org/10.1109/LICS.2000.855763</a>
46272018-12-11T12:09:50Z2023-04-13T13:24:29Z