@article{TACL1020,
	author = {Chang, Yin-Wen  and Collins, Michael },
	title = {A Polynomial-Time Dynamic Programming Algorithm for Phrase-Based Decoding with a Fixed Distortion Limit},
	journal = {Transactions of the Association for Computational Linguistics},
	volume = {5},
	year = {2017},
	keywords = {},
	abstract = {Decoding of phrase-based translation models in the general case is known to be NP-complete, by a reduction from the traveling salesman problem (Knight, 1999). In practice, phrase-based systems often impose a hard distortion limit that limits the movement of phrases during translation. However, the impact on complexity after imposing such a constraint is not well studied. In this paper, we describe a dynamic programming algorithm for phrase-based decoding with a fixed distortion limit. The runtime of the algorithm is O(nd!lh^\{d+1\}) where n is the sentence length, d is the distortion limit, l is a bound on the number of phrases starting at any position in the sentence, and h is related to the maximum number of target language translations for any source word. The algorithm makes use of a novel representation that gives a new perspective on decoding of phrase-based models.},
	issn = {2307-387X},
	url = {https://transacl.org/ojs/index.php/tacl/article/view/1020},
	pages = {59--71}
}