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.