# Tag Info

2

After discussing it further with a3nm, I propose an algorithm that is different than Neal's algorithm and works in a more general setting. The approach gives polynomial delay algorithm but it uses exponential space. The only two properties that we will be using are : (1) The problem is self-reducible, in the sense that if I am given an automaton $A$ and $u \... 6 Here is a proposition for an elementary proof: Let$\mathcal A=(A,Q,q_0,F,\delta)$be a DFA for$L$, we want to build a DFA$\mathcal A'=(A,Q',q_0',F',\delta')$for$f^{-1}(L)$. Intuitively, when reading a word$u$,$\mathcal A'$will remember the state reached in$\mathcal A$by$f(u)$, together with the action of$u$on all states of$\mathcal A\$. More ...

Top 50 recent answers are included