Revisiting the Complexity of Stability of Continuous and Hybrid Systems

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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jul 16, 2014
Accession Number
ADA611548

Entities

People

  • Edmund M. Clarke
  • Sicum Gao
  • Soonho Kong

Organizations

  • Carnegie Mellon University

Tags

Communities of Interest

  • Human Systems

DTIC Thesaurus Topics

  • Arithmetic
  • Automata
  • Coding
  • Computational Science
  • Computations
  • Computer Science
  • Control Theory
  • Differential Equations
  • Hierarchies
  • Hybrid Systems
  • Language
  • Lyapunov Functions
  • Machines
  • Numbers
  • Rational Numbers
  • Real Numbers
  • Time Domain

Fields of Study

  • Computer science
  • Mathematics

Readers

  • Adaptive Control and Estimation with Uncertainty in Dynamic Systems.
  • Mathematical Modeling and Probability Theory.