Kleene algebras and semimodules for energy problems

DOI10.1007/978-3-319-02444-8_9MaRDI QIDQ5166679zbMATH OpenOpenAlexFDO

Authors Uli Fahrenberg, Axel Legay, Karin Quaas, Zoltán Ésik

Publication date 8 July 2014

Published in Automated Technology for Verification and Analysis (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1307.0635

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Algebraic theory of languages and automata (68Q70)

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"uchi acceptance for semiring-weighted automata, we show that these generalized energy problems are decidable. We also provide complexity results for important special cases.

Recommendations

• An algebraic approach to energy problems. I: ^*-continuous Kleene -algebras
• ^*-continuous Kleene -algebras for energy problems
• An algebraic approach to energy problems. II: The algebra of energy functions
• An $\omega$-algebra for real-time energy problems
• An -algebra for real-time energy problems

Cited in

(7)

• ^*-continuous Kleene -algebras
• ^*-continuous Kleene -algebras for energy problems
• An -algebra for real-time energy problems
• An algebraic approach to energy problems. I: ^*-continuous Kleene -algebras
• An algebraic approach to energy problems. II: The algebra of energy functions
• An $\omega$-algebra for real-time energy problems
• Energy Büchi problems

This page was built for publication: Kleene algebras and semimodules for energy problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5166679)