Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I am in my second year in a MSc that doesn't relate too much with TCS though I wish it would. It's basically about control theory, signals and systems and I took classes in advanced systems (robust, nonlinear, optimal, stochastic), advanced signal processing and convex optimization.

I am trying to figure out a good area to tackle for my dissertation paper and I was wondering whether I can somehow relate to some TCS subject.

The only area that I can think of it could relate is optimization, but I don't have anything particular in mind, the whole subject being very interesting.

It would be great if you could share which topic you think belongs to both worlds.

PS: This question might be totally out of the scope of this Q&A site, so I totally agree if you feel like it's worth closing. Thanks!

share|cite|improve this question
So you are basically asking if there are any theoretical computer science approaches to control theory? – András Salamon Oct 13 '10 at 9:36
Yes, it should be plenty of results from TCS that can be applied in control theory and I am interested in which are those. – hyperboreean Oct 13 '10 at 9:39
Thanks Kaveh, I've edited the title to be more suggestive. – hyperboreean Oct 13 '10 at 10:31

Since you mentioned signal processing, you should look at the area of "compressive sensing". Here is an excellent non-technical description of the main ideas involved:

share|cite|improve this answer
Nice subject, thanks – hyperboreean Oct 13 '10 at 16:28

You might want to see if there are any problems in verifying hybrid systems (aka cyberphysical systems) that you want to tackle. The interaction of discrete control with continuous systems is pretty fascinating, and lets you add some logic and model theory to control theory, and it has many useful applications, too (ie, any time a computer interacts with the world!).

Andre Platzer's homepage has a pretty good summary of this area.

share|cite|improve this answer

Another possible connection to explore is the use of coinduction and coalgebraic techniques for reasoning about control theoretic systems. Jan Rutten did some work in this directions some years ago, namely:

  • J.J.M.M. Rutten Coalgebra, concurrency, and control. In: R. Boel and G. Stremersch (eds.), Discrete Event Systems (analysis and control), Proceedings of WODES 2000 (5th Workshop on Discrete Event Systems), Kluwer, 2000, pp. 31--38. (This link to the paper seems to be broken, though).

The coalgebraic tecnology has advanced in the last 10 years, though I don't know whether the connection has been further explored. Edit Jan Komenda (and here) seems to have been following up the connection.

Other possible approaches could involve using process algebra, I/O automata, interface automata, and hybrid variants of these things. The interface automata have a very strong game theoretic feeling which corresponds closely to somethings done in control theory, namely, the distinction between controllable and uncontrollable actions can be though of as actions being played by two different players. I'm not sure whether anything has been done in that area. The connection seems quite obvious.

A final connection that could be worth exploring is between control theory and epistemic logic. The connection can be seen via the games analogy. What does each party know? How can they use that to achieve a suitable outcome in the system being controlled?

share|cite|improve this answer

Robotics (or as it is all too often called these days, "cyberphysical systems") is a good source of problems that require both control theory and algorithms. See Steve Lavalle's Planning Algorithms for a good intro.

share|cite|improve this answer

Social choice seems to be a nice area at the crossroads of many fields: control theory, complexity, etc. Moreover, it is always a surprise (I mean to me) to see that the problems of the guys from the dept of economics are almost the same as the ones we are trying to solve... Believe me, it is worth having a coffee with them (and let them pay, they won't mind ;)).

share|cite|improve this answer

A good area to explore could be the theory of optimal control (i.e., controlling a system while minimizing some given cost function), which was mainly developed by Richard Bellman, together with the dynamic programming paradigm, that is now ubiquitous in computer science.

A very useful application of optimal control is found, e.g., in Markov decision processes: a dynamical system is modeled by a Markov chain which can be altered by using some admissible policies. Costs are given for transitions and/or controls and one is usually interested in finding a policy that minimizes the total/average/discounted cost for a finite/infinite temporal horizon. This can be accomplished, e.g., by formulating a suitable Hamilton-Jacobi-Bellman equation for the system and then solving it by means of dynamic programming (many other methods exist depending on the systems).

Hence a natural application is in stochastic optimization settings in which the dynamical system can be modeled as Markovian. A standard reference for optimal control is:

  • Dimitri P. Bertsekas, Dynamic Programming and Optimal Control, Athena Scientific.
share|cite|improve this answer

How about using optimization algorithms (such as Simulated Annealing or Genetic) to tune the parameters of your choice of control loop algorithm?

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.