A survey of computational complexity results in systems and control

DOI10.1016/S0005-1098(00)00050-9zbMath0989.93006OpenAlexW2113789941MaRDI QIDQ5926262

Blondel, Vincent D., John N. Tsitsiklis

Publication date: 5 August 2002

Published in: Automatica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0005-1098(00)00050-9

zbMATH Keywords

computational complexity nonlinear systems discrete-time systems discrete-event systems hybrid systems Markov decision processes neural networks time-varying systems Turing machines tutorial introduction

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Research exposition (monographs, survey articles) pertaining to systems and control theory (93-02)

Related Items

A probabilistic framework for problems with real structured uncertainty in systems and control, Polynomially ambiguous probabilistic automata on restricted languages, On control system design using random samples of contractive block Toeplitz matrices, Retrofit control: localization of controller design and implementation, Observation of nonlinear systems via finite capacity channels: constructive data rate limits, PERIODIC SEQUENCES OF ARBITRAGE: A TALE OF FOUR CURRENCIES, A survey of randomized algorithms for control synthesis and performance verification, Overlap-free words and spectra of matrices, Diffusive Influence Systems, Observability of Boolean networks: a graph-theoretic approach, On finite-horizon \(\ell_2\)-induced norms of discrete-time switched linear systems, Reachability Problems for One-Dimensional Piecewise Affine Maps, Efficient sampling in spectrahedra and volume approximation, Robustness via structuredH_∞/H_∞synthesis, Minimal controllability of conjunctive Boolean networks is NP-complete, Scalable Reinforcement Learning for Multiagent Networked Systems, Some open problems on simultaneous stabilization of linear systems, On the decidability and complexity of problems for restricted hierarchical hybrid systems, Undecidable problems of decentralized observation and control on regular languages, Stability analysis of switched systems using variational principles: An introduction, On the complexity of switching linear regression, Stochastic algorithms for robustness of control performances, Discrete-time distributed Kalman filter design for networks of interconnected systems with linear time-varying dynamics, Efficient optimal design of uncertain discrete time dynamical systems, LMI stability conditions for uncertain rational nonlinear systems, Polynomial root radius optimization with affine constraints, Absolute stability of third-order systems: a numerical algorithm, A mean-variance optimization problem for discounted Markov decision processes, A variable neighborhood search based algorithm for finite-horizon Markov decision processes, Random search for constrained Markov decision processes with multi-policy improvement, Some criteria for spectral finiteness of a finite subset of the real matrix space \(\mathbb R^{d\times d}\), Reachability in Linear Dynamical Systems, NP-hardness of deciding convexity of quartic polynomials and related problems, On the complexity of piecewise affine system identification, Discussion on: ``Switching control for a class of nonlinear systems with an application to post-harvest food storage, Exponential lower bounds on the complexity of a class of dynamic programs for combinatorial optimization problems, Robust static and fixed-order dynamic output feedback control of discrete-time parametric uncertain Luré systems: Sequential SDP relaxation approaches, A constraint sampling approach for multi-stage robust optimization, Root mean square gain of discrete-time switched linear systems under Dwell time constraints, REACHABILITY PROBLEMS IN LOW-DIMENSIONAL ITERATIVE MAPS, Connectivity Properties of the Set of Stabilizing Static Decentralized Controllers, Robust control of uncertain systems: classical results and recent developments, An exact iterative search algorithm for constrained Markov decision processes, Value set iteration for Markov decision processes, Perron vector optimization applied to search engines, Dwell time analysis of deterministic and stochastic switched systems, Computing Omega-Limit Sets in Linear Dynamical Systems, Controllability and stabilizability of a networked control system with periodic communication constraints, Uniformity of Lyapunov exponents for non-invertible matrices, Value set iteration for two-person zero-sum Markov games, On global near optimality of special periodic protocols for fluid polling systems with setups, A numerical technique for the stability analysis of linear switched systems, Reduced vertex set result for interval semidefinite optimization problems, Sufficient LMI conditions for reduced-order multi-objective \(\mathcal H_2/\mathcal H_\infty\) control of LTI systems, Analysis of networked control systems with drops and variable delays, Boundedness of the Domain of Definition is Undecidable for Polynomial ODEs, Reconfigurable control of piecewise affine systems with actuator and sensor faults: stability and tracking, A survey of recursive analysis and Moore's notion of real computation, Efficient algorithms for deciding the type of growth of products of integer matrices, Approximation of the joint spectral radius using sum of squares, Soft variable-structure controls: a survey, Chaotic behavior of discrete-time linear inclusion dynamical systems, Exponential penalty function control of loss networks, Weighted automata on infinite words in the context of attacker-defender games, Uniform stabilization of discrete-time switched and Markovian jump linear systems, Multi-policy improvement in stochastic optimization with forward recursive function criteria, The continuous Skolem-Pisot problem, PSPACE-completeness of modular supervisory control problems, Unnamed Item, On the number of \(\alpha \)-power-free binary words for \(2<\alpha \leq 7/3\), On deciding stability of multiclass queueing networks under buffer priority scheduling policies, Unnamed Item, On the generation of random stable polynomials, Analysis and design of robust controllers using the interval Diophantine equation, Unnamed Item, Monte Carlo and Las Vegas randomized algorithms for systems and control. An introduction, Randomized algorithms for robust controller synthesis using statistical learning theory: a tutorial overview, Positivity and linear matrix inequalities, PENNON: Software for Linear and Nonlinear Matrix Inequalities, Parameter-dependent robust \(H_\infty\) filtering for uncertain discrete-time systems, Reachability problems in low-dimensional nondeterministic polynomial maps over integers, Synthesis of \(H_{\infty}\) PID controllers: A parametric approach., Polynomially Ambiguous Probabilistic Automata on Restricted Languages, Average-Case Completeness in Tag Systems, On the Complexity of Value Iteration, Risk-theoretic optimal design of output-feedback controllers via iterative convex relaxations, Randomized methods of stabilization of the discrete linear systems, Computational bounds on polynomial differential equations, Non-Sturmian sequences of matrices providing the maximum growth rate of matrix products, Design of structured dynamic output-feedback controllers for interconnected systems, On the generalized spectral subradius, The boundedness of all products of a pair of matrices is undecidable, Trajectory-dependent filter design for discrete-time switched linear systems, The stability of the deterministic Skorokhod problem is undecidable, Randomized methods for design of uncertain systems: sample complexity and sequential algorithms, Some applications of randomized algorithms for control system design, A descriptor Takagi-Sugeno approach to nonlinear model reduction, On the undecidability of probabilistic planning and related stochastic optimization problems, Statistical learning methods in linear algebra and control problems: The example of finite-time control of uncertain linear systems, The presence of a zero in an integer linear recurrent sequence is NP-hard to decide, Strategy Complexity of Point Payoff, Mean Payoff and Total Payoff Objectives in Countable MDPs, Probabilistic performance validation of deep learning‐based robust NMPC controllers, Learning stability guarantees for constrained switching linear systems from noisy observations, Near-Optimal Distributed Linear-Quadratic Regulator for Networked Systems, Discrete‐time decentralized linear quadratic control for linear time‐varying systems, Decentralized control and state estimation of linear time‐periodic systems, A Comment on “Using Randomization to Break the Curse of Dimensionality”, The computability of LQR and LQG control, On the decidability of reachability in continuous time linear time-invariant systems, Decentralised output-feedback LQG control with one-step communication delay, New LMI conditions for H_∞/H₂ output feedback control of linear discrete-time systems, A non‐smooth lower bound on ν, An LMI condition for robust stability of polynomial matrix polytopes, Corrigendum/addendum to: Sets of matrices all infinite products of which converge, Deciding stability and mortality of piecewise affine dynamical systems, The stability of saturated linear dynamical systems is undecidable, Randomized algorithms for robust controller synthesis using statistical learning theory, Probabilistic solutions to some NP-hard matrix problems, On a conservative concept for output static stabilizability:analysis, consequences, and related problems, Adaptive control of passifiable linear systems with quantized measurements and bounded disturbances, Discussion on: ``GPC robust design using linear and/or bilinear matrix inequalities, Computing the Growth of the Number of Overlap-Free Words with Spectra of Matrices, Discussion on: ``Why is resorting to fate wise? A critical look at randomized algorithms in systems and control, REACHABILITY PROBLEMS FOR PRODUCTS OF MATRICES IN SEMIRINGS, Integrated design of structural and control systems with a homotopy like iterative method, Decentralised - filtering of networked control systems: a jump system approach, stability of wind turbine switching control

Cites Work