Ratio and Weight Quantiles
Several types of weighted-automata models and formalisms to specify and verify
constraints on accumulated weights have been studied in the past. The lack of
monotonicity for weight functions with positive and negative values as well as
for ratios of the accumulated values of non-negative weight functions renders
many verification problems to be undecidable or computationally hard.
Our contribution comprises polynomial-time algorithms for computing ratio and weight
quantiles in Markov chains, which provide optimal bounds guaranteed almost surely
or with positive probability on, e.g., cost-utility ratios or the energy conversion efficiency.
- Daniel Krähmann, Jana Schubert, Christel Baier, Clemens Dubslaff:
Ratio and Weight Quantiles (MFCS'15, Springer LNCS)
- Daniel Krähmann, Jana Schubert, Christel Baier, Clemens Dubslaff:
Ratio and Weight Quantiles (MFCS'15, extended version, 24th August 2015)
- Jana Schubert:
Ratio and Weight Objectives in Annotated Markov Chains (Diploma Thesis, TU Dresden, 2015)
List of publications of Prof. Baier's group.