Whenever it is possible, binarization of LCFRS rules, or reduction of rank to two, is therefore important for parsing, as it reduces the time complexity needed for dynamic programming.

Gildea (2010) presents a related method for bina-rizing rules while keeping the time complexity of parsing as small as possible.

Binarization turns out to be possible with no penalty in time complexity, but, again, the factorization algorithm is exponential in the resulting time complexity .

It can also be shown that, if a partial parse having fanout f is obtained by means of the combination of two partial parses with fanout f1 and f2, respectively, the resulting time complexity will be O(|w|f+f1+f2) (Seki et al., 1991; Gildea, 2010).

AS an example, in the case of parsing based on CFGS, nonterminals as well as partial parses all have fanout one, resulting in the standard time complexity of O(|w|3) of dynamic programming methods.

When parsing with TAGS, we have to manipulate objects with fanout two (in the worst case), resulting in time complexity of O(|w|6).

The composite language model has been trained by performing a convergent N -best list approximate EM algorithm that has linear time complexity and a followup EM algorithm to improve word prediction power on corpora with up to a billion tokens and stored on a supercomputer.

They derived a generalized inside-outside algorithm to train the composite language model from a general EM (Dempster et al., 1977) by following Je-linek’s ingenious definition of the inside and outside probabilities for SLM (J elinek, 2004) with 6th order of sentence length time complexity .

Instead of using the 6th order generalized inside-outside algorithm proposed in (Wang et al., 2006), we train this composite model by a convergent N-best list approximate EM algorithm that has linear time complexity and a followup EM algorithm to improve word prediction power.