2016/01/18 by Christoph Haase, Haase, Christoph, Stefan Kiefer +3
Computer Science · #Algorithms and Data Compression #Computational Complexity (cs.CC) #Discrete Mathematics (cs.DM) #F.4.2 #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #Formal Methods in Verification #G.3 #Logic in Computer Science (cs.LO) #cs.CC #cs.DM #cs.FL #cs.LO #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1601.04661
arxiv created 2016/01/18 · openalex publication_date 2016/01/18 · arxiv updated 2016/01/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 stochastic systems, is to compute information about the distribution of the total cost accumulated in a run. This includes the probability of large total costs, the median cost, and other quantiles. While expectations can be computed in polynomial time, previous work has demonstrated that the computation of cost quantiles is harder but can be done in PSPACE. In this paper we show that cost quantiles in cost Markov chains can be computed in the counting hierarchy, thus providing evidence that computing those quantiles is likely not PSPACE-hard. We obtain this result by exhibiting a tight link to a problem in formal language theory: counting the number of words that are both accepted by a given automaton and have a given Parikh image. Motivated by this link, we comprehensively investigate the complexity of the latter problem. Among other techniques, we rely on the so-called BEST theorem for efficiently computing the number of Eulerian circuits in a directed graph.