Kleene Algebras and Semimodules for Energy Problems

Esik, Zoltá;Fahrenberg, Uli;Legay, Axel;Quaas, Karin
(2013) ATVA 2013 - 11th International Symposium Automated Technology for Verification and Analysis (15.October.2013)

Files

No attached file found for this publication.

Details

Authors
  • Esik, Zoltá
    Author
  • Fahrenberg, Uli
    Author
  • Legay, AxelUCLouvain
    Author
  • Quaas, Karin
    Author
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.

Citations

  • APA
  • Chicago
  • FWB

Esik, Z., Fahrenberg, U., Legay, A., & Quaas, K. (2013). Kleene Algebras and Semimodules for Energy Problems. Automated Technology for Verification and Analysis Lecture Notes in Computer Science. ATVA 2013 - 11th International Symposium Automated Technology for Verification and Analysis. https://doi.org/10.1007/978-3-319-02444-8_9