CYK algorithm
In computer science, the Cocke–Younger–Kasami algorithm (alternatively called CYK, or CKY) is a parsing algorithm for context-free grammars published by Itiroo Sakai in 1961. The algorithm is named after some of its rediscoverers: John Cocke, Daniel Younger, Tadao Kasami, and Jacob T. Schwartz. It employs bottom-up parsing and dynamic programming. The standard version of CYK operates only on context-free grammars given in Chomsky normal form (CNF). However any context-free grammar may be transformed (after convention) to a CNF grammar expressing the same language.
- Abstraction100002137
- Act100030358
- Activity100407535
- Algorithm105847438
- Communication100033020
- Event100029378
- Language106282651
- Procedure101023820
- PsychologicalFeature100023100
- Rule105846932
- WikicatAlgorithms
- WikicatAlgorithmsOnStrings
- WikicatFormalLanguages
- WikicatParsingAlgorithms
- YagoPermanentlyLocatedEntity
- Class
- enParsing with context-free grammars
- Comment
- enIn computer science, the Cocke–Younger–Kasami algorithm (alternatively called CYK, or CKY) is a parsing algorithm for context-free grammars published by Itiroo Sakai in 1961. The algorithm is named after some of its rediscoverers: John Cocke, Daniel Younger, Tadao Kasami, and Jacob T. Schwartz. It employs bottom-up parsing and dynamic programming. The standard version of CYK operates only on context-free grammars given in Chomsky normal form (CNF). However any context-free grammar may be transformed (after convention) to a CNF grammar expressing the same language.
- Data
- String (computer science)
- Depiction
- Has abstract
- enIn computer science, the Cocke–Younger–Kasami algorithm (alternatively called CYK, or CKY) is a parsing algorithm for context-free grammars published by Itiroo Sakai in 1961. The algorithm is named after some of its rediscoverers: John Cocke, Daniel Younger, Tadao Kasami, and Jacob T. Schwartz. It employs bottom-up parsing and dynamic programming. The standard version of CYK operates only on context-free grammars given in Chomsky normal form (CNF). However any context-free grammar may be transformed (after convention) to a CNF grammar expressing the same language. The importance of the CYK algorithm stems from its high efficiency in certain situations. Using big O notation, the worst case running time of CYK is , where is the length of the parsed string and is the size of the CNF grammar . This makes it one of the most efficient parsing algorithms in terms of worst-case asymptotic complexity, although other algorithms exist with better average running time in many practical scenarios.
- Is primary topic of
- CYK algorithm
- Label
- enCYK algorithm
- Link from a Wikipage to an external page
- archive.org/details/introductiontoth00sips/page/99
- martinlaz.github.io/demos/cky.html
- www.softwarepreservation.org/projects/FORTRAN/CockeSchwartz_ProgLangCompilers.pdf
- www.swisseduc.ch/informatik/exorciser/
- www.informatica-didactica.de/index.php%3Fpage=LangeLeiss2009
- archive.org/details/introductiontoau00hopc
- Link from a Wikipage to another Wikipage
- Air Force Cambridge Research Laboratories
- Algorithm
- Ambiguous grammar
- Analysis of algorithms
- Asymptotic complexity
- Big O notation
- Big O Notation
- Boolean matrix
- Bottom-up parsing
- Category:Parsing algorithms
- Chomsky normal form
- Computational Intelligence (journal)
- Computer science
- Context-free grammar
- Coppersmith–Winograd algorithm
- Courant Institute of Mathematical Sciences
- Dynamic programming
- Earley parser
- File:CYK algorithm animation showing every step of a sentence parsing.gif
- Formal grammar
- GLR parser
- Information and Computation
- Inside–outside algorithm
- Jacob T. Schwartz
- John Cocke (computer scientist)
- Journal of Computer and System Sciences
- Journal of the ACM
- Matrix multiplication algorithm
- New York University
- Packrat parser
- Parser
- Parse tree
- Parsing
- Pseudocode
- Recognizer
- Stochastic context-free grammar
- String (computer science)
- Tadao Kasami
- Weighted context-free grammar
- Name
- enCocke–Younger–Kasami algorithm
- SameAs
- 55dEL
- Algorithme de Cocke-Younger-Kasami
- Algoritmo CYK
- Algoritmo CYK
- Algoritmo CYK
- Algoritmus Cocke-Younger-Kasami
- Algorytm CYK
- Cocke-Younger-Kasami-Algorithmus
- CYK algorithm
- CYK-algoritme
- CYK-algoritme
- CYK-algoritmen
- CYK-algoritmi
- CYK法
- CYK算法
- CYK 알고리즘
- m.0f3df
- Q954821
- Thuật toán CYK
- Алгоритм Кока — Янгера — Касами
- Кук-Јангер-Касами алгоритам
- الگوریتم سی وای کا
- خوارزمية CYK
- Subject
- Category:Parsing algorithms
- Thumbnail
- Time
- en, where: * is length of the string * is the size of the CNF grammar
- WasDerivedFrom
- CYK algorithm?oldid=1113022326&ns=0
- WikiPageLength
- 17032
- Wikipage page ID
- 53929
- Wikipage revision ID
- 1113022326
- WikiPageUsesTemplate
- Template:Cite book
- Template:Cite conference
- Template:Cite journal
- Template:Cite techreport
- Template:Harv
- Template:Harvtxt
- Template:Infobox algorithm
- Template:Mvar
- Template:Parsers
- Template:Reflist
- Template:Tmath
