for a language $L$ we define $rev\left(L\right)=\left\{ \sigma_{n}\cdot\ldots\cdot\sigma_{1}\mid w=\sigma_{1}\cdot\ldots\cdot\sigma_{n}\in L\right\} $.

My question is, are $\mathsf{L,NL}$ closed under this operation?

Meaning, for example, that if $L\in\mathsf{L}$ is $rev(L)\in\mathsf{L}$?

I think the answer is yes if we simply move the head of the input tape to the end, read the input from start to end, but I'm not sure if causes any problems with logarithmic space.

Is this also correct for the class L-complete, L-hard and NL-complete, NL-hard?



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.