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

[My Computational Complexity Web Log] A Regular Problem

Expand Messages
  • Lance Fortnow
    Here s a problem from Janos Simon. For a set A, let L(A)={x | for some m0, x m is in A} Simon asked, as a homework problem, to show that if A is regular then
    Message 1 of 1 , Nov 14, 2003
    • 0 Attachment
      Here's a problem from Janos Simon. For a set A, let
      L(A)={x | for some m≥0, xm is in A}
      Simon asked, as a homework problem, to show that if A is regular then L(A) is also regular. The standard solutions require an exponential increase in the number of states. Simon asks whether this is needed in general. If A is accepted by an n-state DFA, can one find a poly(n)-state DFA for L(A) or is an exponential state DFA for L(A) required?

      As an aside the submission deadline for the Complexity Conference is right around the corner. Get your papers ready.

      --
      Posted by Lance Fortnow to My Computational Complexity Web Log at 11/14/2003 09:17:53 AM

      Powered by Blogger Pro

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