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

详细信息    查看全文

• 作者：Eugene Asarin^a ; ^{asarin@liafa.jussieu.fr} ; Venkatesh P. Mysore^b ; ¹ ; ^{venkatesh.mysore@deshawresearch.com} ; Amir Pnueli^b ; ² ; Gerardo Schneider^c ; ^d ; ^{gersch@chalmers.se}
• 关键词：Hybrid systems ; Undecidability ; Piece-wise affine maps ; (Hierarchical) piece-wise constant derivative systems
• 刊名：Information and Computation
• 出版年：2012
• 出版时间：February 2012
• 年：2012
• 卷：211
• 期：Complete
• 页码：138-159
• 全文大小：591 K

文摘

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.