Machine translation decoding is accomplished by receiving as input a text segment in a source language to be translated into a target language, generating an initial translation as a current target language translation, applying one or more modification operators to the current target language translation to generate one or more modified target language translations, determining whether one or more of the modified target language translations represents an improved translation in comparison with the current target language translation, setting a modified target language translation as the current target language translation, and repeating these steps until occurrence of a termination condition. Automatically generating a tree (e.g., either a syntactic tree or a discourse tree) can be accomplished by receiving as input a tree corresponding to a source language text segment, and applying one or more decision rules to the received input to generate a tree corresponding to a target language text segment.