Thursday, December 04, 2003

A Regular Problem Solved

Paz Carmi, Yinnon Haviv and Enav Weinreb from Ben-Gurion University have solved the regular language problem I posted last month.

The problem came from Janos Simon based on a homework question in Kozen's book. Let L(A)={x|x^m is in A for some m}. The homework question asked to show that L(A) is regular if A is regular. The question Janos asks was how many states do we need for a DFA for L(A) if A has n states. Carmi, Haviv and Weinreb show that an exponential number of states are required.

Not only did they solve the problem but also sent me this nice write-up of the proof. I believe this is the first time someone has directly solved a problem I've given on this weblog. I owe each of them a beer (or non-alcoholic beverage of their choice).

Update 12/9: I received the following today from Markus Holzer.

It seems that I have missed your posting about the problem last month. The problem you have stated was already solved in June by Jeff Shallit and co-authors. They have given a lower bound on the DFA accepting root, by considering the (largest) syntactic monoid induced by two generators. The latter problem on syntactic monoid size is of its own interest and I was working on that for a while, therefore I know the result of Shallit et al on the root descriptional complexity. Maybe you also owe the beers to Shallit et al.

No comments:

Post a Comment