Linear Grammar in less than cubic time

I have a linear grammar $$G$$ and a string $$s$$. $$G$$ is is not limited to right or left linear only but rather has a mix of rules of both types.

Is there an algorithm to determine whether $$s \in L(G)$$ in less than cubic time?

Converting to CNF and applying the CKY algorithm takes cubic time, and I am wondering if there is a more efficient algorithm.

• You can apply CKY directly, without transforming (it's essentially a dynamic programming algorithm; transforming to CNF is needed only for guaranteed running time). It'll take quadratic time.
– user114966
Oct 5 '20 at 12:11
• @Dmitry Why would the CKY take quadratic time here? Oct 5 '20 at 14:36
• CYK is a dynamic programming algorithm with $n^2$ states. For each state, computation takes $n^{k-1}$ time, where $k$ is the maximum number of nonterminals on the RHS of a rule. For CNF, $k=2$, for linear grammar, $k=1$.
– user114966
Oct 5 '20 at 16:46
• @Dmitry According to en.wikipedia.org/wiki/CYK_algorithm it loops over the input 3 times and thus the cubic time. Would this not be needed to be adjusted in some way to get to $O(n^{2})$? Oct 5 '20 at 20:52
• Please don't make more work for other people by vandalizing your posts. By posting on the Stack Exchange (SE) network, you've granted a non-revocable right, under the CC BY-SA 4.0 license for SE to distribute that content. By SE policy, any vandalism will be reverted. If you want to know more about deleting a post, consider taking a look at: How does deleting work? Oct 8 '20 at 5:18

Yes, you can. As Dmitry explains, CYK parsing can be used to parse a linear grammar in $$O(n^2)$$ time, where $$n$$ is the length of the input word.
CYK parsing is a dynamic programming algorithm that sets $$P[l,s,R]$$ to be true if $$a_{s .. s+l-1}$$ can be generated from the non-terminal $$R$$, where $$a_{1..n}$$ is the input word.
Note that there is a recurrence relation that can be used to compute $$P[l,s,R]$$ from values of the form $$P[l',s',R']$$ with $$l', in $$O(1)$$ time. In particular, if we have the rule $$R \to b_1\cdots b_k Q c_1 \cdots c_m$$, then we should set $$P[l,s,R]$$ to true if $$a_{s .. s+k} = b_{1 .. k}$$ and $$P[l-k-m,s+k,Q]$$ is true and $$a_{s+l-m .. s+l-1} = c_{1 .. m}$$. Do this for each rule with $$R$$ on the left-hand side. If none of them sets $$P[l,s,R]$$ to true, set $$P[l,s,R]$$ to false. This takes $$O(1)$$ time (treating the size of the grammar as a constant).
We repeat this for each of the entries $$P[l,s,R]$$. There are $$O(n^2)$$ such entries (treating the size of the grammar as a constant), and each entry takes $$O(1)$$ time to compute, so the entire algorithm runs in $$O(n^2)$$ time.