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.14
URN: urn:nbn:de:0030-drops-95520
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9552/
Go to the corresponding LIPIcs Volume Portal

Blondin, Michael ; Haase, Christoph ; Mazowiecki, Filip

Affine Extensions of Integer Vector Addition Systems with States

pdf-format:
LIPIcs-CONCUR-2018-14.pdf (0.6 MB)

Abstract

We study the reachability problem for affine Z-VASS, which are integer vector addition systems with states in which transitions perform affine transformations on the counters. This problem is easily seen to be undecidable in general, and we therefore restrict ourselves to affine Z-VASS with the finite-monoid property (afmp-Z-VASS). The latter have the property that the monoid generated by the matrices appearing in their affine transformations is finite. The class of afmp-Z-VASS encompasses classical operations of counter machines such as resets, permutations, transfers and copies. We show that reachability in an afmp-Z-VASS reduces to reachability in a Z-VASS whose control-states grow polynomially in the size of the matrix monoid. Our construction shows that reachability relations of afmp-Z-VASS are semilinear, and in particular enables us to show that reachability in Z-VASS with transfers and Z-VASS with copies is PSPACE-complete.

BibTeX - Entry

@InProceedings{blondin_et_al:LIPIcs:2018:9552,
  author =	{Michael Blondin and Christoph Haase and Filip Mazowiecki},
  title =	{{Affine Extensions of Integer Vector Addition Systems with States}},
  booktitle =	{29th International Conference on Concurrency Theory  (CONCUR 2018)},
  pages =	{14:1--14: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/9552},
  URN =		{urn:nbn:de:0030-drops-95520},
  doi =		{10.4230/LIPIcs.CONCUR.2018.14},
  annote =	{Keywords: Vector addition systems, affine transformations, reachability, semilinear sets, computational complexity}
}

Keywords: Vector addition systems, affine transformations, reachability, semilinear sets, computational complexity
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