Loughborough University
Browse
BellChenJackTCS.pdf (557.58 kB)

On the decidability and complexity of problems for restricted hierarchical hybrid systems

Download (557.58 kB)
journal contribution
posted on 2016-11-11, 10:37 authored by Paul Bell, Shang Chen, Lisa JacksonLisa Jackson
We study variants of a recently introduced hybrid system model, called a Hierarchical Piecewise Constant Derivative (HPCD). These variants (loosely called Restricted HPCDs) form a class of natural models with similarities to many other well known hybrid system models in the literature such as Stopwatch Automata, Rectangular Automata and PCDs. We study the complexity of reachability and mortality problems for variants of RHPCDs and show a variety of results, depending upon the allowed powers. These models form a useful tool for the study of the complexity of such problems for hybrid systems, due to their connections with existing models. We show that the reachability problem and the mortality problem are co-NP-hard for bounded 3-dimensional RHPCDs (3-RHPCDs). Reachability is shown to be in PSPACE, even for n-dimensional RHPCDs. We show that for an unbounded 3-RHPCD, the reachability and mortality problems become undecidable. For a nondeterministic variant of 2-RHPCDs, the reachability problem is shown to be PSPACE-complete.

History

School

  • Science

Department

  • Computer Science

Published in

Theoretical Computer Science

Volume

652

Pages

47 - 63 (16)

Citation

BELL, P.C., CHEN, S. and JACKSON, L.M., 2016. On the decidability and complexity of problems for restricted hierarchical hybrid systems. Theoretical Computer Science, 652, pp. 47-63.

Publisher

© Elsevier

Version

  • AM (Accepted Manuscript)

Publisher statement

This work is made available according to the conditions of the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International (CC BY-NC-ND 4.0) licence. Full details of this licence are available at: https://creativecommons.org/licenses/by-nc-nd/4.0/

Acceptance date

2016-09-06

Publication date

2016-09-13

Copyright date

2016

Notes

This paper was accepted for publication in the journal Theoretical Computer Science and the definitive published version is available at http://dx.doi.org/10.1016/j.tcs.2016.09.003.

ISSN

0304-3975

Language

  • en