On the optimal reachability problem
On the optimal reachability problem
复制标题
关于最优可达性问题
DOI：
--
复制
发表时间：
2006
期刊：
影响因子：
--
通讯作者：
P. Bouyer
中科院分区：
文献类型：
--
作者：
Thomas Brihaye;V. Bruyère;Jean;P. Bouyer
我们研究了加权时间自动机的成本最优可达性问题，使得在边缘和位置上允许正负成本。所谓最优性，我们指的是下确界成本和上确界成本。我们证明了这个问题是PSPACE-紧的。我们的证明使用了线性规划的技术，从而利用了最优运行的一个重要性质：它们的时间转换使用任意接近整数的时间τ。然后，我们提出了一个扩展的区域图，加权离散图，其结构给出光的方式来解决成本最优的可达性问题。我们还给出了应用程序的成本最优的可达性问题的时间游戏的背景下。
We study the cost-optimal reachability problem for weighted timed automata such that positive and negative costs are allowed on edges and locations. By optimality, we mean an infimum cost as well as a supremum cost. We show that this problem is PSPACE-COMPLETE. Our proof uses techniques of linear programming, and thus exploits an important property of optimal runs : their time-transitions use a time τ which is arbitrarily closed to an integer. We then propose an extension of the region graph, the weighted discrete graph, whose structure gives light on the way to solve the cost-optimal reachability problem. We also give an application of the cost-optimal reachability problem in the context of timed games.