This page contains announcements from previous theory seminars.
The seminar is suspended this semester due to lack of time. It will return Spring 2007.
During Spring 2006, the seminar is held Fridays from 12:45 to 2:15 pm on the USC Columbia campus at 300 South Main Street (across Main Street from Swearingen), room B213.
Friday, Januar 20, 2006 Stephen Fenner will discuss well quasi-orders and the subsequence relation on strings.
Abstract: If x and y are two strings over some alphabet Σ, then we say that x is a subsequence of y if x results from removing zero or more letters from y. Equivalently, x is a subsequence of y iff x = x1x2 ⋅⋅⋅ xn and y ∈ Σ*x1Σ*x2Σ* ⋅⋅⋅ Σ*xnΣ*. Given a language L ⊆ Σ*, we define the language SUBSEQ(L) to be the set of all subsequences of strings in L. It is an easy exercise to show that if L is regular, then so is SUBSEQ(L), or to show that if L is c.e. (Turing recognizable), then so is SUBSEQ(L). A classic theorem of Higman gives a much stronger statement:
If L is any language whatsoever, then SUBSEQ(L) is regular.Higman's proof is nonconstructive; given L, it does not describe a method for finding a deterministic finite automaton (DFA) for SUBSEQ(L). We show that this is not just an artifact of the proof: Higman's theorem is inherently not computable. For example, given a Turing machine M recognizing a language L, there is no computable way to find a DFA for SUBSEQ(L), even though we know that such a DFA must exist.
I'll first prove Higman's theorem using the concept of well quasi-orders. Then I'll show that it is inherently uncomputable.
This is joint work with Bill Gasarch and Brian Postow.
This is tentative and subject to change/addition.
January 20, 28 - Stephen Fenner will talk about well quasi-orders and the complexity of the subsequence relation on strings.
February 3 - (no seminar)
February 10, 17 - Vaibhav Gowadia will talk about XML and tree automata (security-related).
February 24, March 17 - Antonio Rodriguez will discuss game theory and computational aspects thereof.
March 24, 31 - Parsanth Kalakota will talk about some aspects of computer algebra.
This page was last modified Monday December 4, 2006 at 15:34:45 EST.