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 that you have read and understand our privacy policy and code of conduct.