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 , 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