Completeness of Compositional Translation

Abstract

In this paper we will show that the Rosetta interlingua approach to machine translation can be modeled as a compositional transfer translation 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.