Wednesday, May 19, 2010

What should be in an automata course: Two views based on recent experience

(Joint Post with Subrahmanyam Kalyanasundaram)

In this post, I speculated on what I might put into my automata theory course. That prompted Subrahmanyam Kalyanasundaram, a PhD student at Georgia Tech, who was teaching Automata theory this spring, to begin a private correspondence with me. Now that both of our courses are over we can tell you what happened.
  1. BILL: I did do Decidability of WS1S (weak second order with Successor and less-than). This was a real win-win-win. (1) It was a nice application of Automata Theory. (2) When I spoke about P and NP and they wanted a natural problem that is KNOWN to not be in NP, Dec of WS1S had already been discussed so I could refer to it and they thought it was natural (I would agree). (3) When I spoke about computability theory and they wanted a natural problem that was not computable I could talk about Hilbert's tenth problem. Since they already had the notion of a fragment of math being decidable or not. Will definitely do this again. Another pro - you can ask real questions about it.
    SUBRUK: I didn't do this.
  2. BILL: Non-Graph-Isom is in AM. I had to do it informally and not prove anything about it. That's fine. I did not do enough of it to be able to ask questions about it. That is a problem with the material. It did give them a plausible intermediary problem (in NP, likely not in P, likely not NPC). Will do it again, it's short, but will think harder about asking them questions about it.
    SUBRUK: I thought about doing this but ended up doing Communication Complexity instead. But I might do this in the future. I only had a few lectures at the end for non traditional topics.
  3. BILL and SUBRUK: Neither of us did Ladner's theorem or the time-hierarchy theorem.
    BILL's REASON: These yield unnatural sets and hence are not of that much interest. Or to put it another way: if a student says ''is there a problem that is decidable but not in NP'' they would much rather see WS1S than a construction of an artificial set. And I agree with them.
  4. BILL and SUBRUK: Neither of us did primitive recursive. There is no real punch-line there. And we won't in the future.
  5. BILL: I didn't do proofs of obvious things. And I won't in the future. I did constructions (e.g., Reg Exp == DFA == NDFA) but did not prove that they work since they obviously work.
    SUBRUK: I did some stuff with TM equivalence that is kind-of obvious which I will skip next time I do the course. Similarly, I may follow BILL's approach on things like Reg Exp == DFA == NDFA in the future.
  6. BILL: Didn't do ZK protocol for SAT. That I would have liked to do and may do in the future; however, we lost two days to snow so that made the semester more time compressed. This I think I COULD make up questions on.
  7. BILL and SUBRUK: We didn't do Mahaney's theorem (if there is a sparse NPC set then P=NP). The PRO of this would have been that there are LOTS I could ask about it. The CON is that there is no punchline for them. I don't really want to go into the Berman-Hartmanis conjecture. BILL personally likes this material (see here) but that is not a good reason to tell them about it. SUBRUK didn't want to start anything that heavy in the few days he had for non-traditional topics.
  8. BILL and SUBRUK: Neither of us did Det PDA's.
  9. BILL and SUBRUK: Both of us did the poly time algorithm for CFGs. This is nice since it fits CFGs in between REG and P.
  10. SUBRUK did a little bit of Communication Complexity Lower Bounds. It was nice and he says that the students liked it. It did not even occur to BILL to do this, but he may consider it in the future.
  11. SUBRUK pondered doing the poly hierarchy but didn't. When he was talking about Sigma-2-P he found that it was hard to keep students interested, and so decided to not cover PH. BILL speculates that this may be true since there are no natural problems there.
  12. SUBRUK did space complexity, NL-completeness, NL = co-NL, Savitch's theorem, PSPACE-completeness. BILL didn't do any of this but is intrigued by the notion of doing it and may consider it in the future.
  13. BILL's Future: SUBRUK has given me some things to think about doing which I had not thought of before. I may move some in or out in the future. If I teach this course many years in a row I will need to vary it some for my own sanity. (Some would say it's too late to worry about that.)
  14. SUBRUK's Future: As noted above, less details on things that are obvious. I would use the extra time to do more interesting non-traditional topics like Interactive Proofs or Zero Knowledge. I might keep varying some of the topics, to see if some new topics might be worth adding.


  1. When he was talking about Sigma-2-P he found that it was hard to keep students interested, and so decided to not cover PH. BILL speculates that this may be true since there are no natural problems there.

    Come again?

    By "there", does BILL mean "in PH - NP"?

  2. Dave Doty: THANKS for the pointer!
    Some of the problems in the paper you point to DO indeed look natural. I may well teach PH next time I do the course!

    Bill (me) means problems that APPEAR to be in
    PH-NP (of course we do not know any that
    ARE there).

  3. Did either of you do any applications for non-theoreticians?

  4. Gilbert- good question. I (Bill) Mentioned compiler applications and that reg exp are used in grep, and I did talk about Minimization of automata.
    However, I would say no, not much on applications. Some lip service.

    There is a required PL class that does some of that, and a non-required compiler design course. However, if you have som
    suggestions I would love to hear them.
    (comment on this blog).

  5. Dave : When I talked about Sigma_2, I gave the example of smallest equivalent formula. But yet it was hard to sustain interest. I was aware of the survey, but might have picked a wrong example. As PH was what I considered an optional topic, I decided to not cover it.

    Gilbert : When I was doing the CYK algorithm for CFG's, I mentioned that a compiler would have to parse and recognize the syntax of a programming languages and so understanding the structure in an efficient manner is important. While doing P vs NP, I mentioned that P represents the notion of efficient problems. Similarly, talked about why space efficiency is important. Like Bill Gasarch says, this was mostly lip service and not real applications.

  6. Nowadays, to do any serious systems engineering, it seems like one needs a whole stack of graduate-level textbooks.

    Our QSE Group is trying trying to compress this stack using the idea of naturality. For younger systems engineers this is a matter of professional survival ... students can't afford to spend seven years in graduate school!

    So, if an automata class were organized around the idea of "naturality", which of the (many) automata-related concepts/theorems mentioned in the post would be most central?

    And, how might one link these concepts together "naturally", to help speed student understanding, both in the narrow context of computational complexity, and perhaps in the broader context of naturality-driven systems engineering?

  7. - the topics you're suggesting really sound like they would be part of a computational complexity syllabus rather than an automata class.

    - for 'natural' problems that cover both automata -and- complexity -and- are known not to be in P, how about regular expression equivalence (when you have extra operators like squaring or complement).

    - if you don't care about 'known to be in P' how about 'QSAT is PSPACE complete'? I consider that natural.

  8. I second Mitch's first comment. The topics seem to me to be more suitable for a complexity course than an automata course. The title of the course may need a change.

    In an automata theory course, I would follow more or less Hopcroft-Ullman (Motwani) ( I prefer the previous edition) with some updates. I am also a bit surprised to hear that neither of you had pumping, Ogden, ... in an automata theory course.

  9. CMSC452 Elementary Theory of Computation

    seems nice and vague enough for almost anything

  10. CS 4510, Automata and Complexity

    title seems to cover any combination of both or either

  11. Mitch & Anonymouses : The class I taught was called 'Automata and Complexity'.

    And I did talk about Pumping Lemma for Regular and Context Free Languages, in detail. Just thought it was too obvious to mention. I only wanted to mention where I possibly deviated from a standard class.

  12. I (Bill) alos did indeed cover Pumping Lemmas for REG and CFL. The reason that the post seems like its topics in complexity is because we discussed the
    EXTRA topics we did, not the standard ones.

    We both did the standard topics
    (DFA,NDFA, REG EXP, Pumping, CFL, PDA,
    Pumping, Computable, c.e. sets, Cooks theorem, reductions).

  13. I didn't do proofs of obvious things.

    I think you lose something here. There is some value in teaching students to think and write formally. Yes, the proofs can sometimes get boring, but you will be amazed how many students in your class could not write (a proof sketch for) an obvious statement.

  14. I agree with the anonymous above. But I am not sure what is the best way to teach students to be rigorous. I have developed this skill by writing proofs and getting feedback on them. I am not sure that a lecture is a good place to teach these, or if this course is appropriate. In an ideal world, one would expect a student to have developed these skills by 3rd year, but we are not living in such a world.

    Any suggestions one this?

  15. At UMCP there is a Discrete Math course they take in their sophmore year BEFORE taking automata theory or algorithms which is supposed to teach them how to prove things.

    I've taught the course several times myself.

    It works some.
    I"ll post on that next time I teach it.

  16. Anonymouses : Like Bill says above, this is a senior level course, so the students typically are aware of proving techniques.

    Moreover, I do not wish to eliminate all obvious looking proofs. For example, when teaching DFA's next, I would teach the closure properties rigorously. Similarly for DFA = NFA. But I think the proof that Regular Expressions are equivalent can be omitted, I would just give an outline and have the students read through the details. Once you have the outline, the details can be worked out and they are not so instructive. I think Bill would agree with this too.

  17. We have a similar second year course, but it seems that sometimes some students pass those courses while they still can't write rigorous proofs, and therefore fail automata & complexity course. But I guess we can't do much about this. Thank you both for the your responses, and the posts about the course.

  18. Bill,

    I took automata from Elaine Rich while she was writing her textbook on the subject. There's an about 150 page appendix of applications at the back of the book. I'd recommend checking that out for some ideas.