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 standard way of justifying that a certain probabilistic property holds in asystem is to provide a witnessing subsystem (also called critical subsystem)for the property. Computing minimal witnessing subsystems is NP-hard alreadyfor acyclic Markov chains, but can be done in polynomial time for Markov chainswhose underlying graph is a tree. This paper considers the problem forprobabilistic systems that are similar to trees or paths. It introduces theparameters directed tree-partition width (dtpw) and directed path-partitionwidth (dppw) and shows that computing minimal witnesses remains NP-hard forMarkov chains with bounded dppw (and hence also for Markov chains with boundeddtpw). By observing that graphs of bounded dtpw have bounded width with respectto all known tree similarity measures for directed graphs, the hardness resultcarries over to these other tree similarity measures. Technically, thereduction proceeds via the conceptually simpler matrix-pair chain problem,which is introduced and shown to be NP-complete for nonnegative matrices offixed dimension. Furthermore, an algorithm which aims to utilise a givendirected tree partition of the system to compute a minimal witnessing subsystemis described. It enumerates partial subsystems for the blocks of the partitionalong the tree order, and keeps only necessary ones. A preliminary experimentalanalysis shows that it outperforms other approaches on certain benchmarks whichhave directed tree partitions of small width.

Witnessing Subsystems for Probabilistic Systems with Low Tree Width