Piotr Hofman ; Jakub Różycki - Linear equations for unordered data vectors in $[D]^k\to{}Z^d$

lmcs:8459 - Logical Methods in Computer Science, December 12, 2022, Volume 18, Issue 4 - https://doi.org/10.46298/lmcs-18(4:11)2022
Linear equations for unordered data vectors in $[D]^k\to{}Z^d$Article

Authors: Piotr Hofman ORCID; Jakub Różycki

    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.


    Volume: Volume 18, Issue 4
    Published on: December 12, 2022
    Accepted on: October 21, 2022
    Submitted on: September 8, 2021
    Keywords: Computer Science - Computational Complexity,Computer Science - Formal Languages and Automata Theory,Computer Science - Symbolic Computation,68Q85,F.4.2,G.2.2,F.3.1

    Consultation statistics

    This page has been seen 1417 times.
    This article's PDF has been downloaded 201 times.