# 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