Kleene Algebras and Semimodules for Energy Problems
Kleene Algebras and Semimodules for Energy Problems
复制标题
能源问题的克林代数和半模
DOI：
10.1007/978-3-319-02444-8_9
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
Karin Quaas
中科院分区：
文献类型：
--
作者：
Z. Ésik;U. Fahrenberg;Axel Legay;Karin Quaas
为了统一文献中能量问题的一些方法，我们引入了广义能量自动机。这些是有限自动机，其边缘标记有能量函数，定义了能级在过渡期间如何演变。揭示了能量问题与半加权自动机的可达性和Buchi可接受性之间的密切联系，证明了这些广义能量问题是可判定的。我们还提供了重要的特殊情况下的复杂性结果。
With the purpose of unifying a number of approaches to energy problems found in the literature, we introduce generalized energy automata. These are finite automata whose edges are labeled with energy functions that define how energy levels evolve during transitions. Uncovering a close connection between energy problems and reachability and Buchi acceptance for semiring-weighted automata, we show that these generalized energy problems are decidable. We also provide complexity results for important special cases.