Accession Number:

ADA611548

Title:

Revisiting the Complexity of Stability of Continuous and Hybrid Systems

Descriptive Note:

Corporate Author:

CARNEGIE-MELLON UNIV PITTSBURGH PA SCHOOL OF COMPUTER SCIENCE

Report Date:

2014-07-16

Pagination or Media Count:

19.0

Abstract:

We develop a general framework for obtaining upper bounds on the practical computational complexity of stability problems, for a wide range of nonlinear continuous and hybrid systems. To do so, we describe stability properties of dynamical systems in first-order theories over the real numbers, and reduce stability problems to the d-decision problems of their descriptions. The framework allows us to give a precise characterization of the complexity of different notions of stability for nonlinear continuous and hybrid systems. We prove that bounded versions of the d-stability problems are generally decidable, and give upper bounds on their complexity. The unbounded versions are generally undecidable, for which we measure their degrees of unsolvability.

Subject Categories:

  • Operations Research

Distribution Statement:

APPROVED FOR PUBLIC RELEASE