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:

Regular Languages: DFA's, NFA's, Reg Expressions.

PDA's, CFL's.

Turing Machines, computable and c.e. sets.

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.

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 omegaautomta, 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 828 of
this PhD thesis.

I am NOT going to do the algorithm for MINIMIZING a DFA.

I am NOT going to do ContextSensitive Languages.

I am NOT going to have them prove things that are obvious, like
that S>aSb, S>emptystring generates {a^{n}b^{n}}.
Generally I am against having students prove things that are obvious.

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.

I am NOT going to to Primitive Recursive functions.

In the NPC section I WILL DO the protocol for, in our language, NGI (nonGraphIsom)
is in AM.

In the NPC section I WILL DO the protocol for, in our language, given bitcommit,
3COL is in ZK. (I may to other ZK protocols as well.)

In the NPC section will do that Vertex Cover with FIXED k is in O(n^{2})
(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(n^{k})) being
WRONG. Shows the NEED to prove things.

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.

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