Deciding stability and mortality of piecewise affine dynamical systems

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

inria-00100820, version 1

Deciding stability and mortality of piecewise affine dynamical systems

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

Theoretical Computer Science A 255, 1-2 (2001) 687-696

Résumé : We show that several global properties (attractivity, global asymptotic stability and mortality) of discrete time dynamical systems defined by iteration of piecewise-affine maps are undecidable. Such results had been known only for local properties (e.g., point-to-point reachability). These three properties are undecidable in dimension at least two, but turn out to be decidable in one dimension for continuous maps. This gives a partial answer to a question of Sontag on the decidability of the stability of saturated linear dynamical systems.

a – UCL, BELGIQUE
b – INRIA
c – CNRS, ENS-LYON
d – UUCB, USA
e – 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
3 : Droit et changement social (DCS)
CNRS : UMR6028 – Université de Nantes

inria-00100820, version 1
http://hal.inria.fr/inria-00100820
oai:hal.inria.fr:inria-00100820
Contributeur : Publications Loria <>
Soumis le : Mardi 26 Septembre 2006, 14:51:37
Dernière modification le : Jeudi 28 Septembre 2006, 15:22:47

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="article"><head>Articles dans des revues avec comité de lecture</head>
<biblStruct type="article" xml:id="inria-00100820"><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>Christos</forename><surname>Papadimitriou</surname></persName>
<affiliation>
<orgName type="laboratory">DCS</orgName>
<orgName type="team">Droit et changement social</orgName>
<country>FR</country>
<orgName type="institution">CNRS : UMR6028</orgName>
<orgName type="institution">Université de Nantes</orgName>
</affiliation>
</author>
<author><persName><forename>John N.</forename><surname>Tsitsiklis</surname></persName></author>
<title type="main" level="a">Deciding stability and mortality of piecewise affine dynamical systems</title></analytic><monogr><title level="j" type="main">Theoretical Computer Science A</title><imprint><publisher>none</publisher><biblScope type="publicationDate">2001-00-00</biblScope><biblScope type="vol">255</biblScope><biblScope type="issue">1-2</biblScope><biblScope type="pp">687-696</biblScope></imprint></monogr><idno type="HALid">http://hal.inria.fr/inria-00100820</idno></biblStruct>
</listBibl>
</listBibl>