<p>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."</p>

<p>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.</p>

CC BY-SA 2.5
2010-09-05T13:49:02.667Z
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.
Vincent Russo
CC BY-SA 2.5
2010-09-05T14:01:19.773Z
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.
Vincent Russo
CC BY-SA 2.5
2010-09-05T16:38:35.163Z
@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.
Ryan Williams
CC BY-SA 2.5
2010-09-05T13:12:16.927Z
2010-09-05T13:12:16.927Z
Jeffrey Shallit
<p>Helping with thesis topic is one of the reasons that we have supervisors for graduate students, so you should consult your supervisor about it.</p>

<p>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.</p>

CC BY-SA 2.5
2010-09-05T15:15:41.900Z
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.
Vincent Russo
CC BY-SA 2.5
2010-09-05T03:37:06.450Z
2010-09-05T03:37:06.450Z
Kaveh
<p>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 <a href="http://www.floc-conference.org/LICS-program.html">LICS 2010</a> as well as previous ones for recent works. The <a href="http://www.cs.toronto.edu/~libkin/csc2428/">lecture notes</a> from a course by Leonid Libkin is a nice place to start.</p>

CC BY-SA 2.5
2010-09-30T08:08:58.563Z
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.  http://www.cis.upenn.edu/~alur/nw.html
András Salamon
CC BY-SA 2.5
2010-09-30T02:15:39.957Z
2010-10-05T01:27:10.373Z
2010-10-05T01:27:10.373Z
Dai Le
<p>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.</p>

<p>See e.g.</p>

<p>Wagner and Dean, Intrusion detection via static analysis, IEEE Symp. Security and Privacy 2001</p>

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

<p>Giffin, Jha, and Miller, Efficient Context-Sensitive Intrusion Detection, NDSS 2004</p>

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

CC BY-SA 2.5
2010-09-05T04:38:01.010Z
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).
Vincent Russo
CC BY-SA 2.5
2010-10-05T04:20:43.443Z
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.
Suresh Venkat
CC BY-SA 2.5
2010-09-05T03:44:10.807Z
2010-09-05T03:44:10.807Z
David Eppstein
<p>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 <a href="http://lucacardelli.name/Papers/Artificial%20Biochemistry.pdf">Artificial Biochemistry</a> by Luca Cardelli, or <a href="http://www.dna.caltech.edu/Papers/DNA_stack_machines2010_DNA16.pdf">Efficient Turing-universal computation with DNA polymers</a> 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.</p>

CC BY-SA 2.5
2010-09-05T04:34:08.270Z
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.
Vincent Russo
CC BY-SA 2.5
2010-09-05T07:23:55.223Z
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".
Charles Stewart
CC BY-SA 2.5
2010-09-05T15:03:11.737Z
Indeed an interesting topic. Another branch of the biocomputing (which I've been involved with) outside the DNA strand displacement  of http://molecular-programming.org/ project has been looking into the "programming" aspect of the biocomputing domain: http://www.diku.dk/~neil/blobentcs.pdf . In my biased opinion worth looking into :)
svrist
CC BY-SA 2.5
2010-09-05T15:56:36.283Z
@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: http://cstheory.stackexchange.com/questions/114/is-there-an-official-name-for-a-notion-of-reusably-universal so you just made my day. :-)
Aaron Sterling
CC BY-SA 2.5
2010-09-05T04:19:58.127Z
2010-09-05T04:19:58.127Z
Aaron Sterling
<p>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. </p>

<p>Any suggestions would be very much appreciated!</p>

CC BY-SA 2.5
2010-09-05T09:53:22.863Z
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?
Jukka Suomela
CC BY-SA 2.5
2010-09-05T13:52:14.773Z
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.
Vincent Russo
<ds.algorithms><automata-theory><fl.formal-languages><soft-question>
Automata Theory / Formal Language Thesis Topic
Vincent Russo
# Automata Theory / Formal Language Thesis Topic

(Asked by: username_0 on 2010-09-05)

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!

**Tags:** ds.algorithms, automata-theory, fl.formal-languages, soft-question
> **Comments:**
> **username_1**: 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?  
> **username_0**: 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.  

---

## 5 answers

### Answer by username_9 on 2010-09-05. Score: 9 | Accepted answer

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](http://lucacardelli.name/Papers/Artificial%20Biochemistry.pdf) by Luca Cardelli, or [Efficient Turing-universal computation with DNA polymers](http://www.dna.caltech.edu/Papers/DNA_stack_machines2010_DNA16.pdf) 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.

> **Comments:**
> **username_0**: 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.  
> **username_10**: 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".  
> **username_11**: Indeed an interesting topic. Another branch of the biocomputing (which I've been involved with) outside the DNA strand displacement  of http://molecular-programming.org/ project has been looking into the "programming" aspect of the biocomputing domain: http://www.diku.dk/~neil/blobentcs.pdf . In my biased opinion worth looking into :)  
> **username_9**: @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: http://cstheory.stackexchange.com/questions/114/is-there-an-official-name-for-a-notion-of-reusably-universal so you just made my day. :-)  

---

### Answer by username_2 on 2010-09-05. Score: 18

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.

> **Comments:**
> **username_0**: 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.  
> **username_0**: 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.  
> **username_3**: @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.  

---

### Answer by username_4 on 2010-09-05. Score: 10

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.

> **Comments:**
> **username_0**: 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.  

---

### Answer by username_5 on 2010-09-30. Score: 7

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](http://www.floc-conference.org/LICS-program.html) as well as previous ones for recent works. The [lecture notes](http://www.cs.toronto.edu/~libkin/csc2428/) from a course by Leonid Libkin is a nice place to start.

> **Comments:**
> **username_6**: 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.  http://www.cis.upenn.edu/~alur/nw.html  

---

### Answer by username_7 on 2010-09-05. Score: 6

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

> **Comments:**
> **username_0**: 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).  
> **username_8**: 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.  

---

