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.

BILL:
I did do Decidability of WS1S (weak second order with Successor and lessthan).
This was a real winwinwin. (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. 
BILL: NonGraphIsom 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. 
BILL and SUBRUK: Neither of us did Ladner's theorem or the timehierarchy 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.  BILL and SUBRUK: Neither of us did primitive recursive. There is no real punchline there. And we won't in the future.

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 kindof 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.  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.
 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 BermanHartmanis 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 nontraditional topics.
 BILL and SUBRUK: Neither of us did Det PDA's.
 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.
 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.
 SUBRUK pondered doing the poly hierarchy but didn't. When he was talking about Sigma2P 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.
 SUBRUK did space complexity, NLcompleteness, NL = coNL, Savitch's theorem, PSPACEcompleteness. BILL didn't do any of this but is intrigued by the notion of doing it and may consider it in the future.
 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.)
 SUBRUK's Future: As noted above, less details on things that are obvious. I would use the extra time to do more interesting nontraditional 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.
When he was talking about Sigma2P 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.
ReplyDeleteCome again? http://ovid.cs.depaul.edu/documents%5Cphcom.ps
By "there", does BILL mean "in PH  NP"?
Dave Doty: THANKS for the pointer!
ReplyDeleteSome 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
PHNP (of course we do not know any that
ARE there).
Did either of you do any applications for nontheoreticians?
ReplyDeleteGilbert good question. I (Bill) Mentioned compiler applications and that reg exp are used in grep, and I did talk about Minimization of automata.
ReplyDeleteHowever, I would say no, not much on applications. Some lip service.
There is a required PL class that does some of that, and a nonrequired compiler design course. However, if you have som
suggestions I would love to hear them.
(comment on this blog).
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.
ReplyDeleteGilbert : 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.
Nowadays, to do any serious systems engineering, it seems like one needs a whole stack of graduatelevel textbooks.
ReplyDeleteOur 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) automatarelated 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 naturalitydriven systems engineering?
 the topics you're suggesting really sound like they would be part of a computational complexity syllabus rather than an automata class.
ReplyDelete 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.
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.
ReplyDeleteIn an automata theory course, I would follow more or less HopcroftUllman (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.
CMSC452 Elementary Theory of Computation
ReplyDeleteseems nice and vague enough for almost anything
CS 4510, Automata and Complexity
ReplyDeletetitle seems to cover any combination of both or either
Mitch & Anonymouses : The class I taught was called 'Automata and Complexity'.
ReplyDeleteAnd 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.
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
ReplyDeleteEXTRA 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).
I didn't do proofs of obvious things.
ReplyDeleteI 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.
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.
ReplyDeleteAny suggestions one this?
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.
ReplyDeleteI've taught the course several times myself.
It works some.
I"ll post on that next time I teach it.
Anonymouses : Like Bill says above, this is a senior level course, so the students typically are aware of proving techniques.
ReplyDeleteMoreover, 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.
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.
ReplyDeleteBill,
ReplyDeleteI 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.