Ratio and Weight Quantiles

Daniel KrähmannDaniel Krähmann, Jana SchubertJana Schubert, Christel BaierChristel Baier, Clemens DubslaffClemens Dubslaff

DOI Link

Daniel Krähmann, Jana Schubert, Christel Baier, Clemens Dubslaff
Ratio and Weight Quantiles
Proc. of the 40th Symposium on Mathematical Foundations of Computer Science (MFCS): Part I, volume 9234 of Lecture Notes in Computer Science, 344--356, 2015. Springer

Details
Bibtex

KurzfassungAbstract
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.
Forschungsgruppe:Research Group: Algebraische und logische Grundlagen der InformatikAlgebraic and Logical Foundations of Computer Science

The final publication is available at Springer via http://dx.doi.org/10.1007/978-3-662-48057-1_27.

@inproceedings{KSBD2015,
  author    = {Daniel Kr{\"{a}}hmann and Jana Schubert and Christel Baier and
               Clemens Dubslaff},
  title     = {Ratio and Weight Quantiles},
  booktitle = {Proc. of the 40th Symposium on Mathematical Foundations of
               Computer Science (MFCS): Part I},
  series    = {Lecture Notes in Computer Science},
  volume    = {9234},
  publisher = {Springer},
  year      = {2015},
  pages     = {344--356},
  doi       = {10.1007/978-3-662-48057-1_27}
}