English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

A cost Markov chain is a Markov chain whose transitions are labelled withnon-negative integer costs. A fundamental problem on this model, withapplications in the verification of stochastic systems, is to computeinformation about the distribution of the total cost accumulated in a run. Thisincludes the probability of large total costs, the median cost, and otherquantiles. While expectations can be computed in polynomial time, previous workhas demonstrated that the computation of cost quantiles is harder but can bedone in PSPACE. In this paper we show that cost quantiles in cost Markov chainscan be computed in the counting hierarchy, thus providing evidence thatcomputing those quantiles is likely not PSPACE-hard. We obtain this result byexhibiting a tight link to a problem in formal language theory: counting thenumber of words that are both accepted by a given automaton and have a givenParikh image. Motivated by this link, we comprehensively investigate thecomplexity of the latter problem. Among other techniques, we rely on theso-called BEST theorem for efficiently computing the number of Euleriancircuits in a directed graph.

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