Linear equations for unordered data vectors in [D]^k→Z^d

08/09/2021
by   Piotr Hofman, et al.
0

Following a recently considered generalisation of linear equations to unordered-data vectors and to ordered-data vectors, we perform a further generalisation to data vectors that are functions from k-element subsets of the unordered-data set to vectors of integer numbers. These generalised equations naturally appear in the analysis of vector addition systems (or Petri nets) extended so that each token carries a set of unordered data. We show that nonnegative-integer solvability of linear equations is in nondeterministic exponential time while integer solvability is in polynomial time.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset