A Note on the Parameterised Complexity of Coverability in Vector Addition Systems

Michał Pilipczuk, Sylvain Schmitz, Henry Sinclair-Banks · 2025

Read A Note on the Parameterised Complexity of Coverability in Vector Addition Systems by Michał Pilipczuk, Sylvain Schmitz, Henry Sinclair-Banks (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2511-19212.txt.

Introduction

Michał Pilipczuk, Sylvain Schmitz, and Henry Sinclair-Banks study the coverability problem for vector addition systems, a model of processes that add integer steps while never dropping below zero. The question asks whether a target configuration can be reached or exceeded from a start state. They examine how hard the problem is when measured by two natural parameters.

Those parameters are the system dimension and the total encoding size of its vector set. Among several results, coverability with dimension as the parameter and numbers written in unary is complete for the complexity class XNL under log-space reductions. The authors also flag open questions, including whether the encoding-size parameter allows a fixed-parameter algorithm.

Catalog record

CREATORMichał Pilipczuk, Sylvain Schmitz, Henry Sinclair-Banks
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE103 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2511-19212

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

A Note on the Parameterised Complexity of Coverability in Vector Addition Systems Michał Pilipczuk, Sylvain Schmitz, Henry Sinclair-Banks Abstract We investigate the parameterised complexity of the classic coverability problem for vector addition systems (VAS): given a finite set of vectors 𝑽 ⊆ ℤ d \mathchoice{\mbox{\boldmath$\displaystyle V$}}{\mbox{\boldmath$\textstyle V$}}{\mbox{\boldmath$\scriptstyle V$}}{\mbox{\boldmath$\scriptscriptstyle V$}}\subseteq\mathbb{Z}^{d} , an initial configuration 𝒔 ∈ ℕ d \mathchoice{\mbox{\boldmath$\displaystyle s$}}{\mbox{\boldmath$\textstyle s$}}{\mbox{\boldmath$\scriptstyle s$}}{\mbox{\boldmath$\scriptscriptstyle s$}}\in\mathbb{N}^{d} , and a target configuration 𝒕 ∈ ℕ d \mathchoice{\mbox{\boldmath$\displaystyle t$}}{\mbox{\boldmath$\textstyle t$}}{\mbox{\boldmath$\scriptstyle t$}}{\mbox{\boldmath$\scriptscriptstyle t$}}\in\mathbb{N}^{d} , decide whether starting from 𝒔 \textstyle s , one can iteratively add vectors from 𝑽 \textstyle V to ultimately arrive at a configuration that is larger than or equal to 𝒕 \textstyle t on every coordinate, while not observing any negative value on any coordinate along the way. We consider two natural parameters for the problem: the dimension d d and the size of 𝑽 \textstyle V , defined as the total bitsize of its encoding. We present several results charting the complexity of those two parameterisations, among which the highlight is that coverability for VAS parameterised by the dimension and with all the numbers in the input encoded in unary is complete for the class 𝖷𝖭𝖫 \mathsf{XNL} under PL-reductions. We also discuss open problems in the topic, most notably the question about fixed-parameter tractability for the parameterisation by the size of 𝑽 \textstyle V . \hideLIPIcs Institute of Informatics, University of Warsaw, Poland and https://www.mimuw.edu.pl/˜mp248287/ [email protected]://orcid.org/0000-0001-7891-1988 \flag Flag_of_Europe.pdf \flag LOGO_ERC.pdfThis work is a part of project BOBR that has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No. 948057). Université Paris Cité, CNRS, IRIF, France and https://www.irif.fr/˜schmitz [email protected]://orcid.org/0000-0002-4101-4308 Institute of Informatics, University of Warsaw, Poland and http://henry.sinclair-banks.com [email protected]://orcid.org/0000-0003-1653-4069This work is a part of project INFSYS that has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No. 950398). \Copyright Michał Pilipczuk, Sylvain Schmitz, and Henry Sinclair-Banks {CCSXML} <ccs2012> <concept> <concept_id>10003752.10003809.10010052</concept_id> <concept_desc>Theory of computation Parameterized complexity and exact algorithms</concept_desc> <concept_significance>500</concept_significance> </concept> <concept> <concept_id>10011007.10010940.10010992.10010998.10003791</concept_id> <concept_desc>Software and its engineering Model checking</concept_desc> <concept_significance>500</concept_significance> </concept> <concept> <concept_id>10003752.10003753.10003761</concept_id> <concept_desc>Theory of computation Concurrency</concept_desc> <concept_significance>100</concept_significance> </concept> </ccs2012> \ccsdesc [500]Theory of computation Parameterized complexity and exact algorithms \ccsdesc [500]Software and its engineering Model checking \ccsdesc [100]Theory of computation Concurrency Acknowledgements. This research was initiated during the InfAut 2024 workshop in Warlity Wielkie, Poland. The authors thank the organisers for launching such a fruitful event. \EventEditors John Q. Open and Joan R. Access \EventNoEds 2 \EventLongTitle 42nd Conference on Very Important Topics (CVIT 2016) \EventShortTitle CVIT 2016 \EventAcronym CVIT \EventYear 2016 \EventDate December 24–27, 2016 \EventLocation Little Whinging, United Kingdom \EventLogo \SeriesVolume 42 \ArticleNo 23 keywords vector addition system, Petri net, parameterised complexity, coverability 1 Introduction Vector Addition Systems. Vector addition systems are a well-established model with a very simple definition: a d -dimensional vector addition system (VAS) [ 31 ] is a finite set \textstyle V of vectors in \mathbb{Z}^{d} , which defines a step relation between configurations in \mathbb{N}^{d} : \mathchoice{\mbox{\boldmath$\displaystyle u$}}{\mbox{\boldmath$\textstyle u$}}{\mbox{\boldmath$\scriptstyle u$}}{\mbox{\boldmath$\scriptscriptstyle u$}}\to_{\mathchoice{\mbox{\boldmath$\displaystyle V$}}{\mbox{\boldmath$\textstyle V$}}{\mbox{\boldmath$\scriptstyle V$}}{\mbox{\boldmath$\scriptscriptstyle V$}}}\mathchoice{\mbox{\boldmath$\displaystyle u$}}{\mbox{\boldmath$\textstyle u$}}{\mbox{\boldmath$\scriptstyle u$}}{\mbox{\boldmath$\scriptscriptstyle u$}}+\mathchoice{\mbox{\boldmath$\displaystyle v$}}{\mbox{\boldmath$\textstyle v$}}{\mbox{\boldmath$\scriptstyle v$}}{\mbox{\boldmath$\scriptscriptstyle v$}} for all \textstyle u in \mathbb{N}^{d} and \textstyle v in \textstyle V , provided that \mathchoice{\mbox{\boldmath$\displaystyle u$}}{\mbox{\boldmath$\textstyle u$}}{\mbox{\boldmath$\scriptstyle u$}}{\mbox{\boldmath$\scriptscriptstyle u$}}+\mathchoice{\mbox{\boldmath$\displaystyle v$}}{\mbox{\boldmath$\textstyle v$}}{\mbox{\boldmath$\scriptstyle v$}}{\mbox{\boldmath$\scriptscriptstyle v$}} is in \mathbb{N}^{d} . One usually interprets the d coordinates of a configuration \mathchoice{\mbox{\boldmath$\displaystyle u$}}{\mbox{\boldmath$\textstyle u$}}{\mbox{\boldmath$\scriptstyle u$}}{\mbox{\boldmath$\scriptscriptstyle u$}}\in\mathbb{N}^{d} as d counters that may take non-negative integer values; then \textstyle V represents a set of allowed updates to the counter values, which can be applied only if none of the counters becomes negative. In spite of this apparent simplicity, vector addition systems can exhibit highly complex behaviours. Famously, their reachability problem is \mathsf{ACKERMANN} -complete [ 35 , 34 , 13 ] : given as input a d -dimensional VAS \textstyle V , an initial configuration \mathchoice{\mbox{\boldmath$\displaystyle s$}}{\mbox{\boldmath$\textstyle s$}}{\mbox{\boldmath$\scriptstyle s$}}{\mbox{\boldmath$\scriptscriptstyle s$}}\in\mathbb{N}^{d} , and a target configuration \mathchoice{\mbox{\boldmath$\displaystyle t$}}{\mbox{\boldmath$\textstyle t$}}{\mbox{\boldmath$\scriptstyle t$}}{\mbox{\boldmath$\scriptscriptstyle t$}}\in\mathbb{N}^{d} , the reachability problem asks whether \textstyle t is reachable from \mathchoice{\mbox{\boldmath$\displaystyle s$}}{\mbox{\boldmath$\textstyle s$}}{\mbox{\boldmath$\scriptstyle s$}}{\mbox{\boldmath$\scriptscriptstyle s$}}\in\mathbb{N}^{d} in \textstyle V , i.e., whether \mathchoice{\mbox{\boldmath$\displaystyle s$}}{\mbox{\boldmath$\textstyle s$}}{\mbox{\boldmath$\scriptstyle s$}}{\mbox{\boldmath$\scriptscriptstyle s$}}\to^{\ast}_{\mathchoice{\mbox{\boldmath$\displaystyle V$}}{\mbox{\boldmath$\textstyle V$}}{\mbox{\boldmath$\scriptstyle V$}}{\mbox{\boldmath$\scriptscriptstyle V$}}}\mathchoice{\mbox{\boldmath$\displaystyle t$}}{\mbox{\boldmath$\textstyle t$}}{\mbox{\boldmath$\scriptstyle t$}}{\mbox{\boldmath$\scriptscriptstyle t$}} . This combination of a simple definition with rich behaviours makes vector addition systems—along with the equivalent model of Petri nets—well-suited whenever one needs to model systems managing multiple discrete resources, e.g., threads in concurrent computations, molecules in chemical reactions [ 3 , 4 ] , organisms in biological processes [ 5 ] , etc., but also as a theoretical tool involved in establishing decidability and complexity statements for a variety of decision problems in logic, formal languages, verification, etc. [ 42 , Section 5] . The Coverability Problem. In this note, we are interested in a decision problem with a less extreme complexity: given the same input, the coverability problem asks whether there exists a coordinate-wise larger or equal configuration \mathchoice{\mbox{\boldmath$\displaystyle t$}}{\mbox{\boldmath$\textstyle t$}}{\mbox{\boldmath$\scriptstyle t$}}{\mbox{\boldmath$\scriptscriptstyle t$}}^{\prime}\sqsupseteq\mathchoice{\mbox{\boldmath$\displaystyle t$}}{\mbox{\boldmath$\textstyle t$}}{\mbox{\boldmath$\scriptstyle t$}}{\mbox{\boldmath$\scriptscriptstyle t$}} such that \mathchoice{\mbox{\boldmath$\displaystyle s$}}{\mbox{\boldmath$\textstyle s$}}{\mbox{\boldmath$\scriptstyle s$}}{\mbox{\boldmath$\scriptscriptstyle s$}}\to^{\ast}_{\mathchoice{\mbox{\boldmath$\displaystyle V$}}{\mbox{\boldmath$\textstyle V$}}{\mbox{\boldmath$\scriptstyle V$}}{\mbox{\boldmath$\scriptscriptstyle V$}}}\mathchoice{\mbox{\boldmath$\displaystyle t$}}{\mbox{\boldmath$\textstyle t$}}{\mbox{\boldmath$\scriptstyle t$}}{\mbox{\boldmath$\scriptscriptstyle t$}}^{\prime} . This relaxation of the reachability problem was first shown decidable by Karp and Miller [ 31 ] , before being proven \mathsf{EXPSPACE} -hard by Lipton [ 36 ] and to belong to \mathsf{EXPSPACE} by Rackoff [ 40 ] . Like reachability, coverability in vector addition systems inter-reduces with numerous decision problems, notably in relation to the automated verification of safety properties in concurrent or distributed systems [ 30 , 29 , 22 , 16 , 18 , 23 , 2 , 6 ] , as well as reasoning on data-aware logics or systems [ 15 , 25 , 1 ] . These applications have motivated a thorough investigation of the problem [ 31 , 36 , 40 , 9 , 33 , 32 , 44 ] and the development of several tools specifically targeted at solving it [ 19 , 8 , 24 ] . Towards Parameterised Complexity. Rosier and Yen [ 41 ] refined Rackoff’s analysis to identify the contribution of several parameters to the final complexity of the coverability problem. Among those, the main parameter driving the complexity is the dimension , i.e., the number of counters of the system. Indeed, Rackoff obtains his result by showing a bound on the length of the shortest covering runs from the source to the target configuration, which is in n^{2^{\mathcal{O}(d\log d)}} when parameterised by the dimension d , where n is the size of the input encoded in unary. (While \mathsf{EXPSPACE} -completeness holds with both a unary and a binary encoding, the complexity landscape changes as soon as one isolates the dimension as a parameter). This upper bound on the length of shortest covering runs in unary-encoded VAS was recently improved to n^{2^{\mathcal{O}(d)}} by Künnemann, Mazowiecki, Schütze, Sinclair-Banks, and Węgrzycki [ 32 , Theorem 3.3] , and this matches the n^{2^{\Omega(d)}} lower bound in the family of systems constructed by Lipton [ 36 ] . In turn, this upper bound on the length of the shortest covering runs entails that the coverability problem with a unary encoding can be solved either in non-deterministic space 2^{\mathcal{O}(d)}\cdot\log n or in deterministic time n^{2^{\mathcal{O}(d)}} [ 32 , Corollary 3.4] ; moreover, the latter time bound is also achieved by

Read the complete text