Efficient Quantile Computation in Markov Chains via Counting Problems for Parikh Images

Christoph Haase, Stefan Kiefer, Markus Lohrey

A cost Markov chain is a Markov chain whose transitions are labelled with non-negative integer costs. A fundamental problem on this model, with applications in the verification of…