9/32
\begin{frame}{Cocke-Younger-Kasami Algorithm (1965)}
\begin{block}{}
Let $G$ be a grammar in Chomsky normal form.
\smallskip

\emph{Goal:} determine whether word $w \ne \lambda$ is in $L(G)$.
\pause\medskip

\emph{Idea:} compute sets $V_{u}$ of variables ($u$ subword of $w$) such that
\begin{talign}
\alert{V_{u}} = \{\, A\in V \mid A \Rightarrow^+ u \,\}
\end{talign}
\pause
as follows:
\begin{itemize}
\pause
\item if $|u| = 1$, then $V_{u} = \{\, A \in V \mid A \to u \in P \,\}$
\pause
\item if $|u| > 1$, then $V_{u}$ is the set of all $A \in V$ such that
\begin{itemize}
\item $u = u_1u_2$ for some non-empty words $u_1,u_2$, and
\item $A\to BC \in P$ with $B \in V_{u_1}$ and $C\in V_{u_2}$.
\end{itemize}
\end{itemize}
\pause
Finally, \alert{$w \in L(G)$} $\Leftrightarrow$ \alert{$S\in V_{w}$}.
\end{block}
\pause\medskip

\begin{goal}{}
\structure{Worst-case time complexity}: $O(n^3)$\\
(There are $n(n+1)/2$ sets $V_{u}$, and computation of $V_{u}$ is $O(n)$.)
\end{goal}
\end{frame}