Cubic time
Related Topics
Publications (6)

1Spectral Learning for NonDeterministic Dependency Parsinginsideoutside algorithm for the parsing model that runs in cubic time, hence maintaining the standard parsing costs for contextfree...

2The Problem of Computing the Most Probable Tree in DataOriented Parsing and Stochastic Tree Grammars1995  Rens Badfor one tree). 3.2 Disambiguation Cubic time parsing does not guarantee cubic time disambiguation, as a sentence may have...

3Nondeterministic Recursive Ascent Parsing1991  Rene LeermakersIn the general nondeterministic case, the parser has cubic time complexity if the parse functions are implemented as ...

4Generalized LeftCorner Parsing1993  MarkJan Nederhofgrammars. How the algorithm can be improved to operate in cubic time is shown in Section 5. The improved algorithm produces...

5Constraints on NonProjective Dependency Parsing2006  Joakim Nivre431–438. Jason M. Eisner. 2000. Bilexical grammars and their cubictime parsing algorithms. In Harry Bunt and Anton Nijholt, editors...

6Translation as Weighted Deduction2009  Adam Lopezis crucial for efficiency. CKY computes all parses in cubic time by reusing subparses. To parse a sentence a1...aK , we...