Completeness of compositional translation
In this paper we will show that the Rosetta interlingua approach to machine translation can be
modeled as a compositional transfer system in which the grammars of the source language and the target language
are generated many-sorted algebras and transfer is a set-valued homomorphism from the term algebra of the former
to the term algebra of the latter. On the basis of this algebraic formalisation we are able to prove a result
concerning the completeness of translation systems in this framework: we will prove that one can effectively
compute a function from which the answer to the question whether the system produces at least one grammatical
target-language translation for each expression in the source language can be read off directly.
Herman Hendriks and Willem-Olaf Huijsen