Pushdown machines for the macro tree transducer

Joost Engelfriet, Heiko Vogler

Research output: Contribution to journalArticleAcademic

50 Citations (Scopus)
135 Downloads (Pure)


The macro tree transducer can be considered as a system of recursive function procedures with parameters, where the recursion is on a tree (e.g., the syntax tree of a program). We investigate characterizations of the class of tree (tree-to-string) translations which is induced by macro tree transducers (macro tree-to-string transducers, respectively). For this purpose we define several pushdown machines of which the control is recursive without parameters, or even iterative, and which work on a generalized pushdown as storage. Because of the relevance for semantics of programming languages, we stress (besides the nondeterministic case) the study of machines for the total deterministic macro tree(-to-string) transducer, which translates every input tree into exactly one output tree (string, respectively). Finally, we characterize the n-fold composition of total deterministic macro tree transducers by recursive pushdown machines with an iterated pushdown as storage, which is a pushdown of pushdowns of … of pushdowns.
Original languageEnglish
Pages (from-to)251-368
JournalTheoretical computer science
Publication statusPublished - 1986


Dive into the research topics of 'Pushdown machines for the macro tree transducer'. Together they form a unique fingerprint.

Cite this