10
$\begingroup$

Hey All, I'm currently trying to find a solid masters thesis topic pertaining to some branch of automata theory or related to formal languages. I'm trying to generate some good ideas for what an acceptable topic would be, something ambitious but something doable at the same time.

Any suggestions would be very much appreciated!

Improve this question
$\endgroup$
2
  • 3
    $\begingroup$ In general, in questions like this it would be very useful to specify what kind of thesis you are supposed to write: For example, BSc, MSc, PhD, something else? In particular, are you expected to do new research or "just" organise existing knowledge? $\endgroup$
    – Jukka Suomela
    Sep 5, 2010 at 9:53
  • 1
    $\begingroup$ I apologize for not specifying, I've edited it above to show it's for my MSc. As far as I can tell, all theses must contribute new results / research and are not just an organization of existing knowledge. So something up that alley if you have any suggestions. $\endgroup$
    – Vincent Russo
    Sep 5, 2010 at 13:52

5 Answers 5

Reset to default
9
$\begingroup$

While I agree with David Eppstein's response in general (and I upvoted it), the emerging field of automata that define biological processes and other natural computing "things" is a vibrant area. Getting hired later is not something I can speak to, but you might be interested in taking a look at Artificial Biochemistry by Luca Cardelli, or Efficient Turing-universal computation with DNA polymers by Qian et al. The first paper is Cardelli's latest attempt to provide formal methods to biochemical processes; the second, a theoretical DNA implementation of a stack machine.

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ As far as the practicality of hiring merit of my thesis topic, I'm not too concerned. I find these topics to be very interesting and would much rather dedicate my time something I'm passionate about rather than something will get me a fatter pay check. With that said, I do like the biological themed idea. I also am a huge fan of quantum computing, yet am unsure as to what a masters level thesis could really entail on quantum complexity. $\endgroup$
    – Vincent Russo
    Sep 5, 2010 at 4:34
  • $\begingroup$ The problems are also different and harder to the classic 70s work: natural computing problems tend not to be classic string-parsing problems, but generally over acyclic graphs. Look up "graph grammars natural computing". $\endgroup$
    – Charles Stewart
    Sep 5, 2010 at 7:23
  • 1
    $\begingroup$ Indeed an interesting topic. Another branch of the biocomputing (which I've been involved with) outside the DNA strand displacement of molecular-programming.org project has been looking into the "programming" aspect of the biocomputing domain: diku.dk/~neil/blobentcs.pdf . In my biased opinion worth looking into :) $\endgroup$
    – svrist
    Sep 5, 2010 at 15:03
  • 1
    $\begingroup$ @svrist, Thanks very much for posting the link to the Hartmann et al. paper. I'll read it today. It looks like the answer to the question I asked here: cstheory.stackexchange.com/questions/114/… so you just made my day. :-) $\endgroup$
    – Aaron Sterling
    Sep 5, 2010 at 15:56
18
$\begingroup$

I think David Eppstein is too dismissive of the area of automata theory and formal languages. The claim that "getting it published in top-level conferences and convincing someone to hire you once you graduate may be problematic" seems to be what Haldane called Aunt Jobiska’s Theorem: "It’s a fact the whole world knows."

In fact, there are good conferences (such as STACS and ICALP) that routinely publish results in automata theory and formal languages; there are well-attended conferences (such as DLT) that focus on the area; it is a very active area in Germany, France, and Italy; there are great open problems in the area; and I know many students that have had no problem getting jobs.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ That is reassuring, seeing as automata theory and formal languages underly everything conceivably done in the field of computer science it's not too surprising either. As far as the job market is concerned I'm not investing my time in this because I care about making money, I'm doing it because I'm passionate about the subject matter. Thanks for the suggestions. $\endgroup$
    – Vincent Russo
    Sep 5, 2010 at 13:49
  • 1
    $\begingroup$ By the by, are there any good repositories online for these open problems you are mention? I've found a few here and there, but most of them state the most "commercial" theoretical computer science topics. i.e. NP ?= P etc. Thanks again for the help. $\endgroup$
    – Vincent Russo
    Sep 5, 2010 at 14:01
  • 3
    $\begingroup$ @Captainhampton: You might want to try browsing the proceedings of conferences like STACS and ICALP (as mentioned in Jeffrey's answer) to look up the latest work and open problems arising from them. Good thesis topics can often be found using this method. $\endgroup$
    – Ryan Williams
    Sep 5, 2010 at 16:38
10
$\begingroup$

Helping with thesis topic is one of the reasons that we have supervisors for graduate students, so you should consult your supervisor about it.

The general advice that I have heard is that you should pick proceedings of a number of recent reputable conferences in the area you want to work and have a look at the papers in them till you find something interesting and discuss it with your supervisor to see if it is a reasonable thesis topic.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Thanks for the feedback Kaveh. I have been talking back and forth with my advisor, but ultimately the decision is up to me as I'll be the one dedicating the bulk of his time to subject matter. So just curious if anyone here had any good thesis experiences with the subject matter. Possibly something pertaining to quantum complexity but "bite size" enough for a masters thesis level. $\endgroup$
    – Vincent Russo
    Sep 5, 2010 at 15:15
7
$\begingroup$

Another fruitful area not already mentioned here is the connection between automata theory and logic. I guess this research direction is more popular is Europe than North America. Since I don't work on that field, I can't suggest you a specific problem. But you can check out the recent LICS 2010 as well as previous ones for recent works. The lecture notes from a course by Leonid Libkin is a nice place to start.

Improve this answer
$\endgroup$
1
  • 4
    $\begingroup$ As an example, the study of nested word languages that are recognized by visibly pushdown automata has gathered a lot of attention over the last decade. One reason is that this is a good model of many problems related to XML, another is that the model serves to tie together work in several different areas (programming language theory, software verification, concurrency, logic). It seems to be one of those topics that truly cross the A/B divide. cis.upenn.edu/~alur/nw.html $\endgroup$
    – András Salamon
    Sep 30, 2010 at 8:08
6
$\begingroup$

The theoretical study of automata theory and formal languages is kind of moribund (meaning, you can probably still find interesting research problems to work on, but getting it published in top-level conferences and convincing someone to hire you once you graduate may be problematic). However, I believe there is also interesting work being done on applying formal language theory to internet threat/intrusion detection , etc., and this area seems much more hot right now.

See e.g.

Wagner and Dean, Intrusion detection via static analysis, IEEE Symp. Security and Privacy 2001

Wagner and Soto, Mimicry attacks on host-based intrusion detection systems, ACM Conf. Computer and Communications Security 2002

Giffin, Jha, and Miller, Efficient Context-Sensitive Intrusion Detection, NDSS 2004

Feng et al, Formalizing Sensitivity in Static Analysis for Intrusion Detection, IEEE Symposium on Security and Privacy 2004

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ I do agree that the practicality in the job market of automata theory is lacking, yet applications of the theory are quite numerous as you've shown. Thanks for the recommendations. Are there any other applicable automata topics not including security that you may recommend? I really would like to do something with quantum complexity theory, yet believe it may be a bit ambitious for a masters project (perhaps a Ph.d). $\endgroup$
    – Vincent Russo
    Sep 5, 2010 at 4:38
  • 3
    $\begingroup$ Also David, I think you give short shrift to formal methods as used in verification. Especially when involving things like Buchi automata, there are all kinds of interesting questions. They've just moved away from the STOC/FOCS/SODA land. $\endgroup$
    – Suresh Venkat
    Oct 5, 2010 at 4:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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