GUEST BLOGGER: Bill Gasarch (BEFORE I START TODAYS BLOG- A REQUEST. EMAIL ME OTHER LUDDITE QUESTIONS- I WILL POST THE BEST ONES ON FRIDAY) If u,v \in \Sigma^* then u is a SUBSEQUENCE OF v if you can obtain u by taking v and removing any letters you like. EXAMPLE: if v= 10010 then e,0,1,00,01,10,11,000,001,110,0010,1000,1001,1010,10010 are all of its subsequences Let L be any language-- a subset of \Sigma^* SUBSEQ(L) is the set of subsequences of all of the strings in L. The following three could be easy problems in a course in automata theory: a) Show that if L is regular then SUBSEQ(L) is regular b) Show that if L is context free then SUBSEQ(L) is context free c) Show that if L is c.e. then SUBSEQ(L) is c.e. (NOTE- c.e. is computably enumerable- what used to be called r.e.- recursively enumerable) Note that the following is not on the list: Show that if L is DECIDABLE then SUBSEQ(L) is Decidable. Is this even true? Its certainly not obvious. THINK about this for a little bit before going on. There is a theorem due to Higman (1952), (actually a corollary of what he did) which we will call SUBSEQ THEOREM: If L is ANY LANGUAGE WHATSOEVER over ANY FINITE ALPHABET then SUBSEQ(L) is regular. This is a wonderful theorem that seems to NOT be that well known. It's in very few Automata theory texts. It is not heard much. It falls out of well quasi order theory, but papers in that area (is that even an area?) don't seem to mention it much. This SEEMS to be an INTERESTING theorem that should get more attention, which is why I wrote this blog. Also, I should point out that I am working on a paper (with Steve Fenner and Brian Postow) about this theorem. BUT to ask an objective question: Why do some theorems get attention and some do not? 1) If a theorem lets you really DO something, it gets attention. There has never been a case of `OH, how do I prove L is regular? WOW- its the subseq language of L' !!' By contrast, the Graph Minor Theorem, also part of well quasi order theory, lets you PROVE things you could not prove before. 2) If a theorem's proof is easy to explain, it gets attention. The SUBSEQ theorem needs well quasi order theory to explain. (`needs' is too strong- Steve Fenner has a prove of the |\Sigma|=2 case that does not need wqo theory, but is LOOOOOOOOOOOOOONG. He things he can do a proof for the |\Sigma|=3 case, but that will be LOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOONG. Can be explained to an ugrad but you are better off going through wqo theory.) 3) If a theorem CONNECTS to other concepts, its gets attention. There are no real consequences of the SUBSEQ theorem. Nor did it inspire new math to prove it. 4) If a theorem has a CHAMPION it may get attention. For example the SUBSEQ Theorem is not in Hopcroft-Ullman's book on automata theory- one of the earliest books (chicken and egg problem- its not well known because its not in Hopcroft-Ulman, its not in HU because its not well known). The SUBSEQ theorem had no CHAMPION. 5) Timing. Higman did not state his theorem in terms of regular languages, so the CS community (such as it was in 1952) could not really appreciate it anyway. Yet, it still seems like the statement of it should be in automata theory texts NOW. And people should just know that it is true. Are there other theorems that you think are interesting and not as well known as they should be? If so I INVITE you to post them as comments. The theorem that gets the most votes as SHOULD BE BETTER KNOWN will then become better known and hence NOT be the winner, or the loser, or whatever. NOTE: The |\Sigma|=1 case of Higman's theorem CAN be asked in an automata theory course and answered by a good student.