Reachability in VASS Extended with Integer Counters
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866918372805967872 |
|---|---|
| author | Bizière, Clotilde Czerwiński, Wojciech Guttenberg, Roland Leroux, Jérôme Michielini, Vincent Orlikowski, Łukasz Puch, Antoni Sinclair-Banks, Henry |
| author_facet | Bizière, Clotilde Czerwiński, Wojciech Guttenberg, Roland Leroux, Jérôme Michielini, Vincent Orlikowski, Łukasz Puch, Antoni Sinclair-Banks, Henry |
| contents | We consider a variant of VASS extended with integer counters, denoted VASS+Z. These are automata equipped with N and Z counters; the N-counters are required to remain nonnegative and the Z-counters do not have this restriction. We study the complexity of the reachability problem for VASS+Z when the number of N-counters is fixed. We show that reachability is NP-complete in 1-VASS+Z (i.e. when there is only one N-counter) regardless of unary or binary encoding. For $d \geq 2$, using a KLMST-based algorithm, we prove that reachability in d-VASS+Z lies in the complexity class $\mathcal{F}_{d+2}$. Our upper bound improves on the naively obtained Ackermannian complexity by simulating the Z-counters with N-counters.
To complement our upper bounds, we show that extending VASS with integer counters significantly lowers the number of N-counters needed to exhibit hardness. We prove that reachability in unary 2-VASS+Z is PSPACE-hard; without Z-counters this lower bound is only known in dimension 5. We also prove that reachability in unary 3-VASS+Z is TOWER-hard. Without Z-counters, reachability in 3-VASS has elementary complexity and TOWER-hardness is only known in dimension 8. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_05221 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Reachability in VASS Extended with Integer Counters Bizière, Clotilde Czerwiński, Wojciech Guttenberg, Roland Leroux, Jérôme Michielini, Vincent Orlikowski, Łukasz Puch, Antoni Sinclair-Banks, Henry Formal Languages and Automata Theory We consider a variant of VASS extended with integer counters, denoted VASS+Z. These are automata equipped with N and Z counters; the N-counters are required to remain nonnegative and the Z-counters do not have this restriction. We study the complexity of the reachability problem for VASS+Z when the number of N-counters is fixed. We show that reachability is NP-complete in 1-VASS+Z (i.e. when there is only one N-counter) regardless of unary or binary encoding. For $d \geq 2$, using a KLMST-based algorithm, we prove that reachability in d-VASS+Z lies in the complexity class $\mathcal{F}_{d+2}$. Our upper bound improves on the naively obtained Ackermannian complexity by simulating the Z-counters with N-counters. To complement our upper bounds, we show that extending VASS with integer counters significantly lowers the number of N-counters needed to exhibit hardness. We prove that reachability in unary 2-VASS+Z is PSPACE-hard; without Z-counters this lower bound is only known in dimension 5. We also prove that reachability in unary 3-VASS+Z is TOWER-hard. Without Z-counters, reachability in 3-VASS has elementary complexity and TOWER-hardness is only known in dimension 8. |
| title | Reachability in VASS Extended with Integer Counters |
| topic | Formal Languages and Automata Theory |
| url | https://arxiv.org/abs/2603.05221 |