Lics

ACM/IEEE Symposium on Logic in Computer Science

LICS Home - LICS Awards - LICS Newsletters - LICS Archive - LICS Organization - Logic-Related Conferences - Links

Forty-First Annual Symposium on

Logic in Computer Science (LICS 2026)

Paper: Reachability in VASS Extended with Integer Counters (at LICS 2026)

Authors: Clotilde Bizière Wojciech Czerwiński Roland Guttenberg Jérôme Leroux Vincent Michielini Łukasz Orlikowski Antoni Puch Henry Sinclair-Banks

Open access: https://doi.org/10.4230/LIPIcs.LICS.2026.19

Abstract

We consider a variant of VASS extended with integer counters, denoted VASS+ℤ. These are automata equipped with ℕ- and ℤ-counters; the ℕ-counters are required to remain nonnegative and the ℤ-counters do not have this restriction. We study the complexity of the reachability problem for VASS+ℤ when the number of ℕ-counters is fixed. We show that reachability is NP-complete in 1-VASS+ℤ (i.e. when there is only one ℕ-counter) regardless of unary or binary encoding. For d ≥ 2, using a KLMST-based algorithm, we prove that reachability in d-VASS+ℤ lies in the complexity class ℱ_{d+2}. Our upper bound improves on the naively obtained Ackermannian complexity by simulating the ℤ-counters with ℕ-counters. To complement our upper bounds, we show that extending VASS with integer counters significantly lowers the number of ℕ-counters needed to exhibit hardness. We prove that reachability in unary 2-VASS+ℤ is PSpace-hard; without ℤ-counters this lower bound is only known in dimension 5. We also prove that reachability in unary 3-VASS+ℤ is Tower-hard. Without ℤ-counters, reachability in 3-VASS has elementary complexity and Tower-hardness is only known in dimension 8.

BibTeX

  @InProceedings{BiziereCzerwinskiGu-ReachabilityinVASSE,
    author = 	 {Clotilde Bizière and Wojciech Czerwiński and Roland Guttenberg and Jérôme Leroux and Vincent Michielini and Łukasz Orlikowski and Antoni Puch and Henry Sinclair-Banks},
    title = 	 {Reachability in VASS Extended with Integer Counters},
    booktitle =  {Proceedings of the Forty-First Annual Symposium on Logic in Computer Science (LICS 2026)},
    year =	 {2026},
    month =	 {July}, 
    pages =      {19:1--19:26},
    location =   {Lisbon, Portugal}, 
    publisher =	 {Schloss Dagstuhl -- Leibniz-Zentrum für Informatik},
    doi =        {10.4230/LIPIcs.LICS.2026.19}
  }
   

Last modified: 2026-09-2114:25
Sam Staton