Complexity of stability and controllability of elementary hybrid systems

被引：147
作者：
Blondel, VD
Tsitsiklis, JN
机构：
[1] Univ Liege, Inst Math B37, B-4000 Liege, Belgium
[2] MIT, Informat & Decis Syst Lab, Cambridge, MA 02139 USA
来源：
AUTOMATICA | 1999年 / 35卷 / 03期
关键词：
hybrid systems; nonlinear systems; control; decidability; computability; computational complexity; NP-hard;
D O I：
10.1016/S0005-1098(98)00175-7
中图分类号：
TP [自动化技术、计算机技术];
学科分类号：
0812 ;
摘要：
In this paper, we consider simple classes of nonlinear systems and prove that basic questions related to their stability and controllability are either undecidable or computationally intractable (NP-hard). As a special case, we consider a class of hybrid systems in which the stale space is partitioned into two halfspaces, and the dynamics in each halfspace correspond to a different linear system. (C) 1999 Elsevier Science Ltd. All rights reserved.
引用
收藏
页码：479 / 489
页数：11
相关论文
共 25 条
[1]  
[Anonymous], 1979, Computers and Intractablity: A Guide to the Theoryof NP-Completeness
[2]   REACHABILITY ANALYSIS OF DYNAMICAL-SYSTEMS HAVING PIECEWISE-CONSTANT DERIVATIVES [J].
ASARIN, E ;
MALER, O ;
PNUELI, A .
THEORETICAL COMPUTER SCIENCE, 1995, 138 (01) :35-65
[3]  
Blondel V. D., 1998, LEARNING CONTROL HYB, P46
[4]   When is a pair of matrices mortal? [J].
Blondel, VD ;
Tsitsiklis, JN .
INFORMATION PROCESSING LETTERS, 1997, 63 (05) :283-286
[5]  
BLONDEL VD, 1999, UNPUB AUTOMATICA
[6]   On the computational power of dynamical systems and hybrid systems [J].
Bournez, O ;
Cosnard, M .
THEORETICAL COMPUTER SCIENCE, 1996, 168 (02) :417-459
[7]   UNIVERSAL COMPUTATION AND OTHER CAPABILITIES OF HYBRID AND CONTINUOUS DYNAMICAL-SYSTEMS [J].
BRANICKY, MS .
THEORETICAL COMPUTER SCIENCE, 1995, 138 (01) :67-100
[8]   SETS OF MATRICES ALL INFINITE PRODUCTS OF WHICH CONVERGE [J].
DAUBECHIES, I ;
LAGARIAS, JC .
LINEAR ALGEBRA AND ITS APPLICATIONS, 1992, 161 :227-263
[9]  
GURVITS L, 1995, LINEAR ALGEBRA APPL, V231, P47, DOI 10.1016/0024-3795(94)00010-7
[10]  
GURVITS L, 1997, UNPUB STABILITY LI 2
123