2
$\begingroup$

Is there a context sensitive language $L$ so that $L$ cannot be recognized by a deterministic linear bounded turing machine in $O(n^2)$ steps, but still can be recognized by a deterministic LBA?

The existence of $L$ would imply that linear-space-bounded cellular automata are more powerful than linear-time cellular automata: All deterministic CSL's can be recognized by linear-space-bounded cellular automata and linear-time cellular automata can be simulated by LBA's in $O(n^2)$ steps.

By using crossing-sequences, it is shown that unbounded LBA's are more powerful than linear-time-bounded LBA's. In particular the context free language $\{ ww^R\: | \: w \in \Sigma^* \}$ cannot be recognized by a turing machine in $O(n)$ steps, but can be recognized in $O(n^2)$ steps.

Improve this question
$\endgroup$
1
  • $\begingroup$ A stronger question is: Is there an universal deterministic LBA, i.e. a deterministic LBA that can decide whether a given (encoded) deterministic LBA accepts a given input? This would allow diagonalization. $\endgroup$
    – Henning
    Commented Jul 15, 2017 at 14:01

0

Reset to default

Your Answer

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