The CYK algorithm, also called the Cocke-Younger-Kasami algorithm, is a parsing algorithm for context-free grammars published by Itiroo Sakai in 1961 and named for several of its rediscoverers, including John Cocke, Daniel Younger and Tadao Kasami. It uses bottom-up parsing and dynamic programming, operates on grammars in Chomsky normal form, into which any context-free grammar can be algorithmically converted, and its worst-case running time makes it one of the most efficient parsing algorithms by asymptotic complexity, even though other algorithms can be faster in practice.
Facts
Time Complexity
Time Complexity (category) Classification
Design Technique Connections
Credited To
Source CYK algorithm (Wikipedia)
In Field
Source CYK algorithm (Wikipedia)
Invented By
Source CYK algorithm (Wikipedia)
Uses Design Technique
Sources
1. CYK Algorithm (Wikipedia)
https://en.wikipedia.org/wiki/CYK_algorithmQuote, https://en.wikipedia.org/wiki/CYK_algorithm
It employs bottom-up parsing and dynamic programming.
2. CYK algorithm (Wikipedia)
Lead
Using big O notation, the worst case running time of CYK is O ( n 3 ⋅ | G | )
- In Field: Algorithms and Complexity Theory, Lead paragraph
In Group: Parsing Algorithms, Lead section
is a parsing algorithm for context-free grammars
Credited To: John Cocke, Lead paragraph
The algorithm is named after some of its rediscoverers: John Cocke, Daniel Younger, Tadao Kasami, and Jacob T.
Invented By: John Cocke, Lead paragraph
The algorithm is named after some of its rediscoverers: John Cocke, Daniel Younger, Tadao Kasami, and Jacob T.
View the SourceReader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.