Reachability in 3-VASS is Elementary
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866909596017229824 |
|---|---|
| author | Czerwiński, Wojciech Jecker, Ismaël Lasota, Sławomir Orlikowski, Łukasz |
| author_facet | Czerwiński, Wojciech Jecker, Ismaël Lasota, Sławomir Orlikowski, Łukasz |
| contents | The reachability problem in 3-dimensional vector addition systems with states (3-VASS) is known to be PSpace-hard, and to belong to Tower. We significantly narrow down the complexity gap by proving the problem to be solvable in doubly-exponential space. The result follows from a new upper bound on the length of the shortest path: if there is a path between two configurations of a 3-VASS then there is also one of at most triply-exponential length. We show it by introducing a novel technique of approximating the reachability sets of 2-VASS by small semi-linear sets. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_13916 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Reachability in 3-VASS is Elementary Czerwiński, Wojciech Jecker, Ismaël Lasota, Sławomir Orlikowski, Łukasz Formal Languages and Automata Theory Logic in Computer Science The reachability problem in 3-dimensional vector addition systems with states (3-VASS) is known to be PSpace-hard, and to belong to Tower. We significantly narrow down the complexity gap by proving the problem to be solvable in doubly-exponential space. The result follows from a new upper bound on the length of the shortest path: if there is a path between two configurations of a 3-VASS then there is also one of at most triply-exponential length. We show it by introducing a novel technique of approximating the reachability sets of 2-VASS by small semi-linear sets. |
| title | Reachability in 3-VASS is Elementary |
| topic | Formal Languages and Automata Theory Logic in Computer Science |
| url | https://arxiv.org/abs/2502.13916 |