patternMinor
Are there any context-free languages that are not known to be in $\mathrm{DTIME}(O(n))$?
Viewed 0 times
dtimemathrmfreearelanguagesanythatknowncontextthere
Problem
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?
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?
Solution
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$.
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$.
Context
StackExchange Computer Science Q#94127, answer score: 4
Revisions (0)
No revisions yet.