The translation power of top-down tree-to-graph transducers
Auch gedruckt in der BibliothekQAA 5/A4.92,14
FakultätFakultät für Ingenieurwissenschaften und Informatik
Ressourcen- / MedientypBericht, Text
Datum der Freischaltung2012-08-11
We introduce a new syntax-directed translation device called top-down tree-to-graph transducer. Such transducers are very similar to the usual top-down tree transducers except that the right-hand sides of their rules are hypergraphs rather than trees. Since we are aiming at a device which also allows to translate trees into objects different from graphs, we focus our attention on so-called tree-generating top-down tree-to-graph transducers. Then the result of every computation is a hypergraph which represents a tree, and in its turn the tree can be interpreted in any algebra of appropriate signature.