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.

Authors

• Eugene Asarin
• Venkatesh P. Mysore
• Amir Pnueli
• Gerardo Schneider

Keywords

• Hybrid systems
• Undecidability
• Piece-wise affine maps
• (Hierarchical) piece-wise constant derivative systems