Content deleted Content added
→Valiant's algorithm: +abboud et al |
m Various citation & identifier cleanup, plus AWB genfixes. Citation bot to follow |
||
Line 34:
<div class="toccolours mw-collapsible mw-collapsed">
==== Probabilistic CYK (for finding the most probable parse) ====
Allows to recover the most probable parse given the probabilities of all productions.
Line 120 ⟶ 121:
as the CYK algorithm; yet he showed that [[Matrix multiplication algorithm#Sub-cubic algorithms|algorithms for efficient multiplication]] of [[Boolean matrix|matrices with 0-1-entries]] can be utilized for performing this computation.
Using the [[Coppersmith–Winograd algorithm]] for multiplying these matrices, this gives an asymptotic worst-case running time of <math>O(n^{2.38} \cdot |G|)</math>. However, the constant term hidden by the [[Big O Notation]] is so large that the Coppersmith–Winograd algorithm is only worthwhile for matrices that are too large to handle on present-day computers {{harv|Knuth|1997}}, and this approach requires subtraction and so is only suitable for recognition. The dependence on efficient matrix multiplication cannot be avoided altogether: {{harvtxt|Lee|2002}} has proved that any parser for context-free grammars working in time <math>O(n^{3-\varepsilon} \cdot |G|)</math> can be effectively converted into an algorithm computing the product of <math>(n \times n)</math>-matrices with 0-1-entries in time <math>O(n^{3 - \varepsilon/3})</math>, and this was extended by Abboud et al.<ref>{{
==See also==
| |||