Paper Info
Title
An improved version of the Cocke-Younger-Kasami algorithm
Abstract
The Cocke-Younger-Kasami algorithm (CYK) always requires 0(n^3) time and 0(n^2) space to recognize a trial sentence @w = w"1w"2...w"n, given an e-free context-free grammar in Chomsky Normal form. The same inductive rule that underlies the CYK algorithm may be used to produce a variant that computes the same information but requires (1) a maximum of 0(n^3) time and 0(n^2) space, and (2) only 0(s(n)) space and time for an unambiguous grammar, where s(n) is the number of triples (A,i,j) for which a nonterminal symbol A derives w"iw"i"+"1...w"i"+"j"-"1. In this case, time and space consumed are at worst 0(n^2). It is shown in addition, for any grammar, that a parse may be obtained from the table left from the recognition algorithm in time 0(s(n)) whether or not the grammar is ambiguous. The same procedure for the CYK algorithm requires time 0(n^2). The performance of our variant is quite similar to that of the Earley algorithm except that the Earley algorithm substitutes for s(n), a function which is usually smaller. The model we use of a RAM is strictly identical to the model used in the CYK algorithm. CR categories: 4.20, 5.23, 5.25.
Year
DOI
Venue
1978
10.1016/0096-0551(78)90029-2
Comput. Lang.
Keywords
DocType
Volume
Cocke-Younger-Kasami algorithm,Younger algorithm,Parsing table replacement,recognition algorithm,inductive rule,e-free context-free grammar,Chomsky Normal form,Parsing,improved version,unambiguous grammar,CYK algorithm,Earley algorithm,Earley algorithm substitute,Earley parsing algorithm,CR category,List processing
Journal
3
Issue
ISSN
Citations 
2
Computer Languages
1
PageRank 
References 
Authors
2.36
1
1
Name
Order
Citations
PageRank
Glenn K. Manacher120598.95