Here's a problem from Janos Simon. For a set A, let L(A)={x | for some m≥0, x 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?^{m}is in A}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