论文标题
明确的瓦斯的普遍问题
Universality Problem for Unambiguous VASS
论文作者
论文摘要
我们研究了明确的VASS语言，即与状态的矢量增加系统，其过渡读取了有限字母的字母，并且其接受条件是由一组最终状态（即覆盖性语言）定义的。我们表明，明确的VASS的普遍性问题是Expass-Complete，与Ackermann的完整性形成了鲜明的对比，即使在维度1中。
We study languages of unambiguous VASS, that is, Vector Addition Systems with States, whose transitions read letters from a finite alphabet, and whose acceptance condition is defined by a set of final states (i.e., the coverability language). We show that the problem of universality for unambiguous VASS is ExpSpace-complete, in sheer contrast to Ackermann-completeness for arbitrary VASS, even in dimension 1. When the dimension d is fixed, the universality problem is PSpace-complete if d is at least 2, and coNP-hard for 1-dimensional VASSes (also known as One Counter Nets).
