Algorithms & Randomness Center (ARC)

William Gasarch – University of Maryland

Wednesday, February 17, 20116

Klaus 1116 East - 1:00 pm

(Refreshments will be served in Klaus 2222 at 2 pm)

Title:
Advanced Results in the Theory of Languages and Computation which have Simple Proofs

Abstract:
Automata theory is about the following: Given a language (a set of strings) how hard is it? Is it regular, context free, or decidable? We give three results that COULD be put in a course on such but are not!

1. Regular, Context free, and Decidable languages are closed under many operations. Note the following: if L is regular (CFL) then SUBSEQ(L) is regular (CFL).  This is an easy exercise. But what if L is decidable? Is SUBSEQ(L) decidable? The answer may surprise you!
2. There are languages L that are regular but the DFA for them is much smaller than the CFG for them. How much smaller? The answer may surprise you!
3. It is easy to show that COL3 \le COL4 (three-colorability \le 4-colorablity). Is COL4 \le COL3? You probably know that it is by going through the Cook-Levin Theorem. Is there an easier proof? The answer would surprise you if I didn't ask the question so I'll just say YES- I will show COL4 \le COL3 with a simple proof.

The answers may surprise you!