Hi all, In the Moses manual and also in SMT textbooks it is mentioned that the decoding complexity for PB-SMT is exponential in the source sentence length. If we have a source sentence with length n, in decoding by hypothesis expansion, we have power(2,n) state, each of them can be reordered in n! orders, and each state can be translated in power(T,n), where T is the number of translation options, right? so the decoder complexity is power(2,n)*n!*power(T,n), so why its mentioned that the complexity is exponential?
Could someone please explain for me how the decoder complexity is calculated? I've read the Knight(1999) paper, but I couldn't understand it. Could you please introduce another reference? Thanks
_______________________________________________ Moses-support mailing list Moses-support@mit.edu http://mailman.mit.edu/mailman/listinfo/moses-support