论文标题
单场网的参数性通用问题
Parametrized Universality Problems for One-Counter Nets
论文作者
论文摘要
我们研究单场网的语言普遍性问题，也称为具有状态（1个比）的1维矢量添加系统，具有初始反值的参数化，或在运行过程中允许的反值上的上限。 OCN接受的语言（通过达到最终控制状态定义）在两个参数中都是单调的。这产生了两个自然问题：1）是否存在使语言通用的初始反价值？ 2）是否存在足够高的天花板，以使有限语言是普遍的？尽管普通的普遍性问题是可决定的（并且是Ackermann complete），而这些参数化的问题似乎减少到检查基础自动机的基本结构特性，但我们表明实际上两个问题都是不可避免的。我们还研究了几个可确定子类的问题的复杂性，即明确的和确定性的系统，以及单行字母内的问题。
We study the language universality problem for One-Counter Nets, also known as 1-dimensional Vector Addition Systems with States (1-VASS), parameterized either with an initial counter value, or with an upper bound on the allowed counter value during runs. The language accepted by an OCN (defined by reaching a final control state) is monotone in both parameters. This yields two natural questions: 1) Does there exist an initial counter value that makes the language universal? 2) Does there exist a sufficiently high ceiling so that the bounded language is universal? Although the ordinary universality problem is decidable (and Ackermann-complete) and these parameterized problems seem to reduce to checking basic structural properties of the underlying automaton, we show that in fact both problems are undecidable. We also look into the complexities of the problems for several decidable subclasses, namely for unambiguous, and deterministic systems, and for those over a single-letter alphabet.
