Loading ...
Sorry, an error occurred while loading the content.

[My Computational Complexity Web Log] A Regular Problem Solved

Expand Messages
  • Lance Fortnow
    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
    Message 1 of 1 , Dec 4, 2003
    • 0 Attachment
      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).

      --
      Posted by Lance Fortnow to My Computational Complexity Web Log at 12/4/2003 07:31:43 AM

      Powered by Blogger Pro

    Your message has been successfully submitted and would be delivered to recipients shortly.