{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,19]],"date-time":"2026-03-19T11:52:11Z","timestamp":1773921131225,"version":"3.50.1"},"reference-count":176,"publisher":"Elsevier BV","issue":"9","license":[{"start":{"date-parts":[[2000,9,1]],"date-time":"2000-09-01T00:00:00Z","timestamp":967766400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Automatica"],"published-print":{"date-parts":[[2000,9]]},"DOI":"10.1016\/s0005-1098(00)00050-9","type":"journal-article","created":{"date-parts":[[2002,7,26]],"date-time":"2002-07-26T02:38:44Z","timestamp":1027651124000},"page":"1249-1274","source":"Crossref","is-referenced-by-count":546,"title":["A survey of computational complexity results in systems and control"],"prefix":"10.1016","volume":"36","author":[{"given":"Vincent D.","family":"Blondel","sequence":"first","affiliation":[]},{"given":"John N.","family":"Tsitsiklis","sequence":"additional","affiliation":[]}],"member":"78","reference":[{"key":"10.1016\/S0005-1098(00)00050-9_BIB1","series-title":"The design and analysis of computer algorithms","author":"Aho","year":"1974"},{"key":"10.1016\/S0005-1098(00)00050-9_BIB2","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1016\/0304-3975(94)00202-T","article-title":"The algorithmic analysis of hybrid systems","volume":"138","author":"Alur","year":"1995","journal-title":"Theoretical Computer Science"},{"key":"10.1016\/S0005-1098(00)00050-9_BIB3","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1109\/TAC.1975.1100846","article-title":"Output feedback stabilization and related problem \u2014 solutions via decision methods","volume":"20","author":"Anderson","year":"1975","journal-title":"IEEE Transactions on Automatic Control"},{"key":"10.1016\/S0005-1098(00)00050-9_BIB4","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1016\/0304-3975(94)00228-B","article-title":"Reachability analysis of dynamical systems having piecewise-constant derivatives","volume":"138","author":"Asarin","year":"1995","journal-title":"Theoretical Computer Science"},{"key":"10.1016\/S0005-1098(00)00050-9_BIB5","series-title":"Synchronization and linearity","author":"Baccelli","year":"1992"},{"key":"10.1016\/S0005-1098(00)00050-9_BIB6","unstructured":"Barabanov, N. E. (1988). Lyapunov indicators of discrete inclusions, parts I, II and III, Avtomatika i Telemekhanika, 2, 40\u201346, 3, 24\u201329 and 5, 17\u201324. Translation in Automatic remote control (1988) part I, 49(3), 152\u2013157, part II, 49(5), 558\u2013565."},{"key":"10.1016\/S0005-1098(00)00050-9_BIB7","unstructured":"Barmish, B. R., Floudas, C. A., Hollot, C. V., & Tempo, R. (1994). A global linear programming solution to some open robustness problems. Proceedings of the American control conference, Seattle, USA (pp. 3871\u20133877)."},{"key":"10.1016\/S0005-1098(00)00050-9_BIB8","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1007\/BF02551236","article-title":"Root locations of an entire polytope of polynomials: It suffices to check the edges","volume":"1","author":"Bartlett","year":"1988","journal-title":"Mathematics of Control, Signals, and Systems"},{"key":"10.1016\/S0005-1098(00)00050-9_BIB9","doi-asserted-by":"crossref","first-page":"1002","DOI":"10.1145\/235809.235813","article-title":"On the combinatorial and algebraic complexity of quantifier elimination","volume":"43","author":"Basu","year":"1996","journal-title":"Journal of the ACM"},{"key":"10.1016\/S0005-1098(00)00050-9_BIB10","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1016\/0024-3795(92)90267-E","article-title":"Bounded semigroups of matrices","volume":"166","author":"Berger","year":"1992","journal-title":"Linear Algebra Applications"},{"key":"10.1016\/S0005-1098(00)00050-9_BIB11","series-title":"Dynamic programming and optimal control","author":"Bertsekas","year":"1995"},{"key":"10.1016\/S0005-1098(00)00050-9_BIB12","series-title":"Introduction to linear optimization","author":"Bertsimas","year":"1997"},{"key":"10.1016\/S0005-1098(00)00050-9_BIB13","first-page":"473","article-title":"A necessary and sufficient condition for the stability of convex combinations of stable polynomials or matrices","volume":"33","author":"Bialas","year":"1985","journal-title":"Bulletin of the Polish Academy of Sciences, Technical Sciences"},{"key":"10.1016\/S0005-1098(00)00050-9_BIB14","unstructured":"Blondel, V. D., Bournez, O., Koiran, P., Papadimitriou, C., & Tsitsiklis, J. N. (1999a). Deciding stability and mortality of piecewise affine dynamical systems. Preprint."},{"key":"10.1016\/S0005-1098(00)00050-9_BIB15","doi-asserted-by":"crossref","unstructured":"Blondel, V. D., Bournez, O., Koiran, P., & Tsitsiklis, J. N. (1999b). The stability of saturated linear dynamical systems is undecidable. Preprint.","DOI":"10.1007\/3-540-46541-3_40"},{"key":"10.1016\/S0005-1098(00)00050-9_BIB16","unstructured":"Blondel, V. D., Gaubert, S., & Tsitsiklis, J. N. (1998). Approximating Lyapunov exponents of matrices in the max-algebra is NP-hard. Preprint."},{"key":"10.1016\/S0005-1098(00)00050-9_BIB17","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1016\/S0947-3580(95)70004-8","article-title":"Survey on the state of systems and control","volume":"1","author":"Blondel","year":"1995","journal-title":"European Journal of Control"},{"key":"10.1016\/S0005-1098(00)00050-9_BIB18","unstructured":"Blondel, V. D., & Portier, N. (1999a). The presence of a zero in an integer linear recurrent sequence is NP-hard to decide. Preprint."},{"key":"10.1016\/S0005-1098(00)00050-9_BIB19","doi-asserted-by":"crossref","first-page":"2118","DOI":"10.1137\/S0363012994272630","article-title":"NP-hardness of some linear control design problems","volume":"35","author":"Blondel","year":"1997","journal-title":"SIAM Journal of Control and Optimization"},{"key":"10.1016\/S0005-1098(00)00050-9_BIB20","doi-asserted-by":"crossref","first-page":"283","DOI":"10.1016\/S0020-0190(97)00123-3","article-title":"When is a pair of matrices mortal?","volume":"63","author":"Blondel","year":"1997","journal-title":"Information Processing Letters"},{"key":"10.1016\/S0005-1098(00)00050-9_BIB21","unstructured":"Blondel, V. D., & Tsitsiklis, J. N. (1998). Overview of complexity and decidability results for three classes of elementary nonlinear systems. In Y. Yamamoto, & S. Hara, Learning, control and hybrid systems (pp. 46\u201358) Heidelberg: Springer."},{"key":"10.1016\/S0005-1098(00)00050-9_BIB22","doi-asserted-by":"crossref","first-page":"479","DOI":"10.1016\/S0005-1098(98)00175-7","article-title":"Complexity of stability and controllability of elementary hybrid systems","volume":"35","author":"Blondel","year":"1999","journal-title":"Automatica"},{"key":"10.1016\/S0005-1098(00)00050-9_BIB23","unstructured":"Blondel, V. D., & Tsitsiklis, J. N. (1999b). Boundedness of finitely generated matrix semigroups is undecidable. Preprint."},{"key":"10.1016\/S0005-1098(00)00050-9_BIB24","doi-asserted-by":"crossref","unstructured":"Blondel, V. D., Sontag, E. D., Vidyasagar, M., & Willems, J. C. (1999c). Open problems in mathematical systems and control theory. London: Springer, http:\/\/www.inma.ucl.ac.be\/\u223cblondel\/openprobs.html.","DOI":"10.1007\/978-1-4471-0807-8"},{"key":"10.1016\/S0005-1098(00)00050-9_BIB25","series-title":"Complexity and real computation","author":"Blum","year":"1998"},{"key":"10.1016\/S0005-1098(00)00050-9_BIB26","doi-asserted-by":"crossref","first-page":"417","DOI":"10.1016\/S0304-3975(96)00086-2","article-title":"On the computational power of dynamical systems and hybrid systems","volume":"168","author":"Bournez","year":"1996","journal-title":"Theoretical Computer Science"},{"key":"10.1016\/S0005-1098(00)00050-9_BIB27","unstructured":"Bournez, O., & Branicky, M. (1998). On matrix mortality in low dimensions. Technical Report 98-01, Verimag, France."},{"key":"10.1016\/S0005-1098(00)00050-9_BIB28","doi-asserted-by":"crossref","unstructured":"Boyd, S., El Ghaoui, L., Feron, E., & Balakrishnan, V. (1994). Linear matrix inequalities in system and control theory. SIAM Studies in Applied Mathematics, vol. 15. Philadelphia, PA: SIAM.","DOI":"10.1137\/1.9781611970777"},{"key":"10.1016\/S0005-1098(00)00050-9_BIB29","doi-asserted-by":"crossref","first-page":"1000","DOI":"10.1109\/9.284879","article-title":"Computational complexity of \u03bc calculation","volume":"39","author":"Braatz","year":"1994","journal-title":"IEEE Transactions on Automatic Control"},{"key":"10.1016\/S0005-1098(00)00050-9_BIB30","unstructured":"Branicky, M.S. (1995a). Studies in hybrid systems: Modeling, analysis, and control. Ph.D. thesis, Center for Intelligent Control Systems, Cambridge, MA: MIT Press."},{"key":"10.1016\/S0005-1098(00)00050-9_BIB31","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1016\/0304-3975(94)00147-B","article-title":"Universal computation and other capabilities of hybrid and continuous dynamical systems","volume":"138","author":"Branicky","year":"1995","journal-title":"Theoretical Computer Science"},{"key":"10.1016\/S0005-1098(00)00050-9_BIB32","doi-asserted-by":"crossref","first-page":"1121","DOI":"10.1109\/TCS.1980.1084749","article-title":"Constructive stability and asymptotic stability of dynamical systems","volume":"27","author":"Brayton","year":"1980","journal-title":"IEEE Transactions on Circuits and Systems"},{"key":"10.1016\/S0005-1098(00)00050-9_BIB33","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1016\/0004-3702(94)90081-7","article-title":"The computational complexity of propositional STRIPS planning","volume":"69","author":"Bylander","year":"1994","journal-title":"Artificial Intelligence"},{"key":"10.1016\/S0005-1098(00)00050-9_BIB34","doi-asserted-by":"crossref","first-page":"466","DOI":"10.1016\/0885-064X(89)90021-6","article-title":"The complexity of dynamic programming","volume":"5","author":"Chow","year":"1989","journal-title":"Journal of Complexity"},{"key":"10.1016\/S0005-1098(00)00050-9_BIB35","doi-asserted-by":"crossref","first-page":"898","DOI":"10.1109\/9.133184","article-title":"An optimal one-way multigrid algorithm for discrete-time stochastic control","volume":"36","author":"Chow","year":"1991","journal-title":"IEEE Transactions on Automatic Control"},{"key":"10.1016\/S0005-1098(00)00050-9_BIB36","series-title":"Computational models of games","author":"Condon","year":"1989"},{"key":"10.1016\/S0005-1098(00)00050-9_BIB37","doi-asserted-by":"crossref","first-page":"203","DOI":"10.1016\/0890-5401(92)90048-K","article-title":"The complexity of stochastic games","volume":"96","author":"Condon","year":"1992","journal-title":"Information and Computation"},{"key":"10.1016\/S0005-1098(00)00050-9_BIB38","doi-asserted-by":"crossref","unstructured":"Cook, S.A. (1971). The complexity of theorem proving procedures. Proceedings of the third ACM symposium on the theory of computing (pp. 117\u2013128).","DOI":"10.1145\/800157.805047"},{"key":"10.1016\/S0005-1098(00)00050-9_BIB39","doi-asserted-by":"crossref","first-page":"279","DOI":"10.1007\/BF01211520","article-title":"The computational complexity of approximating the minimal perturbation scaling to achieve instability in an interval matrix","volume":"7","author":"Coxson","year":"1994","journal-title":"Mathematics of Control, Signals, and Systems"},{"key":"10.1016\/S0005-1098(00)00050-9_BIB40","unstructured":"Coxson, G. E. (1993). Computational complexity of robust stability and regularity in families of linear systems. Ph.D. thesis, Electrical and Computer Engineering Department, University of Wisconsin at Madison."},{"key":"10.1016\/S0005-1098(00)00050-9_BIB41","doi-asserted-by":"crossref","first-page":"381","DOI":"10.1016\/0167-6911(88)90096-5","article-title":"Kharitonov's theorem revisited","volume":"11","author":"Dasgupta","year":"1988","journal-title":"Systems and Control Letters"},{"key":"10.1016\/S0005-1098(00)00050-9_BIB42","doi-asserted-by":"crossref","first-page":"227","DOI":"10.1016\/0024-3795(92)90012-Y","article-title":"Sets of matrices all infinite products of which converge","volume":"162","author":"Daubechies","year":"1992","journal-title":"Linear Algebra Applications"},{"key":"10.1016\/S0005-1098(00)00050-9_BIB43","doi-asserted-by":"crossref","first-page":"233","DOI":"10.2307\/2318447","article-title":"Hilbert's tenth problem is unsolvable","volume":"80","author":"Davis","year":"1973","journal-title":"American Mathematical Monthly"},{"key":"10.1016\/S0005-1098(00)00050-9_BIB44","series-title":"Computability and unsolvability","author":"Davis","year":"1982"},{"key":"10.1016\/S0005-1098(00)00050-9_BIB45","doi-asserted-by":"crossref","first-page":"10","DOI":"10.1137\/0613003","article-title":"The component-wise distance to the nearest singular matrix","volume":"13","author":"Demmel","year":"1992","journal-title":"SIAM Journal of Matrix Analysis and Applications"},{"key":"10.1016\/S0005-1098(00)00050-9_BIB46","first-page":"240","article-title":"Analysis of feedback systems with structured uncertainties","volume":"129","author":"Doyle","year":"1982","journal-title":"IEE Proceedings"},{"key":"10.1016\/S0005-1098(00)00050-9_BIB47","doi-asserted-by":"crossref","unstructured":"Fu, M. (1999). Approximation of complex \u03bc. In V. D. Blondel, E. D. Sontag, M. Vidyasagar, & J. C. Willems, Open problems in mathematical systems and control theory, Problem 22. London: Springer.","DOI":"10.1007\/978-1-4471-0807-8_22"},{"key":"10.1016\/S0005-1098(00)00050-9_BIB48","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1016\/S0167-6911(97)00014-5","article-title":"Computational complexity of a poblem aising in fixed order output feedback design","volume":"30","author":"Fu","year":"1997","journal-title":"Systems and Control Letters"},{"key":"10.1016\/S0005-1098(00)00050-9_BIB49","doi-asserted-by":"crossref","first-page":"173","DOI":"10.1016\/0167-6911(88)90056-4","article-title":"Maximal unidirectional perturbation bounds for stability of polynomials and matrices","volume":"11","author":"Fu","year":"1988","journal-title":"Systems and Control Letters"},{"key":"10.1016\/S0005-1098(00)00050-9_BIB50","unstructured":"Fu, M., & Dasgupta, S. (1998). Computational complexity of real structured singular value in \u2113p setting. Preprint."},{"key":"10.1016\/S0005-1098(00)00050-9_BIB51","doi-asserted-by":"crossref","first-page":"213","DOI":"10.1109\/9.341786","article-title":"Robust stability under a class of nonlinear parametric perturbations","volume":"40","author":"Fu","year":"1995","journal-title":"IEEE Transactions on Automatic Control"},{"key":"10.1016\/S0005-1098(00)00050-9_BIB52","unstructured":"Gantmacher, F.R. (1959). Matrix theory, vol. 2. New York: Chelsea Publishing Company."},{"key":"10.1016\/S0005-1098(00)00050-9_BIB53","series-title":"Computers and intractability: A guide to the theory of NP-completeness","author":"Garey","year":"1979"},{"key":"10.1016\/S0005-1098(00)00050-9_BIB54","series-title":"Models of massive parallelism. Analysis of cellular automata and neural networks","author":"Garzon","year":"1995"},{"key":"10.1016\/S0005-1098(00)00050-9_BIB55","series-title":"Multi-armed bandit allocation indices","author":"Gittins","year":"1989"},{"key":"10.1016\/S0005-1098(00)00050-9_BIB56","doi-asserted-by":"crossref","first-page":"431","DOI":"10.1016\/0167-6911(89)90079-0","article-title":"The complexity of some reachability problems for a system on a finite group","volume":"12","author":"Golaszewski","year":"1989","journal-title":"Systems and Control Letters"},{"key":"10.1016\/S0005-1098(00)00050-9_BIB57","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1016\/0024-3795(94)00082-4","article-title":"Computing the joint spectral radius","volume":"234","author":"Gripenberg","year":"1996","journal-title":"Linear Algebra Applications"},{"key":"10.1016\/S0005-1098(00)00050-9_BIB58","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1016\/0024-3795(95)90006-3","article-title":"Stability of discrete linear inclusions","volume":"231","author":"Gurvits","year":"1995","journal-title":"Linear Algebra Applications"},{"key":"10.1016\/S0005-1098(00)00050-9_BIB59","unstructured":"Gurvits, L. (1996). Stability of linear inclusions \u2014 Part 2. Technical Report TR 96-173, NEC Research."},{"key":"10.1016\/S0005-1098(00)00050-9_BIB60","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1006\/jcss.1998.1581","article-title":"What's decidable about hybrid automata","volume":"57","author":"Henzinger","year":"1998","journal-title":"Journal of Computer and System Science"},{"key":"10.1016\/S0005-1098(00)00050-9_BIB61","doi-asserted-by":"crossref","first-page":"532","DOI":"10.1109\/9.126593","article-title":"The extreme eigenvalues and stability of real symmetric interval matrices","volume":"37","author":"Hertz","year":"1992","journal-title":"IEEE Transactions on Automatic Control"},{"key":"10.1016\/S0005-1098(00)00050-9_BIB62","doi-asserted-by":"crossref","first-page":"219","DOI":"10.2307\/2269811","article-title":"The undecidability of the Turing machine immortality problem","volume":"2","author":"Hooper","year":"1966","journal-title":"The Journal of Symbolic Logic"},{"key":"10.1016\/S0005-1098(00)00050-9_BIB63","series-title":"Formal languages and their relation to automata","author":"Hopcroft","year":"1969"},{"key":"10.1016\/S0005-1098(00)00050-9_BIB64","series-title":"Introduction to automata theory, languages, and computation","author":"Hopcroft","year":"1979"},{"key":"10.1016\/S0005-1098(00)00050-9_BIB65","doi-asserted-by":"crossref","unstructured":"Hyotyniemu, H. (1997). On unsolvability of nonlinear system stability. Proceedings of the fourth European control conference, Brussels, vol. 636 (pp. 1\u20136).","DOI":"10.23919\/ECC.1997.7082482"},{"key":"10.1016\/S0005-1098(00)00050-9_BIB66","doi-asserted-by":"crossref","first-page":"724","DOI":"10.2307\/2319560","article-title":"Recursive undecidability","volume":"81","author":"Jones","year":"1974","journal-title":"American Mathematical Monthly"},{"key":"10.1016\/S0005-1098(00)00050-9_BIB67","doi-asserted-by":"crossref","unstructured":"Karp, R. M. (1972). Reducibility among combinatorial problems. In R. Miller, & J. Thatcher, Complexity of computer computations. New York: Plenum Press (pp. 85\u2013104).","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"10.1016\/S0005-1098(00)00050-9_BIB68","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1016\/0012-365X(78)90078-X","article-title":"A characterization of the minimum cycle mean in a digraph","volume":"23","author":"Karp","year":"1978","journal-title":"Discrete Mathematics"},{"key":"10.1016\/S0005-1098(00)00050-9_BIB69","doi-asserted-by":"crossref","first-page":"9","DOI":"10.1016\/0167-6911(90)90038-V","article-title":"The complexity of deciding controllability","volume":"15","author":"Kawski","year":"1990","journal-title":"Systems and Control Letters"},{"key":"10.1016\/S0005-1098(00)00050-9_BIB70","doi-asserted-by":"crossref","unstructured":"Khargonekar, P. P., & Tikku, A. (1996). Randomized algorithms for robust control analysis have polynomial complexity. Proceedings of the conference on decision and control.","DOI":"10.1109\/CDC.1996.573700"},{"key":"10.1016\/S0005-1098(00)00050-9_BIB71","first-page":"2086","article-title":"Asymptotic stability of an equilibrium position of a family of systems of linear differential equations","volume":"14","author":"Kharitonov","year":"1978","journal-title":"Differentsial'nye Uravneniya"},{"key":"10.1016\/S0005-1098(00)00050-9_BIB72","doi-asserted-by":"crossref","first-page":"48","DOI":"10.1006\/inco.1996.0062","article-title":"The dynamic universality of sigmoidal neural networks","volume":"128","author":"Kilian","year":"1996","journal-title":"Information and Computation"},{"key":"10.1016\/S0005-1098(00)00050-9_BIB73","doi-asserted-by":"crossref","first-page":"223","DOI":"10.1142\/S0218196791000146","article-title":"On the undecidability of the freeness of integer matrix semigroups","volume":"1","author":"Klarner","year":"1991","journal-title":"International Journal of Algebra and Computation"},{"key":"10.1016\/S0005-1098(00)00050-9_BIB74","doi-asserted-by":"crossref","first-page":"473","DOI":"10.1016\/S0304-3975(96)00088-6","article-title":"A family of universal recurrent networks","volume":"168","author":"Koiran","year":"1996","journal-title":"Theoretical Computer Science"},{"key":"10.1016\/S0005-1098(00)00050-9_BIB75","doi-asserted-by":"crossref","first-page":"217","DOI":"10.1016\/S0304-3975(98)00117-0","article-title":"Closed-form analytic maps in 1 or 2 dimension can simulate universal Turing machines","volume":"210","author":"Koiran","year":"1999","journal-title":"Theoretical Computer Science"},{"key":"10.1016\/S0005-1098(00)00050-9_BIB76","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1016\/0304-3975(94)90229-1","article-title":"Computability properties of low-dimensional dynamical systems","volume":"132","author":"Koiran","year":"1994","journal-title":"Theoretical Computer Science"},{"key":"10.1016\/S0005-1098(00)00050-9_BIB77","doi-asserted-by":"crossref","unstructured":"Kokame, H., & Mori, T. (1992). A branch-and-bound method to check the stability of a polytope of matrices. In M. Mansour, S. Balemi & W. Truoel, Robustness of dynamics systems with parameter uncertainties (pp. 125\u2013137). Basel: Birkhauser.","DOI":"10.1007\/978-3-0348-7268-3_13"},{"key":"10.1016\/S0005-1098(00)00050-9_BIB78","first-page":"754","article-title":"Algebraic unsolvability of problem of absolute stability of desynchronized systems","volume":"51","author":"Kozyakin","year":"1990","journal-title":"Automation and Remote Control"},{"key":"10.1016\/S0005-1098(00)00050-9_BIB79","unstructured":"Kreinovich, V., Lakeyev, A., & Rohn, J. (1995). Computational complexity of interval algebraic problems: Some are feasible and some are computationally intractable \u2014 a survey. Scientific computing and validated numerics (Wuppertal, 1995) (pp. 293\u2013306). Mathematical Research, vol. 90. Berlin: Akademie Verlag."},{"key":"10.1016\/S0005-1098(00)00050-9_BIB80","unstructured":"Kreinovich, V., Lakeyev, A., Rohn, J., & Kahl, P. (1997). Computational complexity and feasibility of data processing and interval computation. Applied Optimization Series, vol. 10. Dordrecht: Kluwer Academic."},{"key":"10.1016\/S0005-1098(00)00050-9_BIB81","doi-asserted-by":"crossref","first-page":"335","DOI":"10.1007\/BF01752404","article-title":"An unsolvable problem with products of matrices","volume":"14","author":"Krom","year":"1981","journal-title":"Mathematical Systems Theory"},{"key":"10.1016\/S0005-1098(00)00050-9_BIB82","doi-asserted-by":"crossref","first-page":"437","DOI":"10.1002\/malq.19890350510","article-title":"Recursive solvability of problems with matrices","volume":"35","author":"Krom","year":"1989","journal-title":"Z. Math. Logik Grundlagen Math."},{"key":"10.1016\/S0005-1098(00)00050-9_BIB83","doi-asserted-by":"crossref","unstructured":"Lafferierre, G., Pappas, G. J., & Yovine, S. (1999). A new class of decidable hybrid systems. Lecture Notes in Computer Sciences, vol. 1596. Heidelberg: Spirnger.","DOI":"10.1007\/3-540-48983-5_15"},{"key":"10.1016\/S0005-1098(00)00050-9_BIB84","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1016\/0024-3795(93)00052-2","article-title":"The finiteness conjecture for the generalized spectral radius of a set of matrices","volume":"214","author":"Lagarias","year":"1995","journal-title":"Linear Algebra Applications"},{"key":"10.1016\/S0005-1098(00)00050-9_BIB85","series-title":"From animals to animats 3: Proceedings of the third International Conference on simulation of adaptive behavior","article-title":"Memoryless policies: Theoretical limitations and practical results.","author":"Littman","year":"1994"},{"key":"10.1016\/S0005-1098(00)00050-9_BIB86","unstructured":"Littman, M. L. (1996). Algorithms for sequential decision making. Ph.D. thesis, Department of Computer Science, Brown University."},{"key":"10.1016\/S0005-1098(00)00050-9_BIB87","unstructured":"Littman, M. L. (1997). Probabilistic propositional planning: Representations and complexity. In Proceedings of the 14th national conference on artificial intelligence (pp. 748\u2013754). Cambridge, MA: AAAI Press\/The MIT Press."},{"key":"10.1016\/S0005-1098(00)00050-9_BIB88","unstructured":"Littman, M. L., Dean, T. L., & Kaelbling, L. P. (1995). On the complexity of solving Markov decision problems. Proceedings of the 11th annual conference on uncertainty in artificial intelligence, Montreal, Qu\u00e9bec, Canada (pp. 394\u2013402)."},{"key":"10.1016\/S0005-1098(00)00050-9_BIB89","first-page":"1","article-title":"The computational complexity of probabilistic plan existence and evaluation","volume":"9","author":"Littman","year":"1998","journal-title":"Journal of AI Research"},{"key":"10.1016\/S0005-1098(00)00050-9_BIB90","series-title":"Dynamical systems with saturation nonlinearities: Analysis and design","author":"Liu","year":"1994"},{"key":"10.1016\/S0005-1098(00)00050-9_BIB91","unstructured":"Madani, O., Hanks, S., & Condon, A. (1999). On the undecidability of probabilistic planning and infinite-horizon partially observable Markov decision problems, Proceedings of AAAI99, to appear."},{"key":"10.1016\/S0005-1098(00)00050-9_BIB92","first-page":"279","article-title":"Enumerable sets are diophantine","volume":"191","author":"Matiyasevich","year":"1970","journal-title":"Doklady Akademii Nauk SSSR"},{"key":"10.1016\/S0005-1098(00)00050-9_BIB93","doi-asserted-by":"crossref","unstructured":"Matiyasevich, Y., & S\u00e9nizergues, G. (1996). Decision problem for semi-Thue systems with a few rules. Proceedings of LICS96 (pp. 523\u2013531). Silver Spring, MD: IEEE Computer Society Press.","DOI":"10.1109\/LICS.1996.561469"},{"key":"10.1016\/S0005-1098(00)00050-9_BIB94","doi-asserted-by":"crossref","first-page":"188","DOI":"10.1287\/ijoc.6.2.188","article-title":"On the complexity of the policy improvement algorithm for markov decision processes","volume":"6","author":"Melekopoglou","year":"1994","journal-title":"ORSA Journal on Computing"},{"key":"10.1016\/S0005-1098(00)00050-9_BIB95","first-page":"63","article-title":"The distance between terms of an algebraic recurrence sequence","volume":"349","author":"Mignotte","year":"1984","journal-title":"Journal fur die Reine and Angewandte Mathematik"},{"key":"10.1016\/S0005-1098(00)00050-9_BIB96","doi-asserted-by":"crossref","first-page":"995","DOI":"10.1109\/9.35816","article-title":"An elementary proof of Kharitonov's theorem with extensions","volume":"34","author":"Minnichelli","year":"1989","journal-title":"IEEE Transactions on Automatic Control"},{"key":"10.1016\/S0005-1098(00)00050-9_BIB97","series-title":"Computation. Finite and infinite machines","author":"Minsky","year":"1967"},{"key":"10.1016\/S0005-1098(00)00050-9_BIB98","doi-asserted-by":"crossref","first-page":"2354","DOI":"10.1103\/PhysRevLett.64.2354","article-title":"Unpredictability and undecidability in dynamical systems","volume":"64","author":"Moore","year":"1990","journal-title":"Physical Review Letters"},{"key":"10.1016\/S0005-1098(00)00050-9_BIB99","doi-asserted-by":"crossref","first-page":"199","DOI":"10.1088\/0951-7715\/4\/2\/002","article-title":"Generalized shifts: Undecidability and unpredictability in dynamical systems","volume":"4","author":"Moore","year":"1991","journal-title":"Nonlinearity"},{"key":"10.1016\/S0005-1098(00)00050-9_BIB100","unstructured":"Moore, C. (1998). Finite-dimensional analog computers: Flows, maps, and recurrent neural networks. Proceedings of the first international conference on unconventional models of computation, Auckland, New Zealand."},{"key":"10.1016\/S0005-1098(00)00050-9_BIB101","unstructured":"Mundhenk, M. J., Goldsmith, J., Lusena, C., & Allender, E. (1997). Encyclopedia of complexity results for finite horizon Markov decision process problems. Technical Report 273-97, Computer Science Department, University of Kentucky."},{"key":"10.1016\/S0005-1098(00)00050-9_BIB102","series-title":"Integer and combinatorial optimization","author":"Nemhauser","year":"1988"},{"key":"10.1016\/S0005-1098(00)00050-9_BIB103","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1007\/BF01211741","article-title":"Several NP-Hard problems arising in robust stability analysis","volume":"63","author":"Nemirovskii","year":"1993","journal-title":"Mathematics of Control. Signals, and Systems"},{"key":"10.1016\/S0005-1098(00)00050-9_BIB104","series-title":"Problem complexity and method efficiency in optimization","author":"Nemirovsky","year":"1983"},{"key":"10.1016\/S0005-1098(00)00050-9_BIB105","first-page":"94","article-title":"Computational complexity of neural networks: A survey","volume":"1","author":"Orponen","year":"1994","journal-title":"Nordic Journal of Computing"},{"key":"10.1016\/S0005-1098(00)00050-9_BIB106","series-title":"Computational complexity","author":"Papadimitriou","year":"1994"},{"key":"10.1016\/S0005-1098(00)00050-9_BIB107","doi-asserted-by":"crossref","first-page":"211","DOI":"10.1016\/S0019-9958(82)91034-8","article-title":"On the complexity of designing distributed protocols","volume":"53","author":"Papadimitriou","year":"1982","journal-title":"Information and Control"},{"key":"10.1016\/S0005-1098(00)00050-9_BIB108","doi-asserted-by":"crossref","first-page":"639","DOI":"10.1137\/0324038","article-title":"Intractable problems in control theory","volume":"24","author":"Papadimitriou","year":"1986","journal-title":"SIAM Journal of Control and Optimization"},{"key":"10.1016\/S0005-1098(00)00050-9_BIB109","doi-asserted-by":"crossref","first-page":"441","DOI":"10.1287\/moor.12.3.441","article-title":"The complexity of Markov decision processes","volume":"12","author":"Papadimitriou","year":"1987","journal-title":"Mathematics of Operations Research"},{"key":"10.1016\/S0005-1098(00)00050-9_BIB110","unstructured":"Papadimitriou, C. H., & Tsitsiklis, J. N. (1994). The complexity of optimal queueing network control. Proceedings of the nineth annual conference on struture in complexity theory. Amsterdam, The Netherlands. Full version available from: http:\/\/web.mit.edu\/jnt\/www\/publ.html."},{"key":"10.1016\/S0005-1098(00)00050-9_BIB111","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1002\/sapm1970491105","article-title":"Unsolvability in 3\u00d73 matrices","volume":"49","author":"Paterson","year":"1970","journal-title":"Studies in Applied Mathematics"},{"key":"10.1016\/S0005-1098(00)00050-9_BIB112","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BF01213466","article-title":"Checking robust nonsingularity is NP-hard","volume":"6","author":"Poljak","year":"1993","journal-title":"Mathematics of Control, Signals, and Systems"},{"key":"10.1016\/S0005-1098(00)00050-9_BIB113","unstructured":"Pollack, J. B. (1987). On connectionist models of natural language processing. Ph.D. thesis, Department of Computer Science, University of Illinois, Urbana."},{"key":"10.1016\/S0005-1098(00)00050-9_BIB114","doi-asserted-by":"crossref","first-page":"264","DOI":"10.1090\/S0002-9904-1946-08555-9","article-title":"A variant of a recursively unsolvable problem","volume":"52","author":"Post","year":"1946","journal-title":"Bulletin of the American Mathematical Society"},{"key":"10.1016\/S0005-1098(00)00050-9_BIB115","series-title":"Markov decision processes","author":"Puterman","year":"1994"},{"key":"10.1016\/S0005-1098(00)00050-9_BIB116","unstructured":"Puterman, M. L., & Brumelle, S. L. (1978). The analytic theory of policy iteration. In M.L. Puterman, Dynamic programming and its applications. New York: Academic Press."},{"key":"10.1016\/S0005-1098(00)00050-9_BIB117","first-page":"437","article-title":"Algorithms for stochastic games \u2014 a survey","volume":"35","author":"Raghavan","year":"1991","journal-title":"Zeitschrift f\u00fcr O. R."},{"key":"10.1016\/S0005-1098(00)00050-9_BIB118","doi-asserted-by":"crossref","first-page":"857","DOI":"10.1214\/aoms\/1177704455","article-title":"Team decision problems","volume":"33","author":"Radner","year":"1962","journal-title":"Annals of Mathematical Statistics"},{"key":"10.1016\/S0005-1098(00)00050-9_BIB119","unstructured":"Ramadge, P. J. (1983). Control and supervision of discrete event processes. Ph.D. thesis, Department of Electrical Engineering, University of Toronto."},{"key":"10.1016\/S0005-1098(00)00050-9_BIB120","doi-asserted-by":"crossref","first-page":"206","DOI":"10.1137\/0325013","article-title":"Supervisory control of a class of discrete event processes","volume":"25","author":"Ramadge","year":"1987","journal-title":"SIAM J. Control Optimization"},{"key":"10.1016\/S0005-1098(00)00050-9_BIB121","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1016\/S0304-3975(96)00077-1","article-title":"Small universal Turing machines","volume":"168","author":"Rogozhin","year":"1996","journal-title":"Theoretical Computer Science"},{"key":"10.1016\/S0005-1098(00)00050-9_BIB122","doi-asserted-by":"crossref","first-page":"175","DOI":"10.1137\/S0895479891219216","article-title":"Positive definiteness and stability of interval matrices","volume":"15","author":"Rohn","year":"1994","journal-title":"SIAM Journal on Matrix Analysis and Applications"},{"key":"10.1016\/S0005-1098(00)00050-9_BIB123","first-page":"795","article-title":"Checking positive definiteness or stability of symmetric interval matrices is NP-hard","volume":"35","author":"Rohn","year":"1994","journal-title":"Commentationes Mathematicae Universitatis Carolinae"},{"key":"10.1016\/S0005-1098(00)00050-9_BIB124","doi-asserted-by":"crossref","first-page":"315","DOI":"10.1023\/A:1009987227018","article-title":"Complexity of some linear problems with interval data","volume":"3","author":"Rohn","year":"1997","journal-title":"Reliable Computing"},{"key":"10.1016\/S0005-1098(00)00050-9_BIB125","doi-asserted-by":"crossref","unstructured":"Rosenthal, J., & Wang, X. (1997). Inverse eigenvalue problems for multivariable linear systems. In C. I. Byrnes, B. N. Datta, D. Gilliam, & C. F. Martin, Systems and control in the twenty-first century (pp. 289\u2013311). Basel: Birkhauser.","DOI":"10.1007\/978-1-4612-4120-1_16"},{"key":"10.1016\/S0005-1098(00)00050-9_BIB126","doi-asserted-by":"crossref","first-page":"379","DOI":"10.1016\/S1385-7258(60)50046-1","article-title":"A note on the joint spectral radius","volume":"22","author":"Rota","year":"1960","journal-title":"Nederlandse Koninkl\u00ffke Akademie & van Wetenschappen Indagationes Mathematicae"},{"key":"10.1016\/S0005-1098(00)00050-9_BIB127","doi-asserted-by":"crossref","first-page":"1313","DOI":"10.1109\/9.400469","article-title":"The computational complexity of decentralized discrete-event control problems","volume":"40","author":"Rudie","year":"1995","journal-title":"IEEE Transactions on Automatic Control"},{"key":"10.1016\/S0005-1098(00)00050-9_BIB128","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1051\/ita\/1997310100671","article-title":"Undecidable event detection problems for ODEs of dimension one and two","volume":"31","author":"Ruohonen","year":"1997","journal-title":"RAIRO Information and Theoretical Applications"},{"key":"10.1016\/S0005-1098(00)00050-9_BIB129","unstructured":"Rust, J. (1996). Numerical dynamic programming in economics. In H. Amman, D. Kendrick, & J. Rust, Handbook of computational economics (pp. 619\u2013729). Amsterdam: Elsevier (Chapter 14)."},{"issue":"3","key":"10.1016\/S0005-1098(00)00050-9_BIB130","doi-asserted-by":"crossref","first-page":"487","DOI":"10.2307\/2171751","article-title":"Using randomization to break the curse of dimensionality","volume":"65","author":"Rust","year":"1997","journal-title":"Econometrica"},{"key":"10.1016\/S0005-1098(00)00050-9_BIB131","doi-asserted-by":"crossref","unstructured":"Rust, J. (1997b). A comparison of policy iteration methods for solving continuous-state, infinite-horizon Markovian decision problems using random, quasi-random, and deterministic discretizations. Available from the Economics Working Paper archive: http:\/\/econwpa.wustl.edu\/eprints\/comp\/papers\/9704\/9704001.abs","DOI":"10.2139\/ssrn.37768"},{"key":"10.1016\/S0005-1098(00)00050-9_BIB132","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1049\/ip-d.1982.0054","article-title":"Stability margins of diagonally perturbed multivariable feedback systems","volume":"129","author":"Safonov","year":"1982","journal-title":"Proceedings of IEE-D"},{"key":"10.1016\/S0005-1098(00)00050-9_BIB133","series-title":"Computation and automata","author":"Salomaa","year":"1985"},{"key":"10.1016\/S0005-1098(00)00050-9_BIB134","series-title":"Automata-theoretic aspects of formal power series","author":"Salomaa","year":"1978"},{"key":"10.1016\/S0005-1098(00)00050-9_BIB135","unstructured":"Samake, K. (1996). Suite r\u00e9currentes lin\u00e9aires, probl\u00e8mes d'effectivit\u00e9. Ph.D. thesis, Institut de Recherche Math\u00e9matique Avan\u00e7\u00e9e, Universit\u00e9 Louis Pasteur, Strasbourg, France."},{"key":"10.1016\/S0005-1098(00)00050-9_BIB136","series-title":"Theory of linear and integer programming","author":"Schrijver","year":"1986"},{"key":"10.1016\/S0005-1098(00)00050-9_BIB137","doi-asserted-by":"crossref","first-page":"365","DOI":"10.2307\/1969640","article-title":"A new decision method for elementary algebra","volume":"60","author":"Seidenberg","year":"1954","journal-title":"Annals of Mathematics"},{"key":"10.1016\/S0005-1098(00)00050-9_BIB138","doi-asserted-by":"crossref","first-page":"1095","DOI":"10.1073\/pnas.39.10.1095","article-title":"Stochastic games","volume":"39","author":"Shapley","year":"1953","journal-title":"Proceedings of the National Academy of Sciences"},{"key":"10.1016\/S0005-1098(00)00050-9_BIB139","doi-asserted-by":"crossref","first-page":"315","DOI":"10.1007\/BF02551283","article-title":"An efficient algorithm for checking the robust stability of a polytope of polynomials","volume":"4","author":"Sideris","year":"1991","journal-title":"Mathematics of Control, Signals, and Systems"},{"key":"10.1016\/S0005-1098(00)00050-9_BIB140","series-title":"Neural networks and analog computation. Beyond the Turing limit","author":"Siegelmann","year":"1998"},{"key":"10.1016\/S0005-1098(00)00050-9_BIB141","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1016\/0893-9659(91)90080-F","article-title":"Turing computability with neural nets","volume":"4","author":"Siegelmann","year":"1991","journal-title":"Applied Mathematics Letters"},{"key":"10.1016\/S0005-1098(00)00050-9_BIB142","doi-asserted-by":"crossref","first-page":"331","DOI":"10.1016\/0304-3975(94)90178-3","article-title":"Analog computation via neural networks","volume":"131","author":"Siegelmann","year":"1994","journal-title":"Theoretical Computer Science"},{"key":"10.1016\/S0005-1098(00)00050-9_BIB143","doi-asserted-by":"crossref","first-page":"132","DOI":"10.1006\/jcss.1995.1013","article-title":"On the computational power of neural nets","author":"Siegelmann","year":"1995","journal-title":"Journal of Computer and System Sciences"},{"key":"10.1016\/S0005-1098(00)00050-9_BIB144","doi-asserted-by":"crossref","first-page":"243","DOI":"10.1080\/00207179008934060","article-title":"Necessary and sufficient conditions for stability of symmetric interval matrices","volume":"51","author":"Soh","year":"1990","journal-title":"International Journal of Control"},{"key":"10.1016\/S0005-1098(00)00050-9_BIB145","doi-asserted-by":"crossref","first-page":"346","DOI":"10.1109\/TAC.1981.1102596","article-title":"Nonlinear regulation: the piecewise linear approach","volume":"26","author":"Sontag","year":"1981","journal-title":"IEEE Transactions on Automatic Control"},{"key":"10.1016\/S0005-1098(00)00050-9_BIB146","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1016\/0020-0190(85)90076-6","article-title":"Real addition and the polynomial hierarchy","volume":"20","author":"Sontag","year":"1985","journal-title":"Information Processing Letters"},{"key":"10.1016\/S0005-1098(00)00050-9_BIB147","doi-asserted-by":"crossref","first-page":"1106","DOI":"10.1137\/0326061","article-title":"Controllability is harder to decide than accessibility","volume":"26","author":"Sontag","year":"1988","journal-title":"SIAM Journal of Control and Optimization"},{"key":"10.1016\/S0005-1098(00)00050-9_BIB148","doi-asserted-by":"crossref","unstructured":"Sontag, E. D. (1988b). Some complexity questions regarding controllability. Proceedings IEEE conference on decision and control, San Antonio, TX (pp. 1326\u20131329).","DOI":"10.1109\/CDC.1988.194538"},{"key":"10.1016\/S0005-1098(00)00050-9_BIB149","doi-asserted-by":"crossref","unstructured":"Sontag, E. D. (1995). From linear to nonlinear: Some complexity comparisons. Proceedings of the IEEE conference decision and control, New Orleans (pp. 2916\u20132920).","DOI":"10.1109\/CDC.1995.478585"},{"key":"10.1016\/S0005-1098(00)00050-9_BIB150","doi-asserted-by":"crossref","unstructured":"Sontag, E. D. (1996a). Interconnected automata and linear systems: A theoretical framework in discrete-time. In R. Alur, T. Henzinger, & E. D. Sontag, Hybrid systems III: Verification and control (pp. 436\u2013448). Berlin: Springer.","DOI":"10.1007\/BFb0020966"},{"key":"10.1016\/S0005-1098(00)00050-9_BIB151","unstructured":"Sontag, E. D. (1996b). Recurrent neural networks: Some learning and systems-theoretic aspects. Preprint."},{"key":"10.1016\/S0005-1098(00)00050-9_BIB152","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1016\/S0005-1098(96)00141-0","article-title":"Static output feedback: A survey","volume":"33","author":"Syrmos","year":"1994","journal-title":"Automatica"},{"key":"10.1016\/S0005-1098(00)00050-9_BIB153","series-title":"A decision method for elementary algebra and geometry","author":"Tarski","year":"1951"},{"key":"10.1016\/S0005-1098(00)00050-9_BIB154","doi-asserted-by":"crossref","unstructured":"Tempo, R., Bai, E.W., & Dabbene, F. (1996). Probabilistic robustness analysis: Explicit bounds for the minimum number of sampling points. Proceedings on IEEE conference decision and control (pp. 2412\u20132420).","DOI":"10.1109\/CDC.1996.573690"},{"key":"10.1016\/S0005-1098(00)00050-9_BIB155","doi-asserted-by":"crossref","first-page":"2015","DOI":"10.1016\/S0005-1098(97)00129-5","article-title":"On the complexity of the robust stability problem for linear parameter varying systems","volume":"33","author":"Toker","year":"1997","journal-title":"Automatica"},{"key":"10.1016\/S0005-1098(00)00050-9_BIB156","doi-asserted-by":"crossref","unstructured":"Toker, O. (1996). On the algorithmic unsolvability of some stability problems for discrete event systems. Proceedings of IFAC world congress (pp. 353\u2013358).","DOI":"10.1016\/S1474-6670(17)58436-0"},{"key":"10.1016\/S0005-1098(00)00050-9_BIB157","doi-asserted-by":"crossref","unstructured":"Toker, O., & de Jager, P. (1999). Conservatism of the standard upper bound test. In V. D. Blondel, E. D. Sontag, M. Vidyasagar, & J. C. Willems, Open problems in mathematical systems and control theory, Problem 20. London: Springer.","DOI":"10.1007\/978-1-4471-0807-8_43"},{"key":"10.1016\/S0005-1098(00)00050-9_BIB158","doi-asserted-by":"crossref","first-page":"409","DOI":"10.1109\/9.661609","article-title":"On the complexity of purely complex \u03bc computation and related problems in multidimensional systems","volume":"43","author":"Toker","year":"1998","journal-title":"IEEE Transactions on Automatic Control"},{"key":"10.1016\/S0005-1098(00)00050-9_BIB159","doi-asserted-by":"crossref","first-page":"386","DOI":"10.1007\/BF01211858","article-title":"Complexity issues in robust stability of linear delay-differential systems","volume":"9","author":"Toker","year":"1996","journal-title":"Mathematics of Control, Signals, and Systems"},{"key":"10.1016\/S0005-1098(00)00050-9_BIB160","doi-asserted-by":"crossref","unstructured":"Toker, O., & Ozbay, H. (1995). On the NP-hardness of solving bilinear matrix inequalities and simultaneous stabilization with static output feedback. Proceedings of the IEEE American control conference, Seattle, WA (pp. 2525\u20132526).","DOI":"10.1109\/ACC.1995.532300"},{"key":"10.1016\/S0005-1098(00)00050-9_BIB161","series-title":"Information-based complexity","author":"Traub","year":"1988"},{"key":"10.1016\/S0005-1098(00)00050-9_BIB162","unstructured":"Trei, S. (1999). The gap between complex structured singular value and its upper bound is infinite. Preprint, http:\/\/www.math.msu.edu\/\u223ctreil\/research.html."},{"key":"10.1016\/S0005-1098(00)00050-9_BIB163","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1016\/0167-6377(90)90022-W","article-title":"Solving h-horizon, stationary Markov decision problems in time proportional to logh","volume":"9","author":"Tseng","year":"1990","journal-title":"Operations Research Letters"},{"key":"10.1016\/S0005-1098(00)00050-9_BIB164","unstructured":"Tsitsiklis, J. N. (1984). Problems in decentralized decision making and computation. Ph.D. thesis, Department of Electrical Engineering and Computer Science. Cambridge, MA: MIT Press."},{"key":"10.1016\/S0005-1098(00)00050-9_BIB165","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1007\/BF02551817","article-title":"On the control of discrete-event dynamical systems","volume":"2","author":"Tsitsiklis","year":"1989","journal-title":"Mathematics of Control, Signals, and Systems"},{"key":"10.1016\/S0005-1098(00)00050-9_BIB166","doi-asserted-by":"crossref","first-page":"440","DOI":"10.1109\/TAC.1985.1103988","article-title":"On the complexity of decentralized decision making and detection problems","volume":"30","author":"Tsitsiklis","year":"1985","journal-title":"IEEE Transactions on Automatic Control"},{"key":"10.1016\/S0005-1098(00)00050-9_BIB167","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1007\/BF01219774","article-title":"The Lyapunov exponent and joint spectral radius of pairs of matrices are hard \u2014 when not impossible \u2014 to compute and to approximate","volume":"10","author":"Tsitsiklis","year":"1997","journal-title":"Mathematics of Control Signals, and Systems"},{"key":"10.1016\/S0005-1098(00)00050-9_BIB168","doi-asserted-by":"crossref","first-page":"381","DOI":"10.1007\/BF01211553","article-title":"Lyapunov exponents of pairs of matrices, a correction","volume":"10","author":"Tsitsiklis","year":"1997","journal-title":"Mathematics of Control, Signals, and Systems"},{"key":"10.1016\/S0005-1098(00)00050-9_BIB169","series-title":"A theory of learning and generalization. With applications to neural networks and control systems","author":"Vidyasagar","year":"1998"},{"key":"10.1016\/S0005-1098(00)00050-9_BIB170","unstructured":"Vidyasagar, M., & Blondel, V. D. (1999). Probabilistic solutions to some NP-hard matrix problems. Preprint."},{"key":"10.1016\/S0005-1098(00)00050-9_BIB171","doi-asserted-by":"crossref","first-page":"231","DOI":"10.1287\/moor.3.3.231","article-title":"Approximations of dynamic programs \u2014 I","volume":"3","author":"Whitt","year":"1978","journal-title":"Mathematics of Operations Research"},{"key":"10.1016\/S0005-1098(00)00050-9_BIB172","doi-asserted-by":"crossref","first-page":"179","DOI":"10.1287\/moor.4.2.179","article-title":"Approximations of dynamic programs \u2014 II","volume":"4","author":"Whitt","year":"1978","journal-title":"Mathematics of Operations Research"},{"key":"10.1016\/S0005-1098(00)00050-9_BIB173","doi-asserted-by":"crossref","unstructured":"Whittle, P. (1988). Restless bandits: Activity allocation in a changing world. In J. Gani, A celebration of applied probability, Journal of Applied Probability, 25A, 287\u2013298.","DOI":"10.2307\/3214163"},{"key":"10.1016\/S0005-1098(00)00050-9_BIB174","first-page":"138","article-title":"A counterexample in stochastic optimum control","volume":"6","author":"Witsenhausen","year":"1968","journal-title":"SIAM Journal of Control and Optimization"},{"key":"10.1016\/S0005-1098(00)00050-9_BIB175","series-title":"Robust and optimal control","author":"Zhou","year":"1995"},{"key":"10.1016\/S0005-1098(00)00050-9_BIB176","doi-asserted-by":"crossref","first-page":"343","DOI":"10.1016\/0304-3975(95)00188-3","article-title":"The complexity of mean payoff games on graphs","volume":"158","author":"Zwick","year":"1996","journal-title":"Theoretical Computer Science"}],"container-title":["Automatica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0005109800000509?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0005109800000509?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2020,2,5]],"date-time":"2020-02-05T04:04:17Z","timestamp":1580875457000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0005109800000509"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000,9]]},"references-count":176,"journal-issue":{"issue":"9","published-print":{"date-parts":[[2000,9]]}},"alternative-id":["S0005109800000509"],"URL":"https:\/\/doi.org\/10.1016\/s0005-1098(00)00050-9","relation":{},"ISSN":["0005-1098"],"issn-type":[{"value":"0005-1098","type":"print"}],"subject":[],"published":{"date-parts":[[2000,9]]}}}