Document Open Access Logo

An omega-Algebra for Real-Time Energy Problems

Authors David Cachera, Uli Fahrenberg, Axel Legay

PDF
Thumbnail PDF

File

LIPIcs.FSTTCS.2015.394.pdf
  • Filesize: 0.59 MB
  • 14 pages

Document Identifiers

Author Details

David Cachera
Uli Fahrenberg
Axel Legay

Cite As Get BibTex

David Cachera, Uli Fahrenberg, and Axel Legay. An omega-Algebra for Real-Time Energy Problems. In 35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 45, pp. 394-407, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015) https://doi.org/10.4230/LIPIcs.FSTTCS.2015.394

Abstract

We develop a *-continuous Kleene omega-algebra of real-time energy functions. Together with corresponding automata, these can be used to model systems which can consume and regain energy (or other types of resources) depending on available time. Using recent results on *-continuous Kleene omega-algebras and computability of certain manipulations on real-time energy functions, it follows that reachability and Büchi acceptance in real-time energy automata can be decided in a static way which only involves manipulations of real-time energy functions.

Subject Classification

Keywords
  • Energy problem
  • Real time
  • Star-continuous Kleene algebra

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Rajeev Alur, Salvatore La Torre, and George J. Pappas. Optimal paths in weighted timed automata. In HSCC, volume 2034 of LNCS, pages 49-62. Springer, 2001. Google Scholar
  2. Gerd Behrmann, Ansgar Fehnker, Thomas Hune, Kim G. Larsen, Paul Pettersson, Judi Romijn, and Frits W. Vaandrager. Minimum-cost reachability for priced timed automata. In HSCC, volume 2034 of LNCS, pages 147-161. Springer, 2001. Google Scholar
  3. Stephen L. Bloom and Zoltán Ésik. Iteration Theories. Springer, 1993. Google Scholar
  4. Patricia Bouyer, Uli Fahrenberg, Kim G. Larsen, and Nicolas Markey. Timed automata with observers under energy constraints. In HSCC, pages 61-70. ACM, 2010. Google Scholar
  5. Patricia Bouyer, Uli Fahrenberg, Kim G. Larsen, Nicolas Markey, and Jiří Srba. Infinite runs in weighted timed automata with energy constraints. In FORMATS, volume 5215 of LNCS, pages 33-47. Springer, 2008. Google Scholar
  6. Patricia Bouyer, Kim G. Larsen, and Nicolas Markey. Lower-bound-constrained runs in weighted timed automata. Perform. Eval., 73:91-109, 2014. Google Scholar
  7. Brijesh Dongol, Ian J. Hayes, Larissa Meinicke, and Kim Solin. Towards an algebra for real-time programs. In RAMiCS, volume 7560 of LNCS, pages 50-65. Springer, 2012. Google Scholar
  8. Manfred Droste, Werner Kuich, and Heiko Vogler, editors. Handbook of Weighted Automata. Springer, 2009. Google Scholar
  9. Zoltá Ésik and Werner Kuich. Locally closed semirings. Monatsh. Math., 137(1):21-29, 2002. Google Scholar
  10. Zoltán Ésik, Uli Fahrenberg, and Axel Legay. ^*-continuous Kleene ω-algebras. CoRR, abs/1501.01118, 2015. URL: http://arxiv.org/abs/1501.01118.
  11. Zoltán Ésik, Uli Fahrenberg, and Axel Legay. Star-continuous Kleene omega-algebras. In DLT, volume 9168 of LNCS, pages 240-251. Springer, 2015. Google Scholar
  12. Zoltán Ésik, Uli Fahrenberg, Axel Legay, and Karin Quaas. Kleene algebras and semimodules for energy problems. In ATVA, volume 8172 of LNCS, pages 102-117. Springer, 2013. Google Scholar
  13. Zoltán Ésik and Werner Kuich. Modern Automata Theory. TU Wien, 2007. URL: http://dmg.tuwien.ac.at/kuich/mat.pdf.
  14. Zoltán Ésik and Werner Kuich. On iteration semiring-semimodule pairs. Semigroup Forum, 75:129-159, 2007. Google Scholar
  15. Uli Fahrenberg, Line Juhl, Kim G. Larsen, and Jiří Srba. Energy games in multiweighted automata. In ICTAC, volume 6916 of LNCS, pages 95-115. Springer, 2011. Google Scholar
  16. Jonathan S. Golan. Semirings and their Applications. Springer, 1999. Google Scholar
  17. Peter Höfner and Bernhard Möller. An algebra of hybrid systems. J. Log. Alg. Prog., 78(2):74-97, 2009. Google Scholar
  18. Dexter Kozen. On Kleene algebras and closed semirings. In MFCS, pages 26-47, 1990. Google Scholar
  19. Dexter Kozen. A completeness theorem for Kleene algebras and the algebra of regular events. Inf. Comput., 110(2):366-390, 1994. Google Scholar
  20. Karin Quaas. On the interval-bound problem for weighted timed automata. In LATA, volume 6638 of LNCS, pages 452-464. Springer, 2011. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact