8
$\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?

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

1 Answer 1

Reset to default
4
$\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$.

Improve this answer
$\endgroup$
0

Your Answer

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

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