论文标题
单盘定价的定时游戏，负重
One-Clock Priced Timed Games with Negative Weights
论文作者
论文摘要
定价定时游戏是在定价定时自动机上玩过的两人零和游戏（其位置和过渡的标记为重量，将在州内花费时间的成本建模并执行动作）。球员的目标是最大程度地减少和最大化成本，分别达到目标位置。我们考虑使用一个时钟和任意整数权重的定时游戏，并表明，对于其中一个重要的子类（所谓的简单定价定时游戏），可以在伪多种单位时间内计算玩家可以实现的最佳价值，并具有相关的最佳策略。作为侧面的结果，我们还表明，确定了一个赌注定价的定时游戏，并且可以在简单的定时游戏上使用结果来解决更通用的所谓的否定镜头定价定时游戏（具有任意整数的重量和一个时钟）。一类定价的定时游戏的可确定性状态仍然开放。
Priced timed games are two-player zero-sum games played on priced timed automata (whose locations and transitions are labeled by weights modelling the cost of spending time in a state and executing an action, respectively). The goals of the players are to minimise and maximise the cost to reach a target location, respectively. We consider priced timed games with one clock and arbitrary integer weights and show that, for an important subclass of them (the so-called simple priced timed games), one can compute, in pseudo-polynomial time, the optimal values that the players can achieve, with their associated optimal strategies. As side results, we also show that one-clock priced timed games are determined and that we can use our result on simple priced timed games to solve the more general class of so-called negative-reset-acyclic priced timed games (with arbitrary integer weights and one clock). The decidability status of the full class of priced timed games with one-clock and arbitrary integer weights still remains open.
