2022/05/09 by Sven Dziadek, Dziadek, Sven, Uli Fahrenberg +3
Computer Science · #Formal Methods in Verification #semigroups and automata theory #Machine Learning and Algorithms
paper · pdf · doi:10.48550/arxiv.2205.04392
We show how to efficiently solve problems involving a quantitative measure, here called energy, as well as a qualitative acceptance condition, expressed as a Büchi or Parity objective, in finite weighted automata and in one-clock weighted timed automata. Solving the former problem and extracting the corresponding witness is our main contribution and is handled by a modified version of the Bellman-Ford algorithm 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.