论文标题
关于历史确定的单场网
On History-Deterministic One-Counter Nets
论文作者
论文摘要
我们考虑历史确定性的单场网（OCN）的模型。历史确定性是过渡系统的属性，它允许有限的非确定性主义可以“直接”解决。代币游戏被用来表征各种模型的历史确定性，也表征了OCN的历史确定性。通过将1句话的游戏减少到模拟游戏，我们可以证明检查OCN的历史确定性是可以决定的。此外，我们证明了此问题对于过渡的一致编码而言是PSPACE完整的，并且用于二进制编码的expspace commetter。 然后，我们研究历史确定性OCN的语言特性。我们表明，针对历史确定性OCN的非确定性解析器最终是周期性的。结果，对于给定的历史确定性的OCN，我们构建了语言等效的确定性单场自动机。我们还显示了比较历史准确性OCN的语言的可决定性，例如语言包容性和语言普遍性。
We consider the model of history-deterministic one-counter nets (OCNs). History-determinism is a property of transition systems that allows for a limited kind of non-determinism which can be resolved 'on-the-fly'. Token games, which have been used to characterise history-determinism over various models, also characterise history-determinism over OCNs. By reducing 1-token games to simulation games, we are able to show that checking for history-determinism of OCNs is decidable. Moreover, we prove that this problem is PSPACE-complete for a unary encoding of transitions, and EXPSPACE-complete for a binary encoding. We then study the language properties of history-deterministic OCNs. We show that the resolvers of non-determinism for history-deterministic OCNs are eventually periodic. As a consequence, for a given history-deterministic OCN, we construct a language equivalent deterministic one-counter automaton. We also show the decidability of comparing languages of history-deterministic OCNs, such as language inclusion and language universality.
