Skip to Main content Skip to Navigation
Conference papers

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.
Complete list of metadata

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 : Tuesday, June 15, 2021 - 4:26:42 PM
Long-term archiving on: : 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

472

Files downloads

249