Ratio and Weight Quantiles
Aus International Center for Computational Logic
Ratio and Weight Quantiles
Daniel KrähmannDaniel Krähmann, Jana SchubertJana Schubert, Christel BaierChristel Baier, Clemens DubslaffClemens Dubslaff
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
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
- 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
@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}
}