The stability of saturated linear dynamical systems is undecidable

Vincent D. Blondel; Olivier Bournez; Pascal Koiran; John N. Tsitsiklis

inria-00099336, version 1

The stability of saturated linear dynamical systems is undecidable

Vincent D. Blondel^a, Olivier Bournez ()^b^, 1, Pascal Koiran^c^, 2, John N. Tsitsiklis^d

17th International Symposium on Theoretical Aspects of Computer Science - STACS'2000 1770 (2000) 479-490

Résumé : We prove that several global properties (global convergence, global asymptotic stability, mortality, and nilpotence) of particular classes of discrete time dynamical systems are undecidable. Such results had been known only for point-to-point properties. We prove these properties undecidable for saturated linear dynamical systems, and for continuous piecewise affine dynamical systems in dimension three. We also describe some consequences of our results on the possible dynamics of such systems.

a – UCL (BELGIQUE)
b – INRIA
c – CNRS, ENS-LYON
d – MIT, USA
1 : PROTHEO (INRIA Lorraine - LORIA)
INRIA – CNRS : UMR7503 – Université Henri Poincaré - Nancy I – Université Nancy II – Institut National Polytechnique de Lorraine (INPL)
2 : Laboratoire d'Imagerie Paramétrique (LIP)
CNRS : UMR7623 – IFR58 – Université Pierre et Marie Curie [UPMC] - Paris VI

inria-00099336, version 1
http://hal.inria.fr/inria-00099336
oai:hal.inria.fr:inria-00099336
Contributeur : Publications Loria <>
Soumis le : Mardi 26 Septembre 2006, 08:53:04
Dernière modification le : Jeudi 28 Septembre 2006, 15:22:46

Voir la fiche détaillée

Exporter

Bibtex EndNote TEI RefWorks

<?xml version="1.0" encoding="UTF-8"?>
<listBibl xmlns="http://www.tei-c.org/ns/1.0" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:mml="http://www.w3.org/1998/Math/MathML">
<listBibl type="inproceedings"><head>Communications avec actes</head>
<biblStruct type="inproceedings" xml:id="inria-00099336"><analytic>
<author><persName><forename>Vincent D.</forename><surname>Blondel</surname></persName></author>
<author><persName><forename>Olivier</forename><surname>Bournez</surname></persName>
<affiliation>
<orgName type="laboratory">INRIA Lorraine - LORIA</orgName>
<orgName type="team">PROTHEO</orgName>
<country>FR</country>
<orgName type="institution">INRIA</orgName>
<orgName type="institution">CNRS : UMR7503</orgName>
<orgName type="institution">Université Henri Poincaré - Nancy I</orgName>
<orgName type="institution">Université Nancy II</orgName>
<orgName type="institution">Institut National Polytechnique de Lorraine (INPL)</orgName>
</affiliation>
</author>
<author><persName><forename>Pascal</forename><surname>Koiran</surname></persName>
<affiliation>
<orgName type="laboratory">LIP</orgName>
<orgName type="team">Laboratoire d'Imagerie Paramétrique</orgName>
<country>FR</country>
<orgName type="institution">CNRS : UMR7623</orgName>
<orgName type="institution">IFR58</orgName>
<orgName type="institution">Université Pierre et Marie Curie [UPMC] - Paris VI</orgName>
</affiliation>
</author>
<author><persName><forename>John N.</forename><surname>Tsitsiklis</surname></persName></author>
<title type="main" level="a">The stability of saturated linear dynamical systems is undecidable</title></analytic><monogr><meeting>17th International Symposium on Theoretical Aspects of Computer Science - STACS'2000</meeting><imprint><publisher>Springer-Verlag</publisher><pubPlace><settlement>Lille</settlement><country> France</country></pubPlace><biblScope type="publicationDate">2000-00-00</biblScope><biblScope type="vol">1770</biblScope><biblScope type="pp">479-490</biblScope></imprint></monogr><idno type="HALid">http://hal.inria.fr/inria-00099336</idno></biblStruct>
</listBibl>
</listBibl>