Reachability Problems for Hierarchical Piecewise Constant Derivative Systems

Bell, Paul C.; Chen, Shang

Abstract

In this paper, we investigate the computability and complexity of reachability problems for two-dimensional hierarchical piecewise constant derivative (HPCD) systems. The main interest in HPCDs stems from the fact that their reachability problem is on the border between decidability and undecidability, since it is equivalent to that of reachability for one-dimensional piecewise affine maps (PAMs) which is a long standing open problem. Understanding the most expressive hybrid system models that retain decidability for reachability has generated a great deal of interest over the past few years. In this paper, we show a restriction of HPCDs (called RHPCDs) which leads to the reachability problem becoming decidable. We then study which additional powers we must add to the RHPCD model to render it 1D PAM-equivalent. Finally, we show NP-hardness of reachability for nondeterministic RHPCDs.

Citation

Bell, P. C., & Chen, S. (2013). Reachability Problems for Hierarchical Piecewise Constant Derivative Systems. In Reachability Problems. RP 2013. Lecture Notes in Computer Science, vol 8169 (46-58). https://doi.org/10.1007/978-3-642-41036-9_6

• Conference Name: Reachability Problems 7th International Workshop, RP 2013
• Conference Location: Uppsala, Sweden
• Start Date: Sep 24, 2013
• End Date: Sep 26, 2013
• Publication Date: 2013
• Deposit Date: Dec 12, 2023
• Publisher: Springer
• Pages: 46-58
• Series Title: Lecture Notes in Computer Science
• Series ISSN: 0302-9743; 1611-3349
• Book Title: Reachability Problems. RP 2013. Lecture Notes in Computer Science, vol 8169
• ISBN: 9783642410352; 9783642410369
• DOI: https://doi.org/10.1007/978-3-642-41036-9_6
• Keywords: Hybrid System; Successor Function; Hybrid Automaton; Initial Interval; Reachability Problem
• Publisher URL: https://link.springer.com/chapter/10.1007/978-3-642-41036-9_6