  We present a language model consisting of a collection of costed
bidirectional finite state automata associated with the head words of phrases.
The model is suitable for incremental application of lexical associations in a
dynamic programming search for optimal dependency tree derivations. We also
present a model and algorithm for machine translation involving optimal
``tiling'' of a dependency tree with entries of a costed bilingual lexicon.
Experimental results are reported comparing methods for assigning cost
functions to these models. We conclude with a discussion of the adequacy of
annotated linguistic strings as representations for machine translation.
