Reversal-Bounded Counter Machines Revisited
Reversal-Bounded Counter Machines Revisited
复制标题
重新审视有反转限制的计数器机
DOI：
--
复制
发表时间：
2008
期刊：
影响因子：
--
通讯作者：
Arnaud Sangnier
中科院分区：
文献类型：
--
作者：
A. Finkel;Arnaud Sangnier
我们扩展类的反向有界计数器机授权有限数量的交替之间的增加和减少模式在一个给定的界限。我们证明了扩展的反向有界计数器机也有有效的半线性可达集。我们还证明了反向有界的性质是不可判定的，即使我们固定的界限，而这个问题成为可判定的考虑向量加法系统的状态。
We extend the class of reversal-bounded counter machines by authorizing a finite number of alternations between increasing and decreasing mode over a given bound. We prove that extended reversal-bounded counter machines also have effective semi-linear reachability sets. We also prove that the property of being reversal-bounded is undecidable in general even when we fix the bound, whereas this problem becomes decidable when considering Vector Addition System with States.