Here's a problem from Janos Simon. For a set A, let

L(A)={x | for some m≥0, x^{m} 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.

## No comments:

## Post a Comment