## [Computational Complexity] What is in MY automata theory course/What should be

Expand Messages
• In the last post I pondered what was more important: Automata Theory or Crypto. This raises the question of what should be in a course in automata theory.
Message 1 of 1 , Feb 23, 2010
In the last post I pondered what was more important: Automata Theory or Crypto. This raises the question of what should be in a course in automata theory. Rather than discuss that I will tell you what is in mine and see what you think.

The standard topics are:
1. Regular Languages: DFA's, NFA's, Reg Expressions.
2. PDA's, CFL's.
3. Turing Machines, computable and c.e. sets.
4. NPC
The following make this course a bit different than others, though not much. All the thing listed below that I claim I WON"T do are definite- I WON"T do them. All the things that I claim I WILL do are less definite I can't do all of them. I'll see how it goes and which ones I will do.
1. Decidability of Weak Second Order with S and ≤. The language has quantifiers that range over finite sets, quantifiers that range over natural numbers, and symbols for Successor and ≤. The proof uses Reg Languages. We do it in the Reg Language section and then revisit it when we do decidability. At that point I will also tell them (but not prove) about some theories that are undecidable. We also do decidability of Presburger arithmetic (quantify over naturals, have + and ≤) which follows from decidability of WS1S easily. Will also talk about decidability of S1S and omega-automta, but not prove anything. This did not take up too much time because I presented alot of it as more examples of regular languages. This material is not in any textbook that I know of, however see pages 8-28 of this PhD thesis.
2. I am NOT going to do the algorithm for MINIMIZING a DFA.
3. I am NOT going to do Context-Sensitive Languages.
4. I am NOT going to have them prove things that are obvious, like that S-->aSb, S-->emptystring generates {anbn}. Generally I am against having students prove things that are obvious.
5. I am NOT going to have them ever program a Turing Machine. I will tell them they can do everything and rarely refer to them ever again. I DO need the definition so that I can prove Cook's theorem.
6. I am NOT going to to Primitive Recursive functions.
7. In the NPC section I WILL DO the protocol for, in our language, NGI (non-Graph-Isom) is in AM.
8. In the NPC section I WILL DO the protocol for, in our language, given bit-commit, 3-COL is in ZK. (I may to other ZK protocols as well.)
9. In the NPC section will do that Vertex Cover with FIXED k is in O(n2) (I know that better is known.) Why? Because this is a very good example of an obvious thing (can't do better than roughly O(nk)) being WRONG. Shows the NEED to prove things.
10. Might do NSPACE(n) closed under Complementation. Might not- this may be conventionally difficult for this audience. And we really wont' be talking about space anyway.
11. Let SUBSEQ(L) be the set of a subsequence of L. I will, throughout the year, do the following: Show that if L is regular than SUBSEQ(L) is regular, Show that if L is context free than SUBSEQ(L) is context free, Show that if L is c.e. than SUBSEQ(L) is c.e. All of this leads to material I discussed in this old post. I WILL NOT prove that if L is ANY language then SUBSEQ(L) is regular, but I may talk about it.

--
Posted By GASARCH to Computational Complexity at 2/23/2010 08:46:00 AM
Your message has been successfully submitted and would be delivered to recipients shortly.