论文标题
在非负合理中加权自动机的界限和零隔离问题
The boundedness and zero isolation problems for weighted automata over nonnegative rationals
论文作者
论文摘要
我们考虑在非负合理的半含量上进行线性成本注册自动机（相当于加权自动机），这将概率自动机推广。有界性和零隔离的两个问题询问是否有一系列单词分别收敛到无穷大和零。在一般模型中，这两个问题都是不可决定的，因此我们专注于无拷贝线性限制。在那里，我们表明有界问题是可以决定的。 至于零隔离问题，我们需要进一步限制类。我们获得了一个模型，其中零隔离变得等同于矫形矢量添加系统（OVAS）的通用覆盖能力，这是VAS家族中一种新模型的有趣。在标准的VAS中，仅在正矫正处考虑，而在卵子中，每个矫正器都有自己的一组向量，可以在该矫正中应用。假设Schanuel的猜想是正确的，我们证明了对三维OVA的普遍覆盖性的可决定性，这意味着在最多具有三个独立寄存器的模型中，零隔离性的可决定性。
We consider linear cost-register automata (equivalent to weighted automata) over the semiring of nonnegative rationals, which generalise probabilistic automata. The two problems of boundedness and zero isolation ask whether there is a sequence of words that converge to infinity and to zero, respectively. In the general model both problems are undecidable so we focus on the copyless linear restriction. There, we show that the boundedness problem is decidable. As for the zero isolation problem we need to further restrict the class. We obtain a model, where zero isolation becomes equivalent to universal coverability of orthant vector addition systems (OVAS), a new model in the VAS family interesting on its own. In standard VAS runs are considered only in the positive orthant, while in OVAS every orthant has its own set of vectors that can be applied in that orthant. Assuming Schanuel's conjecture is true, we prove decidability of universal coverability for three-dimensional OVAS, which implies decidability of zero isolation in a model with at most three independent registers.
