## Thursday, January 17, 2013

### Open Problems

One of the nice things about teaching an upper-level undergraduate course at a university is the opportunity to mention problems at the edge of our current knowledge. For example, in my course CS 462, Formal Languages and Parsing, I currently mention 15 open problems and offer an automatic 100 in the course for anyone who can solve any one of them.

Anonymous said...

It seems that problem 15 is not stated in the same way on your page and in the pdf.

You ask for words that are not pairwise equal, the pdf talks about words that don´t commute pairwise.

Your version seemes to allow a simple solution (taking 2 words of which one is the square of the other). (If this is wrong, it is caused by my ignorance of the field)

Jeffrey Shallit said...

Thanks! It's just a typo, which I've corrected.

Anonymous said...

There is also a small typo in #12 (which doesn't affect the problem statement).

I am not in your course but am interested. Would it be possible to provide a pointer to the sources of the question(s) for those not provided please? [I try to understand the context within which a problem is posed first and then explore alternative equivalent expressions for generality.] For question #2, I would first attempt to reconcile this with PSLQ/LLL to establish bounds, if any exist. Thank you.

Joel Reyes Noche said...

When I read problem 10, this was the first time I learned about the new name of the Kolakoski word. (I'll try to read Oldenburger's 1939 paper one of these days.) I don't know if the new name will catch on though. (So far, only a few people refer to the Thue-Morse word as the Prouhet-Thue-Morse word.)

Joel Reyes Noche said...

By the way, there is currently an error on the website. Problem 10 says that K = 1221122... but K = 1221121...

Jeffrey Shallit said...

Another typo! I've corrected it, thanks.

The difference between this case and the attribution of Thue-Morse is that it is not really fair to say that Prouhet independently discovered what we now call the Thue-Morse word. He did not discuss it explicitly at all; it is only there if you sort of "read between the lines".

However, Oldenburger really did explicitly discuss K before Kolakoski.

Anonymous said...

Wow, you must have smart students. I would have given a 100 to anyone who solved just one.

Jeffrey Shallit said...

Fascinating - I never would have interpreted "for anyone who can solve them" as "anyone who can solve all of them". What dialect of English do you speak?

Anonymous said...

Yaglom & Yaglom Q.11a Vol 1 may help some on Q.10. While looking for Alfonsin's book (I noted the acknowledgement) I came across your "Automatic Sequences" text 2002. I hope the text will allow me to better understand the problems posed here. Your texts are always copiously referenced which is greatly appreciated. Regarding my earlier request for the sources of the problems, no need.
ANON2

James Cranch said...

I speak UK standard English. I also read that sentence the way your anonymous correspondent did. Obviously I immediately understood your meaning and would never have mentioned it had the subject not arisen, but it did make me smile.

Jeffrey Shallit said...

OK, James, then I will correct it.

IThinkWithMy Liver said...

Please - more mathematical cranks, please! I love seeing mathematical cranks claim to prove to solve the big problems on 1 page, and then see their claims get demolished, but then see them continue to deny the demolition.

IThinkWithMy Liver said...

Sorry. Can't help ya.
I don't know what a DFA or an NFA is!

Wow! I gave my brain a brainache just reading all those problems!