Talk:CYK algorithm: Difference between revisions

Revision as of 07:57, 26 February 2014

Revision as of 13:09, 26 February 2014

Line 11:

:The example given is for ''parsing'' sentences into NP, VP and so on, which is more than [[part-of-speech tagging]]. It may be more common to introduce CYK with artificial examples, but I don't see anything wrong with using an example from an application area. [[Computational linguistics]] is one of the areas where CYK is applied, and CYK is sometimes studied as part of a CL curriculum. But I've reconstructed the grammar from the example and added it to the article. It should now make more sense. -- [[User:UKoch|UKoch]] ([[User talk:UKoch|talk]]) 17:25, 20 December 2011 (UTC)

== I think there is still much room for improvement ==

==I don't like the article either ==

The fact that binary form (no RHS longer than 2) should be used, rather than CNF has been known for about 40 years. It was not published, because it was considered obvious, as the complexity results from the length of right-hand sides. It is also the only way to preserve conveniently the shape of parse trees.

Line 22:

In 1974, Valiant used the Strassen algorithm (1969) to reduce the complexity, but the complexity of matrix multiplication was reduced since then, first by Coppersmith–Winograd (1990), then by Williams (2011). It should be better to discuss usability on the basis of Strassen's algorithm, which is the only one that has a chance of being meaningful. <small><span class="autosigned">—&nbsp;Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[User:Teetooan|Teetooan]] ([[User talk:Teetooan|talk]] • [[Special:Contributions/Teetooan|contribs]]) 00:45, 26 February 2014 (UTC)</span></small><!-- Template:Unsigned --> <!--Autosigned by SineBot-->

[[User:Teetooan|Teetooan]] ([[User talk:Teetooan|talk]]) 00:49, 26 February 2014 (UTC)

It might be nice to underscore that CYK is the only cubic algorithm that can run directly on the grammar (up to the binary transformation, that is both trivial an unescapable).[[User:Teetooan|Teetooan]] ([[User talk:Teetooan|talk]]) 13:09, 26 February 2014 (UTC)

==Explain practical parse tree generation!==