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
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
Can be explained to an ugrad but you are better off going through
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.