# Are there any context-free languages that are not known to be in $\mathrm{DTIME}(O(n))$?

The problem of determining, given a string $x$ and a context-free grammar $G$, whether $x \in L(G)$ is conjectured to take more than linear time in the length of $x$. Currently the best known algorithm is Valiant's which takes $\Theta(|G||x|^\omega)$.

On the other hand, for a fixed $G$ there may be a specialized recognition algorithm which is faster, and indeed linear-time algorithms have been developed for many grammars and classes of grammars of interest. In fact, I can't think of any example of a language which doesn't have a linear-time recognition algorithm.

Is there any example of a context-free language that is not known to be recognizable in linear time?

• Related: $\mathsf{DTIME}(O(n))\neq \mathsf{NTIME}(O(n))$ and the computational problem corresponding to a context-free language belongs to $\mathsf{NTIME}(O(n))$. – xskxzr Jul 11 '18 at 7:38
• IIUC, if any CFL is not in DTIME(O(n)) then Greibach's hardest CFL must not be. – Max Aug 23 '18 at 15:44

Theorem 1 in "If the Current Clique Algorithms are Optimal, so is Valiant’s Parser" shows an explicit context-free grammar $$G$$ such that if $$G$$ can be parsed in linear time (or even a bit slower), then there's a surprisingly fast algorithm for the $$k$$-clique problem. As the paper says, no such algorithm for $$k$$-clique is known to exist and it would be a breakthrough if it was discovered; therefore, there's no known linear-time algorithm for this grammar $$G$$.