Deciding stability and mortality of piecewise affine dynamical systems
Identifieur interne : 001A70 ( Istex/Corpus ); précédent : 001A69; suivant : 001A71Deciding stability and mortality of piecewise affine dynamical systems
Auteurs : Vincent D. Blondel ; Olivier Bournez ; Pascal Koiran ; Christos H. Papadimitriou ; John N. TsitsiklisSource :
- Theoretical Computer Science [ 0304-3975 ] ; 2001.
English descriptors
- Teeft :
- Attractivity problem, Blondel, Commutative diagram, Computational power, Continuous functions, Convergent, Decision algorithm, Discrete time, Dynamical, Dynamical state space, Dynamical system, Dynamical systems, Elsevier science, Global convergence, Hybrid, Hybrid systems, Immortal trajectory, Immortality problem, Initial point, Internal state, Internal states, Larger class, Linear systems, Main theorem, Metric space, Mortality problem, Nite number, Open problem, Simulation, Special state, State space, Study problems, Symmetrical argument, Theoretical computer science, Trajectory, Trajectory converges, Turing, Turing machine, Turing machines, Undecidability, Undecidable.
Abstract
Abstract: In this paper we study problems such as: given a discrete time dynamical system of the form x(t+1)=f(x(t)) where f:Rn→Rn is a piecewise affine function, decide whether all trajectories converge to 0. We show in our main theorem that this Attractivity Problem is undecidable as soon as n⩾2. The same is true of two related problems: Stability (is the dynamical system globally asymptotically stable?) and Mortality (do all trajectories go through 0?). We then show that Attractivity and Stability become decidable in dimension 1 for continuous functions.
Url:
DOI: 10.1016/S0304-3975(00)00399-6
Links to Exploration step
ISTEX:7413000D1133CDB096E3520BEE1F700C7AD0FEE0Le document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title>Deciding stability and mortality of piecewise affine dynamical systems</title><author><name sortKey="Blondel, Vincent D" sort="Blondel, Vincent D" uniqKey="Blondel V" first="Vincent D." last="Blondel">Vincent D. Blondel</name><affiliation><mods:affiliation>CESAME, Université Catholique de Louvain, 4 Av. Georges Lemaitre, B-1348 Louvain-la-Neuve, Belgium</mods:affiliation></affiliation><affiliation><mods:affiliation>Corresponding author</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: blondel@inma.ucl.ac.be</mods:affiliation></affiliation></author><author><name sortKey="Bournez, Olivier" sort="Bournez, Olivier" uniqKey="Bournez O" first="Olivier" last="Bournez">Olivier Bournez</name><affiliation><mods:affiliation>LORIA, Campus Scientifique BP 239, F-54506 Vandoeuvre-les-Nancy, France</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: Olivier.Bournez@loria.fr</mods:affiliation></affiliation></author><author><name sortKey="Koiran, Pascal" sort="Koiran, Pascal" uniqKey="Koiran P" first="Pascal" last="Koiran">Pascal Koiran</name><affiliation><mods:affiliation>LIP, ENS Lyon, 46 allée d'Italie, F-69364 Lyon Cedex 07, France</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: pascal.koiran@ens-lyon.fr</mods:affiliation></affiliation></author><author><name sortKey="Papadimitriou, Christos H" sort="Papadimitriou, Christos H" uniqKey="Papadimitriou C" first="Christos H." last="Papadimitriou">Christos H. Papadimitriou</name><affiliation><mods:affiliation>Department of Computer Sciences, University of California, Berkeley, CA 94720, USA</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: christos@cs.berkeley.edu</mods:affiliation></affiliation></author><author><name sortKey="Tsitsiklis, John N" sort="Tsitsiklis, John N" uniqKey="Tsitsiklis J" first="John N." last="Tsitsiklis">John N. Tsitsiklis</name><affiliation><mods:affiliation>LIDS, MIT, Cambridge, MA 02139, USA</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: jnt@mit.edu</mods:affiliation></affiliation></author></titleStmt><publicationStmt><idno type="wicri:source">ISTEX</idno><idno type="RBID">ISTEX:7413000D1133CDB096E3520BEE1F700C7AD0FEE0</idno><date when="2001" year="2001">2001</date><idno type="doi">10.1016/S0304-3975(00)00399-6</idno><idno type="url">https://api.istex.fr/ark:/67375/6H6-X63FWDCP-Q/fulltext.pdf</idno><idno type="wicri:Area/Istex/Corpus">001A70</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">001A70</idno></publicationStmt><sourceDesc><biblStruct><analytic><title level="a">Deciding stability and mortality of piecewise affine dynamical systems</title><author><name sortKey="Blondel, Vincent D" sort="Blondel, Vincent D" uniqKey="Blondel V" first="Vincent D." last="Blondel">Vincent D. Blondel</name><affiliation><mods:affiliation>CESAME, Université Catholique de Louvain, 4 Av. Georges Lemaitre, B-1348 Louvain-la-Neuve, Belgium</mods:affiliation></affiliation><affiliation><mods:affiliation>Corresponding author</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: blondel@inma.ucl.ac.be</mods:affiliation></affiliation></author><author><name sortKey="Bournez, Olivier" sort="Bournez, Olivier" uniqKey="Bournez O" first="Olivier" last="Bournez">Olivier Bournez</name><affiliation><mods:affiliation>LORIA, Campus Scientifique BP 239, F-54506 Vandoeuvre-les-Nancy, France</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: Olivier.Bournez@loria.fr</mods:affiliation></affiliation></author><author><name sortKey="Koiran, Pascal" sort="Koiran, Pascal" uniqKey="Koiran P" first="Pascal" last="Koiran">Pascal Koiran</name><affiliation><mods:affiliation>LIP, ENS Lyon, 46 allée d'Italie, F-69364 Lyon Cedex 07, France</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: pascal.koiran@ens-lyon.fr</mods:affiliation></affiliation></author><author><name sortKey="Papadimitriou, Christos H" sort="Papadimitriou, Christos H" uniqKey="Papadimitriou C" first="Christos H." last="Papadimitriou">Christos H. Papadimitriou</name><affiliation><mods:affiliation>Department of Computer Sciences, University of California, Berkeley, CA 94720, USA</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: christos@cs.berkeley.edu</mods:affiliation></affiliation></author><author><name sortKey="Tsitsiklis, John N" sort="Tsitsiklis, John N" uniqKey="Tsitsiklis J" first="John N." last="Tsitsiklis">John N. Tsitsiklis</name><affiliation><mods:affiliation>LIDS, MIT, Cambridge, MA 02139, USA</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: jnt@mit.edu</mods:affiliation></affiliation></author></analytic><monogr></monogr><series><title level="j">Theoretical Computer Science</title><title level="j" type="abbrev">TCS</title><idno type="ISSN">0304-3975</idno><imprint><publisher>ELSEVIER</publisher><date type="published" when="2001">2001</date><biblScope unit="volume">255</biblScope><biblScope unit="issue">1–2</biblScope><biblScope unit="page" from="687">687</biblScope><biblScope unit="page" to="696">696</biblScope></imprint><idno type="ISSN">0304-3975</idno></series></biblStruct></sourceDesc><seriesStmt><idno type="ISSN">0304-3975</idno></seriesStmt></fileDesc><profileDesc><textClass><keywords scheme="Teeft" xml:lang="en"><term>Attractivity problem</term><term>Blondel</term><term>Commutative diagram</term><term>Computational power</term><term>Continuous functions</term><term>Convergent</term><term>Decision algorithm</term><term>Discrete time</term><term>Dynamical</term><term>Dynamical state space</term><term>Dynamical system</term><term>Dynamical systems</term><term>Elsevier science</term><term>Global convergence</term><term>Hybrid</term><term>Hybrid systems</term><term>Immortal trajectory</term><term>Immortality problem</term><term>Initial point</term><term>Internal state</term><term>Internal states</term><term>Larger class</term><term>Linear systems</term><term>Main theorem</term><term>Metric space</term><term>Mortality problem</term><term>Nite number</term><term>Open problem</term><term>Simulation</term><term>Special state</term><term>State space</term><term>Study problems</term><term>Symmetrical argument</term><term>Theoretical computer science</term><term>Trajectory</term><term>Trajectory converges</term><term>Turing</term><term>Turing machine</term><term>Turing machines</term><term>Undecidability</term><term>Undecidable</term></keywords></textClass><langUsage><language ident="en">en</language></langUsage></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">Abstract: In this paper we study problems such as: given a discrete time dynamical system of the form x(t+1)=f(x(t)) where f:Rn→Rn is a piecewise affine function, decide whether all trajectories converge to 0. We show in our main theorem that this Attractivity Problem is undecidable as soon as n⩾2. The same is true of two related problems: Stability (is the dynamical system globally asymptotically stable?) and Mortality (do all trajectories go through 0?). We then show that Attractivity and Stability become decidable in dimension 1 for continuous functions.</div></front></TEI><istex><corpusName>elsevier</corpusName><keywords><teeft><json:string>blondel</json:string><json:string>undecidable</json:string><json:string>undecidability</json:string><json:string>theoretical computer science</json:string><json:string>dynamical systems</json:string><json:string>turing</json:string><json:string>dynamical</json:string><json:string>convergent</json:string><json:string>dynamical system</json:string><json:string>hybrid systems</json:string><json:string>turing machines</json:string><json:string>internal state</json:string><json:string>initial point</json:string><json:string>hybrid</json:string><json:string>trajectory</json:string><json:string>attractivity problem</json:string><json:string>state space</json:string><json:string>discrete time</json:string><json:string>continuous functions</json:string><json:string>linear systems</json:string><json:string>computational power</json:string><json:string>immortal trajectory</json:string><json:string>global convergence</json:string><json:string>decision algorithm</json:string><json:string>larger class</json:string><json:string>elsevier science</json:string><json:string>trajectory converges</json:string><json:string>mortality problem</json:string><json:string>nite number</json:string><json:string>internal states</json:string><json:string>symmetrical argument</json:string><json:string>study problems</json:string><json:string>immortality problem</json:string><json:string>special state</json:string><json:string>turing machine</json:string><json:string>commutative diagram</json:string><json:string>main theorem</json:string><json:string>open problem</json:string><json:string>metric space</json:string><json:string>dynamical state space</json:string><json:string>simulation</json:string></teeft></keywords><author><json:item><name>Vincent D. Blondel</name><affiliations><json:string>CESAME, Université Catholique de Louvain, 4 Av. Georges Lemaitre, B-1348 Louvain-la-Neuve, Belgium</json:string><json:string>Corresponding author</json:string><json:string>E-mail: blondel@inma.ucl.ac.be</json:string></affiliations></json:item><json:item><name>Olivier Bournez</name><affiliations><json:string>LORIA, Campus Scientifique BP 239, F-54506 Vandoeuvre-les-Nancy, France</json:string><json:string>E-mail: Olivier.Bournez@loria.fr</json:string></affiliations></json:item><json:item><name>Pascal Koiran</name><affiliations><json:string>LIP, ENS Lyon, 46 allée d'Italie, F-69364 Lyon Cedex 07, France</json:string><json:string>E-mail: pascal.koiran@ens-lyon.fr</json:string></affiliations></json:item><json:item><name>Christos H. Papadimitriou</name><affiliations><json:string>Department of Computer Sciences, University of California, Berkeley, CA 94720, USA</json:string><json:string>E-mail: christos@cs.berkeley.edu</json:string></affiliations></json:item><json:item><name>John N. Tsitsiklis</name><affiliations><json:string>LIDS, MIT, Cambridge, MA 02139, USA</json:string><json:string>E-mail: jnt@mit.edu</json:string></affiliations></json:item></author><subject><json:item><lang><json:string>eng</json:string></lang><value>Discrete dynamical systems</value></json:item><json:item><lang><json:string>eng</json:string></lang><value>Piecewise affine systems</value></json:item><json:item><lang><json:string>eng</json:string></lang><value>Piecewise linear systems</value></json:item><json:item><lang><json:string>eng</json:string></lang><value>Hybrid systems</value></json:item><json:item><lang><json:string>eng</json:string></lang><value>Mortality</value></json:item><json:item><lang><json:string>eng</json:string></lang><value>Stability</value></json:item><json:item><lang><json:string>eng</json:string></lang><value>Decidability</value></json:item></subject><arkIstex>ark:/67375/6H6-X63FWDCP-Q</arkIstex><language><json:string>eng</json:string></language><originalGenre><json:string>Short communication</json:string></originalGenre><abstract>Abstract: In this paper we study problems such as: given a discrete time dynamical system of the form x(t+1)=f(x(t)) where f:Rn→Rn is a piecewise affine function, decide whether all trajectories converge to 0. We show in our main theorem that this Attractivity Problem is undecidable as soon as n⩾2. The same is true of two related problems: Stability (is the dynamical system globally asymptotically stable?) and Mortality (do all trajectories go through 0?). We then show that Attractivity and Stability become decidable in dimension 1 for continuous functions.</abstract><qualityIndicators><score>7.654</score><pdfWordCount>4598</pdfWordCount><pdfCharCount>22172</pdfCharCount><pdfVersion>1.2</pdfVersion><pdfPageCount>10</pdfPageCount><pdfPageSize>544 x 742 pts</pdfPageSize><refBibsNative>true</refBibsNative><abstractWordCount>88</abstractWordCount><abstractCharCount>563</abstractCharCount><keywordCount>7</keywordCount></qualityIndicators><title>Deciding stability and mortality of piecewise affine dynamical systems</title><pii><json:string>S0304-3975(00)00399-6</json:string></pii><genre><json:string>brief-communication</json:string></genre><host><title>Theoretical Computer Science</title><language><json:string>unknown</json:string></language><publicationDate>2001</publicationDate><issn><json:string>0304-3975</json:string></issn><pii><json:string>S0304-3975(00)X0153-3</json:string></pii><volume>255</volume><issue>1–2</issue><pages><first>687</first><last>696</last></pages><genre><json:string>journal</json:string></genre></host><namedEntities><unitex><date><json:string>2000</json:string><json:string>2001</json:string><json:string>1998</json:string></date><geogName></geogName><orgName><json:string>NATO under grant CRG-961115</json:string><json:string>ARO under grant DAAL-03-92-G-0115</json:string><json:string>European Commission</json:string></orgName><orgName_funder><json:string>NATO under grant CRG-961115</json:string><json:string>ARO under grant DAAL-03-92-G-0115</json:string><json:string>European Commission</json:string></orgName_funder><orgName_provider></orgName_provider><persName><json:string>V.D. Blondel</json:string><json:string>J.N. Tsitsiklis</json:string><json:string>Olivier Bournezb</json:string><json:string>C.H. Papadimitriou</json:string><json:string>P. Koiran</json:string><json:string>Pascal Koiranc</json:string><json:string>O. Bournez</json:string><json:string>Georges Lema</json:string><json:string>Christos H. Papadimitrioud</json:string></persName><placeName><json:string>Nancy</json:string><json:string>MA</json:string><json:string>France</json:string><json:string>Cambridge</json:string><json:string>Lyon</json:string><json:string>Belgium</json:string></placeName><ref_url></ref_url><ref_bibl><json:string>V.D. Blondel et al.</json:string><json:string>[18]</json:string><json:string>[11]</json:string><json:string>[8]</json:string><json:string>[17]</json:string><json:string>[3]</json:string><json:string>[11,16,12,14,10,6,2]</json:string><json:string>[9]</json:string><json:string>[2]</json:string><json:string>[19,4]</json:string><json:string>[1,5,7,18]</json:string></ref_bibl><bibl></bibl></unitex></namedEntities><ark><json:string>ark:/67375/6H6-X63FWDCP-Q</json:string></ark><categories><wos><json:string>1 - science</json:string><json:string>2 - computer science, theory & methods</json:string></wos><scienceMetrix><json:string>1 - applied sciences</json:string><json:string>2 - information & communication technologies</json:string><json:string>3 - computation theory & mathematics</json:string></scienceMetrix><scopus><json:string>1 - Physical Sciences</json:string><json:string>2 - Computer Science</json:string><json:string>3 - General Computer Science</json:string><json:string>1 - Physical Sciences</json:string><json:string>2 - Mathematics</json:string><json:string>3 - Theoretical Computer Science</json:string></scopus><inist><json:string>1 - sciences appliquees, technologies et medecines</json:string><json:string>2 - sciences exactes et technologie</json:string><json:string>3 - sciences et techniques communes</json:string><json:string>4 - mathematiques</json:string></inist></categories><publicationDate>2001</publicationDate><copyrightDate>2001</copyrightDate><doi><json:string>10.1016/S0304-3975(00)00399-6</json:string></doi><id>7413000D1133CDB096E3520BEE1F700C7AD0FEE0</id><score>1</score><fulltext><json:item><extension>pdf</extension><original>true</original><mimetype>application/pdf</mimetype><uri>https://api.istex.fr/ark:/67375/6H6-X63FWDCP-Q/fulltext.pdf</uri></json:item><json:item><extension>zip</extension><original>false</original><mimetype>application/zip</mimetype><uri>https://api.istex.fr/ark:/67375/6H6-X63FWDCP-Q/bundle.zip</uri></json:item><istex:fulltextTEI uri="https://api.istex.fr/ark:/67375/6H6-X63FWDCP-Q/fulltext.tei"><teiHeader><fileDesc><titleStmt><title level="a">Deciding stability and mortality of piecewise affine dynamical systems</title></titleStmt><publicationStmt><authority>ISTEX</authority><publisher scheme="https://scientific-publisher.data.istex.fr">ELSEVIER</publisher><availability><licence><p>©2001 Elsevier Science B.V.</p></licence><p scheme="https://loaded-corpus.data.istex.fr/ark:/67375/XBH-HKKZVM7B-M">elsevier</p></availability><date>2001</date></publicationStmt><notesStmt><note type="brief-communication" scheme="https://content-type.data.istex.fr/ark:/67375/XTP-S9SX2MFS-0">brief-communication</note><note type="journal" scheme="https://publication-type.data.istex.fr/ark:/67375/JMC-0GLKJH51-B">journal</note><note>This research was partly carried out while Blondel was visiting Tsitsiklis at MIT (Cambridge) and Koiran at ENS (Lyon). This research was supported by the ARO under grant DAAL-03-92-G-0115, by the NATO under grant CRG-961115 and by the European Commission under the TMR (Alapedes) network contract ERBFMRXCT960074.</note><note>Communicated by M. Sintzoff</note><note type="content">Section title: Note</note></notesStmt><sourceDesc><biblStruct type="inbook"><analytic><title level="a">Deciding stability and mortality of piecewise affine dynamical systems</title><author xml:id="author-0000"><persName><forename type="first">Vincent D.</forename><surname>Blondel</surname></persName><email>blondel@inma.ucl.ac.be</email><affiliation>CESAME, Université Catholique de Louvain, 4 Av. Georges Lemaitre, B-1348 Louvain-la-Neuve, Belgium</affiliation><affiliation>Corresponding author</affiliation></author><author xml:id="author-0001"><persName><forename type="first">Olivier</forename><surname>Bournez</surname></persName><email>Olivier.Bournez@loria.fr</email><affiliation>LORIA, Campus Scientifique BP 239, F-54506 Vandoeuvre-les-Nancy, France</affiliation></author><author xml:id="author-0002"><persName><forename type="first">Pascal</forename><surname>Koiran</surname></persName><email>pascal.koiran@ens-lyon.fr</email><affiliation>LIP, ENS Lyon, 46 allée d'Italie, F-69364 Lyon Cedex 07, France</affiliation></author><author xml:id="author-0003"><persName><forename type="first">Christos H.</forename><surname>Papadimitriou</surname></persName><email>christos@cs.berkeley.edu</email><affiliation>Department of Computer Sciences, University of California, Berkeley, CA 94720, USA</affiliation></author><author xml:id="author-0004"><persName><forename type="first">John N.</forename><surname>Tsitsiklis</surname></persName><email>jnt@mit.edu</email><affiliation>LIDS, MIT, Cambridge, MA 02139, USA</affiliation></author><idno type="istex">7413000D1133CDB096E3520BEE1F700C7AD0FEE0</idno><idno type="ark">ark:/67375/6H6-X63FWDCP-Q</idno><idno type="DOI">10.1016/S0304-3975(00)00399-6</idno><idno type="PII">S0304-3975(00)00399-6</idno></analytic><monogr><title level="j">Theoretical Computer Science</title><title level="j" type="abbrev">TCS</title><idno type="pISSN">0304-3975</idno><idno type="PII">S0304-3975(00)X0153-3</idno><imprint><publisher>ELSEVIER</publisher><date type="published" when="2001"></date><biblScope unit="volume">255</biblScope><biblScope unit="issue">1–2</biblScope><biblScope unit="page" from="687">687</biblScope><biblScope unit="page" to="696">696</biblScope></imprint></monogr></biblStruct></sourceDesc></fileDesc><profileDesc><creation><date>2001</date></creation><langUsage><language ident="en">en</language></langUsage><abstract xml:lang="en"><p>Abstract: In this paper we study problems such as: given a discrete time dynamical system of the form x(t+1)=f(x(t)) where f:Rn→Rn is a piecewise affine function, decide whether all trajectories converge to 0. We show in our main theorem that this Attractivity Problem is undecidable as soon as n⩾2. The same is true of two related problems: Stability (is the dynamical system globally asymptotically stable?) and Mortality (do all trajectories go through 0?). We then show that Attractivity and Stability become decidable in dimension 1 for continuous functions.</p></abstract><textClass><keywords scheme="keyword"><list><head>Keywords</head><item><term>Discrete dynamical systems</term></item><item><term>Piecewise affine systems</term></item><item><term>Piecewise linear systems</term></item><item><term>Hybrid systems</term></item><item><term>Mortality</term></item><item><term>Stability</term></item><item><term>Decidability</term></item></list></keywords></textClass></profileDesc><revisionDesc><change when="2000-03-15">Modified</change><change when="2001">Published</change></revisionDesc></teiHeader></istex:fulltextTEI><json:item><extension>txt</extension><original>false</original><mimetype>text/plain</mimetype><uri>https://api.istex.fr/ark:/67375/6H6-X63FWDCP-Q/fulltext.txt</uri></json:item></fulltext><metadata><istex:metadataXml wicri:clean="Elsevier, elements deleted: tail"><istex:xmlDeclaration>version="1.0" encoding="utf-8"</istex:xmlDeclaration><istex:docType PUBLIC="-//ES//DTD journal article DTD version 4.5.2//EN//XML" URI="art452.dtd" name="istex:docType"></istex:docType><istex:document><converted-article version="4.5.2" docsubtype="sco"><item-info><jid>TCS</jid><aid>3855</aid><ce:pii>S0304-3975(00)00399-6</ce:pii><ce:doi>10.1016/S0304-3975(00)00399-6</ce:doi><ce:copyright type="full-transfer" year="2001">Elsevier Science B.V.</ce:copyright></item-info><head><ce:article-footnote><ce:label>☆</ce:label><ce:note-para>This research was partly carried out while Blondel was visiting Tsitsiklis at MIT (Cambridge) and Koiran at ENS (Lyon). This research was supported by the ARO under grant DAAL-03-92-G-0115, by the NATO under grant CRG-961115 and by the European Commission under the TMR (Alapedes) network contract ERBFMRXCT960074.</ce:note-para></ce:article-footnote><ce:dochead><ce:textfn>Note</ce:textfn></ce:dochead><ce:title>Deciding stability and mortality of piecewise affine dynamical systems</ce:title><ce:author-group><ce:author><ce:initials>V.D.</ce:initials><ce:given-name>Vincent D.</ce:given-name><ce:surname>Blondel</ce:surname><ce:cross-ref refid="AFFA"><ce:sup>a</ce:sup></ce:cross-ref><ce:cross-ref refid="COR1">*</ce:cross-ref><ce:e-address>blondel@inma.ucl.ac.be</ce:e-address></ce:author><ce:author><ce:given-name>Olivier</ce:given-name><ce:surname>Bournez</ce:surname><ce:cross-ref refid="AFFB"><ce:sup>b</ce:sup></ce:cross-ref><ce:e-address>Olivier.Bournez@loria.fr</ce:e-address></ce:author><ce:author><ce:given-name>Pascal</ce:given-name><ce:surname>Koiran</ce:surname><ce:cross-ref refid="AFFC"><ce:sup>c</ce:sup></ce:cross-ref><ce:e-address>pascal.koiran@ens-lyon.fr</ce:e-address></ce:author><ce:author><ce:given-name>Christos H.</ce:given-name><ce:surname>Papadimitriou</ce:surname><ce:cross-ref refid="AFFD"><ce:sup>d</ce:sup></ce:cross-ref><ce:e-address>christos@cs.berkeley.edu</ce:e-address></ce:author><ce:author><ce:given-name>John N.</ce:given-name><ce:surname>Tsitsiklis</ce:surname><ce:cross-ref refid="AFFE"><ce:sup>e</ce:sup></ce:cross-ref><ce:e-address>jnt@mit.edu</ce:e-address></ce:author><ce:affiliation id="AFFA"><ce:label>a</ce:label><ce:textfn>CESAME, Université Catholique de Louvain, 4 Av. Georges Lemaitre, B-1348 Louvain-la-Neuve, Belgium</ce:textfn></ce:affiliation><ce:affiliation id="AFFB"><ce:label>b</ce:label><ce:textfn>LORIA, Campus Scientifique BP 239, F-54506 Vandoeuvre-les-Nancy, France</ce:textfn></ce:affiliation><ce:affiliation id="AFFC"><ce:label>c</ce:label><ce:textfn>LIP, ENS Lyon, 46 allée d'Italie, F-69364 Lyon Cedex 07, France</ce:textfn></ce:affiliation><ce:affiliation id="AFFD"><ce:label>d</ce:label><ce:textfn>Department of Computer Sciences, University of California, Berkeley, CA 94720, USA</ce:textfn></ce:affiliation><ce:affiliation id="AFFE"><ce:label>e</ce:label><ce:textfn>LIDS, MIT, Cambridge, MA 02139, USA</ce:textfn></ce:affiliation><ce:correspondence id="COR1"><ce:label>*</ce:label><ce:text>Corresponding author</ce:text></ce:correspondence></ce:author-group><ce:date-received day="15" month="12" year="1998"></ce:date-received><ce:date-revised day="15" month="3" year="2000"></ce:date-revised><ce:date-accepted day="28" month="9" year="2000"></ce:date-accepted><ce:miscellaneous>Communicated by M. Sintzoff</ce:miscellaneous><ce:abstract><ce:section-title>Abstract</ce:section-title><ce:abstract-sec><ce:simple-para>In this paper we study problems such as: given a discrete time dynamical system of the form <math altimg="si1.gif">x(t+1)=f<ce:hsp sp="0.16"></ce:hsp>(x(t))</math> where <math altimg="si2.gif">f<ce:hsp sp="0.16"></ce:hsp>:<ce:hsp sp="0.16"></ce:hsp><of>R</of><sup>n</sup>→<of>R</of><sup>n</sup></math> is a piecewise affine function, decide whether all trajectories converge to 0. We show in our main theorem that this Attractivity Problem is undecidable as soon as <math altimg="si3.gif">n⩾2</math>. The same is true of two related problems: Stability (is the dynamical system globally asymptotically stable?) and Mortality (do all trajectories go through 0?). We then show that Attractivity and Stability become decidable in dimension 1 for <ce:italic>continuous</ce:italic> functions.</ce:simple-para></ce:abstract-sec></ce:abstract><ce:keywords class="keyword"><ce:section-title>Keywords</ce:section-title><ce:keyword><ce:text>Discrete dynamical systems</ce:text></ce:keyword><ce:keyword><ce:text>Piecewise affine systems</ce:text></ce:keyword><ce:keyword><ce:text>Piecewise linear systems</ce:text></ce:keyword><ce:keyword><ce:text>Hybrid systems</ce:text></ce:keyword><ce:keyword><ce:text>Mortality</ce:text></ce:keyword><ce:keyword><ce:text>Stability</ce:text></ce:keyword><ce:keyword><ce:text>Decidability</ce:text></ce:keyword></ce:keywords></head></converted-article></istex:document></istex:metadataXml><mods version="3.6"><titleInfo><title>Deciding stability and mortality of piecewise affine dynamical systems</title></titleInfo><titleInfo type="alternative" contentType="CDATA"><title>Deciding stability and mortality of piecewise affine dynamical systems</title></titleInfo><name type="personal"><namePart type="given">Vincent D.</namePart><namePart type="family">Blondel</namePart><affiliation>CESAME, Université Catholique de Louvain, 4 Av. Georges Lemaitre, B-1348 Louvain-la-Neuve, Belgium</affiliation><affiliation>Corresponding author</affiliation><affiliation>E-mail: blondel@inma.ucl.ac.be</affiliation><role><roleTerm type="text">author</roleTerm></role></name><name type="personal"><namePart type="given">Olivier</namePart><namePart type="family">Bournez</namePart><affiliation>LORIA, Campus Scientifique BP 239, F-54506 Vandoeuvre-les-Nancy, France</affiliation><affiliation>E-mail: Olivier.Bournez@loria.fr</affiliation><role><roleTerm type="text">author</roleTerm></role></name><name type="personal"><namePart type="given">Pascal</namePart><namePart type="family">Koiran</namePart><affiliation>LIP, ENS Lyon, 46 allée d'Italie, F-69364 Lyon Cedex 07, France</affiliation><affiliation>E-mail: pascal.koiran@ens-lyon.fr</affiliation><role><roleTerm type="text">author</roleTerm></role></name><name type="personal"><namePart type="given">Christos H.</namePart><namePart type="family">Papadimitriou</namePart><affiliation>Department of Computer Sciences, University of California, Berkeley, CA 94720, USA</affiliation><affiliation>E-mail: christos@cs.berkeley.edu</affiliation><role><roleTerm type="text">author</roleTerm></role></name><name type="personal"><namePart type="given">John N.</namePart><namePart type="family">Tsitsiklis</namePart><affiliation>LIDS, MIT, Cambridge, MA 02139, USA</affiliation><affiliation>E-mail: jnt@mit.edu</affiliation><role><roleTerm type="text">author</roleTerm></role></name><typeOfResource>text</typeOfResource><genre type="brief-communication" displayLabel="Short communication" authority="ISTEX" authorityURI="https://content-type.data.istex.fr" valueURI="https://content-type.data.istex.fr/ark:/67375/XTP-S9SX2MFS-0">brief-communication</genre><originInfo><publisher>ELSEVIER</publisher><dateIssued encoding="w3cdtf">2001</dateIssued><dateModified encoding="w3cdtf">2000-03-15</dateModified><copyrightDate encoding="w3cdtf">2001</copyrightDate></originInfo><language><languageTerm type="code" authority="iso639-2b">eng</languageTerm><languageTerm type="code" authority="rfc3066">en</languageTerm></language><abstract lang="en">Abstract: In this paper we study problems such as: given a discrete time dynamical system of the form x(t+1)=f(x(t)) where f:Rn→Rn is a piecewise affine function, decide whether all trajectories converge to 0. We show in our main theorem that this Attractivity Problem is undecidable as soon as n⩾2. The same is true of two related problems: Stability (is the dynamical system globally asymptotically stable?) and Mortality (do all trajectories go through 0?). We then show that Attractivity and Stability become decidable in dimension 1 for continuous functions.</abstract><note>This research was partly carried out while Blondel was visiting Tsitsiklis at MIT (Cambridge) and Koiran at ENS (Lyon). This research was supported by the ARO under grant DAAL-03-92-G-0115, by the NATO under grant CRG-961115 and by the European Commission under the TMR (Alapedes) network contract ERBFMRXCT960074.</note><note>Communicated by M. Sintzoff</note><note type="content">Section title: Note</note><subject><genre>Keywords</genre><topic>Discrete dynamical systems</topic><topic>Piecewise affine systems</topic><topic>Piecewise linear systems</topic><topic>Hybrid systems</topic><topic>Mortality</topic><topic>Stability</topic><topic>Decidability</topic></subject><relatedItem type="host"><titleInfo><title>Theoretical Computer Science</title></titleInfo><titleInfo type="abbreviated"><title>TCS</title></titleInfo><genre type="journal" authority="ISTEX" authorityURI="https://publication-type.data.istex.fr" valueURI="https://publication-type.data.istex.fr/ark:/67375/JMC-0GLKJH51-B">journal</genre><originInfo><publisher>ELSEVIER</publisher><dateIssued encoding="w3cdtf">2001</dateIssued></originInfo><identifier type="ISSN">0304-3975</identifier><identifier type="PII">S0304-3975(00)X0153-3</identifier><part><date>2001</date><detail type="volume"><number>255</number><caption>vol.</caption></detail><detail type="issue"><number>1–2</number><caption>no.</caption></detail><extent unit="issue-pages"><start>1</start><end>700</end></extent><extent unit="pages"><start>687</start><end>696</end></extent></part></relatedItem><identifier type="istex">7413000D1133CDB096E3520BEE1F700C7AD0FEE0</identifier><identifier type="ark">ark:/67375/6H6-X63FWDCP-Q</identifier><identifier type="DOI">10.1016/S0304-3975(00)00399-6</identifier><identifier type="PII">S0304-3975(00)00399-6</identifier><accessCondition type="use and reproduction" contentType="copyright">©2001 Elsevier Science B.V.</accessCondition><recordInfo><recordContentSource authority="ISTEX" authorityURI="https://loaded-corpus.data.istex.fr" valueURI="https://loaded-corpus.data.istex.fr/ark:/67375/XBH-HKKZVM7B-M">elsevier</recordContentSource><recordOrigin>Elsevier Science B.V., ©2001</recordOrigin></recordInfo></mods><json:item><extension>json</extension><original>false</original><mimetype>application/json</mimetype><uri>https://api.istex.fr/ark:/67375/6H6-X63FWDCP-Q/record.json</uri></json:item></metadata><serie></serie></istex></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Istex/Corpus
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 001A70 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Istex/Corpus/biblio.hfd -nk 001A70 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Lorraine
|area= InforLorV4
|flux= Istex
|étape= Corpus
|type= RBID
|clé= ISTEX:7413000D1133CDB096E3520BEE1F700C7AD0FEE0
|texte= Deciding stability and mortality of piecewise affine dynamical systems
}}
| This area was generated with Dilib version V0.6.33. |  |