2
$\begingroup$

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?

Improve this question
$\endgroup$

0

Reset to default

Your Answer

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