I am reading an old paper [1] about time complexity of context-free languages. The computational model is the standard one-tape Turing machine. It is written on page 377 without a proof that "we can show that there exist infinitely many different computational classes of context-free languages between the time functions $T(n)=n\log n$ and $T(n)=n^2$". I am wondering:

Question 1: What is actually known about the time hierarchy for context-free languages?

More specific question:

Question 2: Consider functions $T(n)=n^a(\log n)^b$. Do context-free languages distinguish the classes $\textrm{TIME}(T(n))$ for rational $a\in [1,2)$ and $b\geq 0$?

[1] J. Hartmanis. Computational complexity of one-tape Turing machine computations.



Your Answer

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