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 Tools annual

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 Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

Discrete-time Markov Chains (MCs) and Markov Decision Processes (MDPs) aretwo standard formalisms in system analysis. Their main associated quantitativeobjectives are hitting probabilities, discounted sum, and mean payoff. Althoughthere are many techniques for computing these objectives in general MCs/MDPs,they have not been thoroughly studied in terms of parameterized algorithms,particularly when treewidth is used as the parameter. This is in sharp contrastto qualitative objectives for MCs, MDPs and graph games, for whichtreewidth-based algorithms yield significant complexity improvements.  In this work, we show that treewidth can also be used to obtain fasteralgorithms for the quantitative problems. For an MC with $n$ states and $m$transitions, we show that each of the classical quantitative objectives can becomputed in $O((n+m)\cdot t^2)$ time, given a tree decomposition of the MC thathas width $t$. Our results also imply a bound of $O(\kappa\cdot (n+m)\cdott^2)$ for each objective on MDPs, where $\kappa$ is the number ofstrategy-iteration refinements required for the given input and objective.Finally, we make an experimental evaluation of our new algorithms onlow-treewidth MCs and MDPs obtained from the DaCapo benchmark suite. Ourexperimental results show that on MCs and MDPs with small treewidth, ouralgorithms outperform existing well-established methods by one or more ordersof magnitude.

Faster Algorithms for Quantitative Analysis of Markov Chains and Markov Decision Processes with Small Treewidth