CYK

GPTKB entity

Statements (19)
Predicate Object
gptkbp:instanceOf gptkb:algorithm
gptkbp:category dynamic programming
parsing algorithm
gptkbp:complexity O(n^3 * |G|)
gptkbp:field computer science
formal language theory
gptkbp:firstPublished 1960
gptkbp:fullName gptkb:Cocke–Younger–Kasami_algorithm
https://www.w3.org/2000/01/rdf-schema#label CYK
gptkbp:input string
context-free grammar in Chomsky normal form
gptkbp:namedAfter gptkb:John_Cocke
Daniel Younger
Tadasi Kasami
gptkbp:output parse table
boolean (whether string is in language)
gptkbp:usedFor parsing context-free grammars
gptkbp:bfsParent gptkb:Clydebank_railway_station
gptkbp:bfsLayer 7