Cocke Younger Kasami [CYK]
Mathematics 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 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 for CYK algorithm.
Image credit: Presentation on theme: "1 The Cocke-Younger-Kasami Algorithm * Chung, Sei Kwang *Alfred Aho, Jeffrey Ullman 의 “The Theory of Parsing, Translation, and Compiling” 과 인터넷을 참고하여 작성되었습니다." SlidePlayer.
BACK TO IBM RESEARCH ACCOMPLISHMENTS