{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,14]],"date-time":"2026-01-14T01:31:11Z","timestamp":1768354271024,"version":"3.49.0"},"reference-count":33,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[1997,3,1]],"date-time":"1997-03-01T00:00:00Z","timestamp":857174400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Control Signal Systems"],"published-print":{"date-parts":[[1997,3]]},"DOI":"10.1007\/bf01219774","type":"journal-article","created":{"date-parts":[[2005,2,25]],"date-time":"2005-02-25T16:23:31Z","timestamp":1109348611000},"page":"31-40","source":"Crossref","is-referenced-by-count":212,"title":["The Lyapunov exponent and joint spectral radius of pairs of matrices are hard?when not impossible?to compute and to approximate"],"prefix":"10.1007","volume":"10","author":[{"given":"John N.","family":"Tsitsiklis","sequence":"first","affiliation":[]},{"given":"Vincent D.","family":"Blondel","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"CR1","series-title":"Lecture Notes in Mathematics","volume-title":"Lyapunov Exponents, Proceedings of a Conference Held in Oberwolfach","year":"1991","unstructured":"L. Arnold, H. Crauel, and J.-P. Eckmann (eds.),Lyapunov Exponents, Proceedings of a Conference Held in Oberwolfach, Lecture Notes in Mathematics, vol. 1486, Springer-Verlag, Berlin, 1991."},{"key":"CR2","first-page":"40","volume":"2","author":"N. E. Barabanov","year":"1988","unstructured":"N. E. Barabanov, Lyapunov indicators of discrete inclusions, parts I, II, and III,Automat, i Telemekk,2 (1988), 40?46,3 (1988), 24?29, and5 (1988), 17?24 (Translation inAutomat. Remote Control).","journal-title":"Automat, i Telemekk"},{"key":"CR3","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1016\/0024-3795(92)90267-E","volume":"166","author":"M. Berger","year":"1992","unstructured":"M. Berger and Y. Wang, Bounded semigroup of matrices,Linear Algebra Appl.,166 (1992), 21?27.","journal-title":"Linear Algebra Appl."},{"key":"CR4","unstructured":"V. D. Blondel and J. N. Tsitsiklis, When is a pair of matrices mortal?, Technical report LIDS-P-2314, LIDS, MIT, January 1996. To appear inInformation Processing Letters."},{"key":"CR5","doi-asserted-by":"crossref","unstructured":"V. D. Blondel and J. N. Tsitsiklis, Complexity of stability and controllability of elementary hybrid systems, preprint (1997).","DOI":"10.23919\/ECC.1997.7082569"},{"key":"CR6","series-title":"Lecture Notes in Mathematics, vol. 1486","doi-asserted-by":"crossref","first-page":"112","DOI":"10.1007\/BFb0086662","volume-title":"Lyapunov Exponents","author":"P. Bougerol","year":"1991","unstructured":"P. Bougerol, Filtre de Kalman Bucy et exposants de Lyapounov, inLyapunov Exponents (L. Arnold et al, eds.), Lecture Notes in Mathematics, vol. 1486, Springer-Verlag, Berlin, 1991, pp. 112?122."},{"key":"CR7","volume-title":"SIAM Studies in Applied Mathematics, vol. 15","author":"S. Boyd","year":"1994","unstructured":"S. Boyd, L. El Ghaoui, E. Feron, and V. Balakrishnan,Linear Matrix Inequalities in System and Control Theory, SIAM Studies in Applied Mathematics, vol. 15, SIAM, Philadelphia, PA, 1994."},{"key":"CR8","doi-asserted-by":"crossref","first-page":"1121","DOI":"10.1109\/TCS.1980.1084749","volume":"27","author":"R. Brayton","year":"1980","unstructured":"R. Brayton and C. Tong, Constructive stability and asymptotic stability of dynamical systems,IEEE Trans. Circuits and Systems,27 (1980), 1121?1130.","journal-title":"IEEE Trans. Circuits and Systems"},{"key":"CR9","doi-asserted-by":"crossref","first-page":"69","DOI":"10.1137\/1030002","volume":"30","author":"J. Cohen","year":"1988","unstructured":"J. Cohen, Subadditivity, generalized products of random matrices and operation research,SIAM Rev.,30 (1988), 69?86.","journal-title":"SIAM Rev."},{"key":"CR10","series-title":"Contemporary Mathematics","volume-title":"Random Matrices and Their Applications","year":"1986","unstructured":"J. Cohen, H. Kesten, and M. Newman (eds.),Random Matrices and Their Applications, Contemporary Mathematics, vol. 50, American Mathematical Society, Providence, RI, 1986."},{"key":"CR11","series-title":"Lecture Notes in Mathematics, vol. 1486","doi-asserted-by":"crossref","first-page":"206","DOI":"10.1007\/BFb0086670","volume-title":"Lyapunov Exponents","author":"R. Darling","year":"1991","unstructured":"R. Darling, The Lyapunov exponent for product of infinite-dimensional random matrices, inLyapunov Exponents (L. Arnold et al., eds.), Lecture Notes in Mathematics, vol. 1486, Springer-Verlag, Berlin, 1991, pp. 206?215."},{"key":"CR12","doi-asserted-by":"crossref","first-page":"227","DOI":"10.1016\/0024-3795(92)90012-Y","volume":"162","author":"I. Daubechies","year":"1992","unstructured":"I. Daubechies and J. C. Lagarias, Sets of matrices all infinite products of which converge,Linear Algebra Appl.,162 (1992), 227?263.","journal-title":"Linear Algebra Appl."},{"key":"CR13","doi-asserted-by":"crossref","first-page":"151","DOI":"10.1016\/0024-3795(93)00320-Y","volume":"220","author":"L. Elsner","year":"1995","unstructured":"L. Elsner, The generalized spectral radius theorem: an analytic-geometric proof,Linear Algebra Appl.,220 (1995), 151?159.","journal-title":"Linear Algebra Appl."},{"key":"CR14","volume-title":"Computers and Intractability: A Guide to the Theory of NP-completeness","author":"M. R. Garey","year":"1979","unstructured":"M. R. Garey and D. S. Johnson,Computers and Intractability: A Guide to the Theory of NP-completeness, Freeman, New York, 1979."},{"key":"CR15","unstructured":"R. Gharavi and V. Anantharam, An upper bound for the largest Lyapunov exponent of a Markovian random matrix product of nonnegative matrices, preprint (1995)."},{"key":"CR16","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1016\/0024-3795(94)00082-4","volume":"234","author":"G. Gripenberg","year":"1996","unstructured":"G. Gripenberg, Computing the joint spectral radius,Linear Algebra Appl.,234 (1996), 43?60.","journal-title":"Linear Algebra Appl."},{"key":"CR17","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1016\/0024-3795(95)90006-3","volume":"231","author":"L. Gurvits","year":"1995","unstructured":"L. Gurvits, Stability of discrete linear inclusion,Linear Algebra Appl.,231 (1995), 47?85.","journal-title":"Linear Algebra Appl."},{"key":"CR18","volume-title":"Formal Languages and Their Relation to Automata","author":"J. E. Hopcroft","year":"1969","unstructured":"J. E. Hopcroft and J. D. Ullman,Formal Languages and Their Relation to Automata, Addison-Wesley, Reading, MA, 1969."},{"key":"CR19","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511810817","volume-title":"Matrix Analysis","author":"R. A. Horn","year":"1985","unstructured":"R. A. Horn and C. R. Johnson,Matrix Analysis, Cambridge University Press, Cambridge, 1985."},{"key":"CR20","doi-asserted-by":"crossref","first-page":"883","DOI":"10.1214\/aop\/1176996798","volume":"1","author":"J. Kingman","year":"1976","unstructured":"J. Kingman, Subadditive ergodic theory,Ann. Probab.,1 (1976), 883?909.","journal-title":"Ann. Probab."},{"key":"CR21","first-page":"41","volume":"6","author":"V. S. Kozyakin","year":"1990","unstructured":"V. S. Kozyakin, Algebraic unsolvability of problem of absolute stability of desynchronized systems,Avtomat. i Telemekh.,6 (1990), 41?47 (Translation inAutomat. Remote Control).","journal-title":"Avtomat. i Telemekh."},{"key":"CR22","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1016\/0024-3795(93)00052-2","volume":"214","author":"J. C. Lagarias","year":"1995","unstructured":"J. C. Lagarias and Y. Wang, The finiteness conjecture for the generalized spectral radius of a set of matrices,Linear Algebra Appl.,214 (1995), 17?42.","journal-title":"Linear Algebra Appl."},{"key":"CR23","doi-asserted-by":"crossref","first-page":"3427","DOI":"10.1088\/0305-4470\/27\/10\/019","volume":"27","author":"R. Lima","year":"1994","unstructured":"R. Lima and M. Rahibe, Exact Lyapunov exponent for infinite products of random matrices,J. Phys. A,27 (1994), 3427?3437.","journal-title":"J. Phys. A"},{"key":"CR24","unstructured":"Y. Matiyasevich and G. S\u00e9nizergues, Decision problems for semi-Thue systems with a few rules, preprint (1996)."},{"key":"CR25","first-page":"197","volume":"19","author":"V. I. Oseledec","year":"1968","unstructured":"V. I. Oseledec, A multiplicative ergodic theorem. Lyapunov characteristic numbers for dynamical systems,Trans. Moscow Math. Soc.,19 (1968), 197?231.","journal-title":"Trans. Moscow Math. Soc."},{"key":"CR26","volume-title":"Computational Complexity","author":"C. H. Papadimitriou","year":"1994","unstructured":"C. H. Papadimitriou,Computational Complexity, Addison-Wesley, Reading, MA, 1994."},{"key":"CR27","doi-asserted-by":"crossref","first-page":"441","DOI":"10.1287\/moor.12.3.441","volume":"12","author":"C. H. Papadimitriou","year":"1987","unstructured":"C. H. Papadimitriou and J. N. Tsitsiklis, The complexity of Markov decision processes,Math. Oper. Res.,12 (1987), 441?450.","journal-title":"Math. Oper. Res."},{"key":"CR28","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1002\/sapm1970491105","volume":"49","author":"M. Paterson","year":"1970","unstructured":"M. Paterson, Unsolvability in 3 \u00d7 3 matrices,Stud. Appl. Math.,49 (1970), 105?107.","journal-title":"Stud. Appl. Math."},{"key":"CR29","doi-asserted-by":"crossref","first-page":"531","DOI":"10.1007\/BF01023493","volume":"54","author":"K. Ravishankar","year":"1989","unstructured":"K. Ravishankar, Power law scaling of the top Lyapunov exponent of a product of random matrices,J. Stat. Phys.,54 (1989), 531?537.","journal-title":"J. Stat. Phys."},{"key":"CR30","doi-asserted-by":"crossref","first-page":"199","DOI":"10.1007\/BF00277733","volume":"26","author":"J. Roerdink","year":"1988","unstructured":"J. Roerdink, The biennal life strategy in a random environment,J. Math. Biol.,26 (1988), 199?215.","journal-title":"J. Math. Biol."},{"key":"CR31","doi-asserted-by":"crossref","first-page":"379","DOI":"10.1016\/S1385-7258(60)50046-1","volume":"22","author":"G.-C. Rota","year":"1960","unstructured":"G.-C. Rota and G. Strang, A note on the joint spectral radius,Indag. Math.,22 (1960), 379?381.","journal-title":"Indag. Math."},{"key":"CR32","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1007\/BF01692062","volume":"20","author":"J. N. Tsitsiklis","year":"1987","unstructured":"J. N. Tsitsiklis, On the stability of asynchronous iterative processes,Math. Systems Theory,20 (1987), 137?153.","journal-title":"Math. Systems Theory"},{"key":"CR33","doi-asserted-by":"crossref","unstructured":"J. N. Tsitsiklis and V. D. Blondel, The spectral radius of a pair of matrices is hard to compute,Proceedings of the 35th Conference on Decision and Control, Kobe, December 1996, pp. 3192?3197.","DOI":"10.1109\/CDC.1996.573624"}],"container-title":["Mathematics of Control, Signals, and Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01219774.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01219774\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01219774","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,5]],"date-time":"2020-04-05T23:22:17Z","timestamp":1586128937000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01219774"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1997,3]]},"references-count":33,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1997,3]]}},"alternative-id":["BF01219774"],"URL":"https:\/\/doi.org\/10.1007\/bf01219774","relation":{},"ISSN":["0932-4194","1435-568X"],"issn-type":[{"value":"0932-4194","type":"print"},{"value":"1435-568X","type":"electronic"}],"subject":[],"published":{"date-parts":[[1997,3]]}}}