6
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ 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))$. $\endgroup$ – xskxzr Jul 11 '18 at 7:38
  • $\begingroup$ IIUC, if any CFL is not in DTIME(O(n)) then Greibach's hardest CFL must not be. $\endgroup$ – Max Aug 23 '18 at 15:44
2
$\begingroup$

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$.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.