2026-07-22T04:53:57Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:9562 2024-03-06T10:44:44Z ddc:004 open_access

Linear Equations with Ordered Data Hofman, Piotr Lasota, Slawomir Linear equations Petri nets Petri nets with data vector addition systems sets with atoms orbit-finite sets Following a recently considered generalization of linear equations to unordered data vectors, we perform a further generalization to ordered data vectors. These generalized equations naturally appear in the analysis of vector addition systems (or Petri nets) extended with ordered data. We show that nonnegative-integer solvability of linear equations is computationally equivalent (up to an exponential blowup) to the reachability problem for (plain) vector addition systems. This high complexity is surprising, and contrasts with NP-completeness for unordered data vectors. This also contrasts with our second result, namely polynomial time complexity of the solvability problem when the nonnegative-integer restriction on solutions is relaxed. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Piotr Hofman and Slawomir Lasota 2018 Is Part Of LIPIcs, Volume 118, 29th International Conference on Concurrency Theory (CONCUR 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CONCUR.2018.24 urn:nbn:de:0030-drops-95624 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2018.24 eng https://creativecommons.org/licenses/by/3.0/legalcode