...
首页> 外文期刊>Information and computation >Low dimensional hybrid systems - decidable, undecidable, don't know
【24h】

Low dimensional hybrid systems - decidable, undecidable, don't know

机译:低维混合动力系统-可判定,不可判定,不知道

获取原文
获取原文并翻译 | 示例
           

摘要

Even though many attempts have been made to define the boundary between decidable and undecidable hybrid systems, the affair is far from being resolved. More and more low dimensional systems are being shown to be undecidable with respect to reachability, and many open problems in between are being discovered. In this paper, we present various two-dimensional hybrid systems for which the reachability problem is undecidable. We show their undecidability by simulating Minsky machines. Their proximity to the decidability frontier is understood by inspecting the most parsimonious constraints necessary to make reachability over these automata decidable. We also show that for other two-dimensional systems, the reachability question remains unanswered, by proving that it is as hard as the reachability problem for piecewise affine maps on the real line, which is a well known open problem.
机译:尽管已经进行了许多尝试来确定可决定的和不可决定的混合系统之间的边界,但是这件事远未解决。对于可到达性,越来越多的低维系统被显示为不确定的,并且在它们之间发现了许多未解决的问题。在本文中,我们提出了无法确定可达性问题的各种二维混合系统。我们通过模拟Minsky机器来显示它们的不确定性。通过检查使这些自动机可确定性达到可及性所必需的最简约约束,可以了解它们与可确定性边界的接近性。我们还证明,对于其他二维系统,可达性问题仍然没有得到答案,方法是证明它与实线上的分段仿射图的可达性问题一样困难,这是众所周知的开放问题。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱:kefu@zhangqiaokeyan.com

京公网安备:11010802029741号 ICP备案号:京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有
  • 客服微信

  • 服务号