Interdependent translation schemes

摘要

A translation scheme for specifying translations which depend on both syntactic (input) structure and semantic (output) structure is introduced. Such schemes are called interdependent translation schemes. The syntactic and semantic structures are assumed to be context-free, but their interaction gives rise to a contextual dependence which provides considerably more power than the usual syntax directed translation scheme. It is shown that under two forms of leftmost restriction the class of translations generated by interdependent translation schemes is equal to the class of Turing-computable relations. Length increasing schemes generate translations which are characterized by context-sensitive languages. Interdependent translation schemes which allow associations between nodes in the input and output derivation trees are introduced, and it is shown that these also generate all Turing-computable relations. Normal forms for these schemes are also defined.