DocumentCode
2198450
Title
Syntax directed transduction
Author
Lewis, P.M., II ; Stearns, R.E.
fYear
1966
fDate
26-28 Oct. 1966
Firstpage
21
Lastpage
35
Abstract
A transduction is a mapping from one set of sequences to another. A syntax directed transduction is a particular type of transduction which is defined on the grammar of a context free language and which is meant to be a model of part of the translation process used in many compilers. The transduction is considered from an automata theory viewpoint as specifying the input-output relation of a machine. There is a close relationship between a subclass of these transductions, the simple syntax directed transductions, and push-down machines. This relationship is investigated in detail and conditions for such transductions to be performed on push-down machines are obtained. In addition, some time bounds for transductions on Turing machines are derived.
Keywords
Automata; Context modeling; Dictionaries; Iron; Production; Transducers; Turing machines; Writing;
fLanguage
English
Publisher
ieee
Conference_Titel
Switching and Automata Theory, 1966., IEEE Conference Record of Seventh Annual Symposium on
Conference_Location
Berkeley, CA, USA
ISSN
0272-4847
Type
conf
DOI
10.1109/SWAT.1966.26
Filename
4569518
Link To Document