Staying Alive as Cheaply as Possible
Staying Alive as Cheaply as Possible
复制标题
尽可能便宜地维持生命
DOI：
--
复制
发表时间：
2004
期刊：
影响因子：
--
通讯作者：
K. Larsen
中科院分区：
文献类型：
--
作者：
P. Bouyer;E. Brinksma;K. Larsen
本文主要研究时间自动机的无限时间表的推导，这些时间表在某种意义上是最优的。为了涵盖广泛的最优性标准，我们首先引入了（定价）时间自动机模型的扩展，该模型包括成本和奖励作为单独的建模功能。一个精确的定义，然后给出什么构成这类模型的最佳无限行为。随后，我们证明了这种双重价格的时间自动机的最佳非终止时间表的推导是可计算的。这是通过将问题简化为确定具有加权边的有限图中的最佳平均圈来完成的。这种减少是通过引入所谓的角点抽象，一个强大的抽象技术，我们表明，它保留了最佳的时间表。
This paper is concerned with the derivation of infinite schedules for timed automata that are in some sense optimal. To cover a wide class of optimality criteria we start out by introducing an extension of the (priced) timed automata model that includes both costs and rewards as separate modelling features. A precise definition is then given of what constitutes optimal infinite behaviours for this class of models. We subsequently show that the derivation of optimal non-terminating schedules for such double-priced timed automata is computable. This is done by a reduction of the problem to the determination of optimal mean-cycles in finite graphs with weighted edges. This reduction is obtained by introducing the so-called corner-point abstraction, a powerful abstraction technique of which we show that it preserves optimal schedules.