Reachability and Mortality Problems for Restricted Hierarchical Piecewise Constant Derivatives
Reachability and Mortality Problems for Restricted Hierarchical Piecewise Constant Derivatives
复制标题
受限分层分段常数导数的可达性和死亡率问题
DOI：
--
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
L. Jackson
中科院分区：
文献类型：
--
作者：
Paul C. Bell;Shang Chen;L. Jackson
我们展示了分段常导数 (PCD) 系统的三维变体（称为有界 3 维受限分层 PCD (3-RHPCD)）的可达性和死亡率问题的 NP 难度。这两个问题都显示在 PSPACE 中，即使对于 n 维 RHPCD 也是如此。这是一个受限模型，与文献中的其他模型（例如秒表自动机、矩形自动机和 PCD）相似。我们还表明，对于无界 3-RHPCD，通过明斯基机的模拟，这两个问题都变得不可判定。
We show the NP-hardness of the reachability and mortality problems for a three dimensional variant of Piecewise Constant Derivative (PCD) system called a bounded 3-dimensional Restricted Hierarchical PCD (3-RHPCD). Both problems are shown to be in PSPACE, even for n-dimensional RHPCD. This is a restricted model with similarities to other models in the literature such as stopwatch automata, rectangular automata and PCDs. We also show that for an unbounded 3-RHPCD, both problems become undecidable via a simulation of a Minsky machine.