The Polyhedron-Hitting Problem
The Polyhedron-Hitting Problem
复制标题
多面体撞击问题
DOI：
10.1137/1.9781611973730.64
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
Chonev V
中科院分区：
文献类型：
--
作者：
Chonev V
我们考虑 Kannan 和 Lip-ton 轨道问题 [14, 13] 的多面体版本 - 确定在环境向量空间 ℚm 中重复应用线性变换 A 时是否可以从起点 x 到达目标多面体 V。在程序验证的背景下，Lee 和 Yannakakis 在 [15] 中以及 Braverman 在 [4] 中也考虑了非常相似的可达性问题并保留了开放性。我们提出了多面体击中问题的可判定性景观的完整特征，表示为环境空间维度 m 以及多面体目标 V 的维度的函数：更准确地说，对于每一对维度，我们要么建立可判定性，要么显示长期存在的数论开放问题的硬度。
We consider polyhedral versions of Kannan and Lip-ton's Orbit Problem [14, 13]—determining whether a target polyhedronVmay be reached from a starting pointxunder repeated applications of a linear transformationAin an ambient vector space ℚm. In the context of program verification, very similar reachability questions were also considered and left open by Lee and Yannakakis in [15], and by Braverman in [4]. We present what amounts to a complete characterisation of the decidability landscape for the Polyhedron-Hitting Problem, expressed as a function of the dimensionmof the ambient space, together with the dimension of the polyhedral targetV: more precisely, for each pair of dimensions, we either establish decidability, or show hardness for longstanding number-theoretic open problems.
登录
查看更多内容
论轨道问题的复杂性
影响因子：
2.5
作者：
Ventsislav Chonev;Joël Ouaknine;J. Worrell
通讯作者：
J. Worrell
DOI：
10.1145/2488608.2488728
发表时间：
2013
期刊：
ArXiv
影响因子：
--
作者：
Ventsislav Chonev;Joël Ouaknine;J. Worrell
通讯作者：
J. Worrell
DOI：
10.1137/1.9781611973402.27
发表时间：
2013-07
期刊：
ArXiv
影响因子：
--
作者：
Joël Ouaknine;J. Worrell
通讯作者：
Joël Ouaknine;J. Worrell
评论：Thomas W. Cusick 和 Mary E. Flahive，马可夫谱和拉格朗日谱
DOI：
--
发表时间：
1991
期刊：
影响因子：
--
作者：
J. Vaaler
通讯作者：
J. Vaaler
线性映射和正则语言的轨道
DOI：
--
发表时间：
2010
期刊：
Computer Science Symposium in Russia
影响因子：
--
作者：
S. Tarasov;M. Vyalyi
通讯作者：
M. Vyalyi