Skip to content
Show report in:

UMINF 12.15

The Generative Power of Delegation Networks

A device that generates trees over a ranked alphabet ∑, together with an interpretation of the symbols in ∑ as functions or relations on a domain A, generates subsets of A. This concept of tree-based generators is well known and essentially already present in the seminal paper by Mezei and Wright from 1967. A delegation network is a system consisting of a finite set of such generators that can "delegate" parts of the generation process to each other. It can be viewed as consisting of an (extended) IO context-free tree grammar and an interpretation. We investigate the language-theoretic properties of these systems and establish several characterizations of the generated languages. In particular, we obtain results in the style of Mezei and Wright. We also study the hierarchy of tree language classes obtained by iterating the concept of delegation, and show that this hierarchy is properly contained in the closure of the regular tree languages under nondeterministic macro tree transductions, but not in the IO-hierarchy.


No keywords specified


Frank Drewes and Joost Engelfriet

Back Edit this report
Entry responsible: Frank Drewes

Page Responsible: Frank Drewes