ISSN:
1433-0490
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
Notes:
Abstract The concept of a translation is fundamental to any theory of compiling. Formally, atranslation is any set of pairs of words. Classes of finitely describable translations are considered in general, from the point of view of balloon automata [17, 18, 19]. A translation can be defined by atransducer, a device with an input tape and an output terminal. If, with inputx, the stringy appears at the output terminal, then (x, y) is in the translation defined by the transducer. One can also define a translation by a two input taperecognizer. Ifx andy are placed on the two tapes, the recognizer tells if (x, y) is in the defined translation. One can define closed classes of transducers and recognizers by: (1) restricting the way in which infinite storage may be used (pushdown structure, stack structure, etc.), (2) allowing the finite control to be nondeterministic or deterministic, (3) allowing one way or two way motion on the input tapes. We have some results on classes of translations which can be categorized roughly into three types. (a) Translations defined by certain classes of transducers and recognizers are equivalent. (b) Translations of a given class are sometimes closed under composition and decomposition with a finite memory translation (gsm mapping). (c) A nondeterministically defined translation can be expressed as the composition of a finitely defined translation and a related deterministically defined translation in many cases. In addition, ifC is a class of translations, then one can write a compiler-compiler to render any translationT inC and only if the following question is solvable: For any translationT inC and stringx, does there exist ay such that (x, y) is inT? We shall show that, in general, the decidability of this question is equivalent to the decidability of one or more questions from automata theory, depending upon the type of devices defining the classC.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01703920
Permalink
