For the language $ L= \{a^kb^k | k \geq 0 \} $ How can i show there is no one-tape Turing Machine that can decide $L$ in less than $O(n\log n)$ time ?

  • 1
    $\begingroup$ Have you tried to use the method of crossing sequences? $\endgroup$ Mar 22 at 18:40
  • $\begingroup$ @YuvalFilmus If i define $L_n = \{ a^kb^k | n \geq k \geq 0 \}$ and consider crossing sequences between $n+1$ (to include at least one b) and $2n$ , is it good idea to think about ? $\endgroup$ Mar 22 at 18:59
  • 1
    $\begingroup$ Yes, that's the first step. $\endgroup$ Mar 22 at 19:16


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.