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!
- 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!
- 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!
- 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!
