定价时间自动机的折扣语义与最优调度

"定价时间自动机的折扣语义及其在最优调度中的应用" 这篇论文探讨了定价时间自动机（Priced Timed Automata, PTA）的一个新概念——折扣语义，它在无限路径最优成本问题和最优调度等领域具有应用价值。在折扣语义下，随着事件发生的延迟，成本会按指数方式衰减，这意味着未来事件的成本贡献取决于它们发生的时间点。这种语义有助于处理那些涉及无限行为的优化问题。 作者Uli Furbach和Kim G. Larsen首先介绍了定价时间自动机的基本概念，这是一种扩展的时间自动机模型，其中包含了位置和转换上的价格，用于表示执行过程中累积的成本。过去的研究大多关注有限行为的最优性，而这篇论文则转向了无限路径的最优性问题。 论文提出，利用折扣原理，可以计算出在给定的定价时间自动机中，总折扣价格最小的无限路径。作者证明了这个问题是可计算的，通过将它映射到有限加权图的一个类似问题。这个证明涉及到一个新定理，关于在无限维空间上定义的单调函数的最小化，这个定理本身在理论计算机科学中也具有独立的兴趣。 在时间自动机的背景下，贴现原则并不新鲜，但本文将其应用到定价时间自动机的最优调度问题中。与以往工作如[8]中对极限比最优解的研究不同，本文提出的折扣语义提供了一种处理无限行为的新途径。论文指出，对于定价时间自动机，可以计算出折扣最优无限路径，这为解决更复杂的调度和其他优化问题提供了新的工具。 此外，作者还讨论了如何将有限时间表的概念应用于定价时间自动机，以解决最优调度问题。他们展示了如何将无限路径的问题转化为一个可以在有限结构上解决的问题，这使得实际的计算和分析成为可能。 这篇论文为理论计算机科学，特别是时间自动机理论和优化问题的求解，提供了一个重要的新视角，即利用折扣语义来处理无限路径的最优性。这不仅深化了我们对时间自动机模型的理解，也为实际应用如系统调度、资源管理等提供了新的算法设计思路。