License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CONCUR.2018.24
URN: urn:nbn:de:0030-drops-95624
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9562/
Go to the corresponding LIPIcs Volume Portal

Hofman, Piotr ; Lasota, Slawomir

Linear Equations with Ordered Data

pdf-format:
LIPIcs-CONCUR-2018-24.pdf (0.5 MB)

Abstract

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.

BibTeX - Entry

@InProceedings{hofman_et_al:LIPIcs:2018:9562,
  author =	{Piotr Hofman and Slawomir Lasota},
  title =	{{Linear Equations with Ordered Data}},
  booktitle =	{29th International Conference on Concurrency Theory  (CONCUR 2018)},
  pages =	{24:1--24:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-087-3},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{118},
  editor =	{Sven Schewe and Lijun Zhang},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9562},
  URN =		{urn:nbn:de:0030-drops-95624},
  doi =		{10.4230/LIPIcs.CONCUR.2018.24},
  annote =	{Keywords: Linear equations, Petri nets, Petri nets with data, vector addition systems, sets with atoms, orbit-finite sets}
}

Keywords: Linear equations, Petri nets, Petri nets with data, vector addition systems, sets with atoms, orbit-finite sets
Collection: 29th International Conference on Concurrency Theory (CONCUR 2018)
Issue Date: 2018
Date of publication: 31.08.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI