Facial reconstruction

Search LJMU Research Online

Browse Repository | Browse E-Theses

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

Bell, PC, Chen, S and Jackson, L (2016) On the decidability and complexity of problems for restricted hierarchical hybrid systems. Theoretical Computer Science, 652. pp. 47-63. ISSN 0304-3975

[img]
Preview
Text
On the decidability and complexity of problems for restricted hierarchical hybrid systems.pdf - Accepted Version
Available under License Creative Commons Attribution Non-commercial No Derivatives.

Download (579kB) | Preview

Abstract

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.

Item Type: Article
Uncontrolled Keywords: 08 Information And Computing Sciences, 01 Mathematical Sciences
Subjects: Q Science > QA Mathematics > QA75 Electronic computers. Computer science
Divisions: Computer Science
Publisher: Elsevier
Related URLs:
Date Deposited: 27 Sep 2018 11:17
Last Modified: 28 Sep 2018 12:11
DOI or Identification number: 10.1016/j.tcs.2016.09.003
URI: http://researchonline.ljmu.ac.uk/id/eprint/9331

Actions (login required)

View Item View Item