Kleene Algebras and Semimodules for Energy Problems

Zoltá Esik 1 Uli Fahrenberg 2 Axel Legay 2 Karin Quaas 3
1 Institute of Informatics
Institute of Informatics
2 ESTASYS - Efficient STAtistical methods in SYstems of systems
Inria Rennes – Bretagne Atlantique , IRISA-D4 - LANGAGE ET GÉNIE LOGICIEL
Abstract : 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 Büchi acceptance for semiring-weighted automata, we show that these generalized energy problems are decidable. We also provide complexity results for important special cases.
Liste complète des métadonnées

Cited literature [28 references]  Display  Hide  Download

https://hal.inria.fr/hal-01087913
Contributor : Uli Fahrenberg <>
Submitted on : Thursday, November 27, 2014 - 9:32:07 AM
Last modification on : Friday, November 16, 2018 - 1:39:29 AM
Document(s) archivé(s) le : Friday, April 14, 2017 - 10:14:20 PM

File

atva.pdf
Files produced by the author(s)

Identifiers

Citation

Zoltá Esik, Uli Fahrenberg, Axel Legay, Karin Quaas. Kleene Algebras and Semimodules for Energy Problems. ATVA 2013 - 11th International Symposium Automated Technology for Verification and Analysis, Oct 2013, Hanoi, Vietnam. pp.102-117, ⟨10.1007/978-3-319-02444-8_9⟩. ⟨hal-01087913⟩

Share

Metrics

Record views

400

Files downloads

69