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

We study a class of reachability problems in weighted graphs with constraintson the accumulated weight of paths. The problems we study can equivalently beformulated in the model of vector addition systems with states (VASS). Weconsider a version of the vertex-to-vertex reachability problem in which theaccumulated weight of a path is required always to be non-negative. This isequivalent to the so-called control-state reachability problem (also called thecoverability problem) for 1-dimensional VASS. We show that this problem lies inNC: the class of problems solvable in polylogarithmic parallel time. In ourmain result we generalise the problem to allow disequality constraints on edges(i.e., we allow edges to be disabled if the accumulated weight is equal to aspecific value). We show that in this case the vertex-to-vertex reachabilityproblem is solvable in polynomial time even though a shortest path may haveexponential length. In the language of VASS this means that control-statereachability is in polynomial time for 1-dimensional VASS with disequalitytests.

Coverability in 1-VASS with Disequality Tests