Talk:CYK algorithm: Difference between revisions

Revision as of 22:02, 20 July 2010

Revision as of 11:27, 3 December 2010

Line 59:

Is that paper from 2009 really notable enough to warrant a citation in Wikipedia? It is used to make a fairly technical point. Since all other sources (besides Knuth, which is a reference work) are from the 60s, 70s, it makes the impression as if the latest paper would be the only continuation of the study of this algorithm, which is difficult to believe... that is, IMO it inflates the importance of the paper and the reference should be removed.

:While I understand your feelings about giving undue weight to that paper, I would suggest to add more references of recent date about the CYK algorithm. For instance, the CYK algorithm, as well as Valiant's improvement have been recently generalized from context-free grammars to the case of [[Boolean grammar]]s. Removing content from the article would certainly be a step into the wrong direction, given the size of the article. If there are any recent papers that deserve to be included, please [[Wikipedia:Be_bold|be bold]] and just go ahead. I am confident that the article will further expanded over time, given that the article's subject is covered in many textbooks and courses on automata theory. [[User:Hermel|Hermel]] ([[User talk:Hermel|talk]]) 21:29, 20 July 2010 (UTC)

==Lange & Leiß==

In the previous comment, do you mean the Lange & Leiß paper? I just read that paper, without going deep into the math, and found it incredibly informative, since the main aim is pedagogical.

The paragraph in this article summarizing this paper is weak, and would benefit from being written in more specific terms concerning the three operations (BIN, DEL, UNIT) necessary to transform to CNF, the effect of ordering these operations on size explosion (exponential if DEL precedes BIN), and that DEL and UNIT can be internalized into the CYK algorithm at no extra cost, leaving only a linear transformation on grammar size into 2NF form (BIN). This papers omits TERM because it offers no advantage for the CYK algorithm.

Why so concerned about importance? Clarity often comes at remove from original research and should be valued for its own sake. — [[user:MaxEnt|MaxEnt]] 11:27, 3 December 2010 (UTC)