Word re-ordering and DP-based search in statistical machine translation

In this paper, we describe a search procedure for statistical machine translation (MT) based on dynamic programming (DP). Starting from a DP-based solution to the traveling salesman problem, we present a novel technique to restrict the possible word reordering between source and target language in order to achieve an efficient search algorithm. A search restriction especially useful for the translation direction from German to English is presented. The experimental tests are carried out on the Verbmobil task (German-English, 8000-word vocabulary), which is a limited-domain spoken-language task.