ﻻ يوجد ملخص باللغة العربية
We generalise the hyperplane separation technique (Chatterjee and Velner, 2013) from multi-dimensional mean-payoff to energy games, and achieve an algorithm for solving the latter whose running time is exponential only in the dimension, but not in the number of vertices of the game graph. This answers an open question whether energy games with arbitrary initial credit can be solved in pseudo-polynomial time for fixed dimensions 3 or larger (Chaloupka, 2013). It also improves the complexity of solving multi-dimensional energy games with given initial credit from non-elementary (Brazdil, Janv{c}ar, and Kuv{c}era, 2010) to 2EXPTIME, thus establishing their 2EXPTIME-completeness.
We study stochastic games with energy-parity objectives, which combine quantitative rewards with a qualitative $omega$-regular condition: The maximizer aims to avoid running out of energy while simultaneously satisfying a parity condition. We show th
An average-time game is played on the infinite graph of configurations of a finite timed automaton. The two players, Min and Max, construct an infinite run of the automaton by taking turns to perform a timed transition. Player Min wants to minimise t
In a mean-payoff parity game, one of the two players aims both to achieve a qualitative parity objective and to minimize a quantitative long-term average of payoffs (aka. mean payoff). The game is zero-sum and hence the aim of the other player is to
An ever-important issue is protecting infrastructure and other valuable targets from a range of threats from vandalism to theft to piracy to terrorism. The defender can rarely afford the needed resources for a 100% protection. Thus, the key question
In this paper, we propose a pseudo polynomial size LP formulation for finding a payoff vector in the least core of a weighted voting game. The numbers of variables and constraints in our formulation are both bounded by $mbox{O}(n W_+)$, where $n$ is