Modular tree transducers (Q807012)

A new type of term rewriting system, the modular tree transducer (MTT), is introduced as a formal computational model of nested simultaneous primitive recursion on trees. The rules of an MTT are partitioned into numbered modules. These numbers establish the calling structure of the MTT; the module number \(i\) may call only modules with numbers not less than \(i\). It is shown that MTTs compute (almost) exactly the primitive recursive functions on trees, and that one gets a strict hierarchy of tree transduction classes when a increasing number of modules is allowed. The modular tree transducers are natural extensions of macro tree transducers. In fact, the authors prove that by suitably restricting the calling structure, one obtains from the MTTs with \(n\) modules the \(n\)-fold compositions of macro tree transductions (\(n\geq 1)\). The presentation is exemplary in its clarity, the new concepts are carefully motivated, and the important constructions are illustrated by good examples.