Reachability and mortality are fundamental problems in the study of hybrid dynamical systems. Reachability investigates whether a system can evolve from an initial state to a designated target state, while mortality asks whether the system inevitably halts or reaches a deadlock state under its given dynamics. In this work, we study these problems for two-dimensional restricted hierarchical piecewise constant derivative systems ( \(2\) -RHPCD), a class characterised by a hierarchical structure and piecewise-constant dynamics. We prove that both reachability and mortality are co-NP-hard for bounded \(2\) -RHPCD systems. In particular, our result resolves the open question posed in [4] concerning the complexity of the mortality problem for \(2\) -RHPCD systems.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Reachability and Mortality for Two-Dimensional RHPCD Systems Are co-NP-hard

  • Olga Tveretina

摘要

Reachability and mortality are fundamental problems in the study of hybrid dynamical systems. Reachability investigates whether a system can evolve from an initial state to a designated target state, while mortality asks whether the system inevitably halts or reaches a deadlock state under its given dynamics. In this work, we study these problems for two-dimensional restricted hierarchical piecewise constant derivative systems ( \(2\) -RHPCD), a class characterised by a hierarchical structure and piecewise-constant dynamics. We prove that both reachability and mortality are co-NP-hard for bounded \(2\) -RHPCD systems. In particular, our result resolves the open question posed in [4] concerning the complexity of the mortality problem for \(2\) -RHPCD systems.