Talk:CYK algorithm: Difference between revisions

Revision as of 13:09, 26 February 2014

Revision as of 20:31, 27 February 2014

Line 16:

Beau Shiel had a nice paper about it at Coling 76. The empty word is a problem that cannot be escaped, if parse-trees are to be preserved, which is implied by the name parser (but sometimes not described with the algorithm). If no parse tree is kept, it is a recognizer.

The size of a grammar should be defined explicitly, or a reference given.

For building the parse-tree it is always necessary to store a list of nodes with at least one for each non-terminal found.

The proper way to write for an encyclopedia is to give the modern and simpler description first. Then to give some historical details such as the use of CNF in the first versions. On the other hand, the CNF is easier to explain. It should be noted that it loses infinite ambiguity.

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)