Cocke Younger Kasami (CYK) First N3 Algorithm for Parsing Ambiguous Languages       


Programming Languages Accomplishment | 1970

IBM researchers: John Cocke, Daniel Younger, Tadao Kasami

Where the work was done: IBM T.J. Watson Research Center

What we accomplished: Paraphrasing Wikipedia, "CKY is a parsing algorithm for context-free grammars. The importance of CYK stems from its high efficiency in certain situations. The worst case running time of CYK is \Theta (n^{3}\cdot |G|), where n is the length of the parsed string and |G| is the size of the CNF grammar G. This makes it one of the most efficient parsing algorithms in terms of worst-case asymptotic complexity."

Related links: Wikipedia Entry

BACK TO PROGRAMMING LANGUAGES
BACK TO IBM RESEARCH ACCOMPLISHMENTS