Page 6 - 《软件学报》2026年第1期

陈蔚骏 等: 向量加法系统可达性问题复杂性下界研究综述 3

去理解和分析相关研究, 在此基础上我们也指出了下界研究工作下一步最可能的突破方向.
本文第 1 节形式化定义向量加法系统、可达性问题及一些重要的等价模型. 第 2 节总结低维 VASS 可达性问
题的完备性结论和核心研究技术. 第 3 节陈述 d-VASS 可达性问题关于维度的参数复杂性下界和相关技术. 第 4
节总结近年来固定维 VASS 可达性问题的研究进展. 第 5 节对未来研究方向进行展望和总结.
1 预备知识

本节给出加法向量系统及可达性问题的形式化定义, 定义向量加法系统的等价模型 (即计数器程序), 并介绍
与本文相关的复杂性类. 注意, 本文涵盖大量数学证明, 故后续章节中使用了较多的数学符号, 其各自的含义在相
关上下文中均有对应解释. 同时, 为了进一步帮助读者了解本文乃至 VASS 研究领域的符号使用惯例, 我们也在附
录 A 中给出主要符号对照表, 供读者参考.
1.1 向量加法系统
本文用 N, Z 分别表示自然数集与整数集, 定义 N ω := N∪{ω}, 其中, ω 是最小的极限序数. u, v 通常用于表示
d
,
向量, d ∈ N 通常用于表示向量维度, 例如, u ∈ N 表示一个 d 维的自然数向量. 定义 [d] := {1,2,...,d} [d] 0 := [d]∪
i
{0}. 向量 u 的第 个元素 ( i ∈ [d]) 表示为 u(i), 其无穷范数定义为 ∥u∥ = max i∈[d] |u(i)|. 用 0 d 表示全零向量, 常将下标
d 略去而直接写作 0.
一个向量加法系统 (VAS) 是一个二元组 V = (d,A), 其中, d 指定了该系统的维度, A ⊆ Z 为有限集, 表示系统
d
的迁移规则 (transition). 系统 V 某时刻的格局 (configuration) 用 N 中的向量表示. 给定格局 u, v, 若存在 a ∈ A 使得
d
a a a 1
u+ a = v, 称 u 可通过规则 a 一步迁移到 v, 记作 u→ V v, 在上下文清晰时也简写为 u → v. 有限长的迁移序列 u 0 →
π
π
a n
a 2
u 1 → ... → u n 常称作运行 (run), 简记作 u 0 → u n , 其中, π = a 1 ... a n ∈ A . 若有某个动作序列 π 使得 u 0 → u n , 称 u n 是
∗
从 u 0 出发可达的, 记作 u 0 → V u n , 此时 π 称作可达性证据 (witness).
带状态的向量加法系统 (VASS) 可用三元组 V = (d,Q,T) 表示. 其中, d 指定了系统的维度, Q 为有限的状态
d
d
集, 有限集 T ⊆ Q×Z × Q 是系统迁移规则. VASS 的格局 α = (p,u) ∈ Q×N 记录系统的状态和向量值, 有时也写作
t
p(u). 给定格局 p(u), q(v), 若存在 t = (p, a,q) ∈ T 使得 u+ a = v, 称 p(u) 可通过规则 t 迁移到 q(v), 记作 p(u) → q(v).
π
t 2
t 1
t n
∗
同理称 α 0 → α 1 → ... → α n 为 VASS 的一次运行, 并简写作 α 0 → α n , 其中, π = t 1 ...t n ∈ T . 用 α 0 → V α n 表示 V 中 α n
(
从 α 0 出发可达. (带状态的) d 维向量加法系统常记作 d-VAS d-VASS).
例 1: 给定非负整数 k, 定义 2-VAS V 1 = (2,{a 1 , a 2 }), 其中, a 1 = (−1,1), a 2 = (k,−1). 给定格局 u = (m,0), 容易验
a 2
m m
2
证 u→ V 1 (km,0), 对应的证据为 π = a a . 需注意, u → (m+k,−1) 不是一个合法迁移, 因为所有格局都必须是 N 中
1 2
的向量. 本例说明, 2 维 VAS 可完成数乘计算.
例 2: 定义 3-VASS V 2 = (3,{p,q},{t 1 ,t 2 ,t 3 ,t 4 }), 其中,

t 1 = (p,(−1,1,0), p), t 2 = (p,(0,0,0),q), t 3 = (q,(k,−1,0),q), t 4 = (q,(0,0,−1), p).
V 2 表示为图 1 α 0 = p(1,0,n), 考
为了更直观地表示迁移关系, 我们将 中带标签的多重有向图. 给定初始格局
m m
虑形如 π m = t t 2 t t 4 的规则序列, 易知从 α 0 出发有如下运行:
1 3

π k 0 π k 1 ( ) π k 2 π k n−1
n
α 0 −−→p(k,0,n−1)−−→p k ,0,n−2 −−→...−−−→p(k ,0,0).
2

(0, 0, 0)
(−1, 1, 0) p q (k, −1, 0)
(0, 0, −1)
V 2 的有向图表示
图 1

此 VASS 是取自文献 [12] 的经典例子, 说明了 VASS 在可达性意义下能完成指数运算.
显然 VAS 可被看作状态集 Q 是单元集的特殊 VASS. 因此所有 VAS 的行为都可以使用一个对应的 VASS 来