Reachability in Two-Dimensional Unary Vector Addition Systems with States is NL-Complete
Reachability in Two-Dimensional Unary Vector Addition Systems with States is NL-Complete
复制标题
具有状态的二维一元向量加法系统的可达性是 NL 完全的
DOI：
10.1145/2933575.2933577
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Englert M
中科院分区：
文献类型：
--
作者：
Englert M
Blondin等人在2015年的LICS上表明，具有状态的二维向量加法系统具有状态数的长度指数和向量范数的多项式的可达性证据。由此产生的猜测和验证算法是最佳的（PSPACE），但只有当输入向量是以二进制形式给出的。我们积极回答他们的工作留下的主要问题，即建立伪多项式长度的可达性证人总是存在的。因此，当输入向量以一元形式给出时，改进的猜测和验证算法只需要对数空间。
Blondin et al. showed at LICS 2015 that two-dimensional vector addition systems with states have reachability witnesses of length exponential in the number of states and polynomial in the norm of vectors. The resulting guess-and-verify algorithm is optimal (PSPACE), but only if the input vectors are given in binary. We answer positively the main question left open by their work, namely establish that reachability witnesses of pseudo-polynomial length always exist. Hence, when the input vectors are given in unary, the improved guess-and-verify algorithm requires only logarithmic space.