paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Reachability in Vector Addition Systems is Primitive-Recursive in Fixed Dimension

固定维数下向量加法系统的可达性是原始递归的
LICS 2019 34th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)2019匹配度 2/10 · 该论文属于向量加法系统可达性的纯理论复杂度研究,与形式验证/静态验证有间接关联,但不涉及 LLM/Agent、浮点程序分析、贝叶斯程序分析或 ML/Agentic 程序静态分析等用户核心方向。其理论结果本身也不涉及工程实现、工业落地或 benchmark 设计。引用 63 inbox
Jerome Leroux, Sylvain Schmitz
crossref: 2026-09-12

AI 速览

一句话:通过改进经典分解算法及其终止性证明,将固定维数 VAS 可达性上界降至原始递归,并给出一般情形的 ACKERMANN 上界。

向量加法系统(VAS)的可达性是静态验证及众多可相互归约判定问题的核心。此前即使固定维数,已知上界也不是原始递归的。本文精细改进 Mayr、Kosaraju 与 Lambert 的经典分解算法及其终止性证明,重新分析分解树与递推复杂度,从而在一般情形得到 ACKERMANN 上界,在固定维数得到原始递归上界。该结果虽未达到已知的 TOWER 下界,但对若干相关问题是紧的。

问题
VAS 可达性问题的计算复杂度上界,尤其固定维数下能否低于非原始递归。
方法
细化 Mayr–Kosaraju–Lambert 分解算法及终止性证明,分析分解树与递推复杂度。
评估
证明一般情形 ACKERMANN 上界、固定维数原始递归上界,并与 TOWER 下界及相关问题最优性比较。
原文摘要(Abstract)

The reachability problem in vector addition systems is a central question, not only for the static verification of these systems, but also for many inter-reducible decision problems occurring in various fields. The currently best known upper bound on this problem is not primitive-recursive, even when considering systems of fixed dimension. We provide significant refinements to the classical decomposition algorithm of Mayr, Kosaraju, and Lambert and to its termination proof, which yield an ACKERMANN upper bound in the general case, and primitive-recursive upper bounds in fixed dimension. While this does not match the currently best known TOWER lower bound for reachability, it is optimal for related problems.

链接与引用

DOI 原文 · PDF(开放获取) ·

BibTeX
@inproceedings{paperbot5013,
  title = {Reachability in Vector Addition Systems is Primitive-Recursive in Fixed Dimension},
  author = {Jerome Leroux and Sylvain Schmitz},
  booktitle = {LICS},
  year = {2019},
  doi = {10.1109/lics.2019.8785796}
}