Energy Büchi problems

DOI10.1007/978-3-031-27481-7_14MaRDI QIDQ6174536zbMATH OpenOpenAlexFDO

Authors Sven Dziadek, Uli Fahrenberg, Philipp Schlehuber-Caissier

Publication date 17 August 2023

Published in Formal Methods (Search for Journal in Brave)

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

zbMATH Keywords

energy constraintsenergy problemgeneralized Büchi acceptanceweighted automatonweighted timed automaton

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Abstract: We show how to efficiently solve energy B"uchi problems in finite weighted automata and in one-clock weighted timed automata. Solving the former problem is our main contribution and is handled by a modified version of Bellman-Ford interleaved with Couvreur's algorithm. The latter problem is handled via a reduction to the former relying on the corner-point abstraction. All our algorithms are freely available and implemented in a tool based on the open-source platforms TChecker and Spot.

Recommendations

• Kleene algebras and semimodules for energy problems
• Infinite Runs in Weighted Timed Automata with Energy Constraints
• An $\omega$-algebra for real-time energy problems
• An -algebra for real-time energy problems

Cites work

• A theory of timed automata
• An $\omega$-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
• Better abstractions for timed automata
• Coarse abstractions make Zeno behaviours difficult to detect
• CONCUR 2004 - Concurrency Theory
• Energy games in multiweighted automata
• Energy parity games
• Generalized mean-payoff and energy games
• scientific article; zbMATH DE number 1796123 (Why is no real title available?)
• scientific article; zbMATH DE number 1794367 (Why is no real title available?)
• Infinite Runs in Weighted Timed Automata with Energy Constraints
• On a routing problem
• On the Interval-Bound Problem for Weighted Timed Automata
• Optimal and robust controller synthesis using energy timed automata with uncertainty
• The complexity of multi-mean-payoff and multi-energy games
• Timed automata with observers under energy constraints
• Uppaal in a nutshell

Cited in

(1)

• -regular energy problems

This page was built for publication: Energy Büchi problems

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