The generative power of delegation networks (Q897662)

The starting point of this work is a classical result by \textit{J. Mezei} and \textit{J. B. Wright} [Inf. Control 11, 3--29 (1967; Zbl 0155.34301)] by which the equational subsets of any algebra of finite type are homomorphic images of recognizable tree languages. This fact suggests a general scheme for producing subsets of a given domain: it consists of a device generating trees over some ranked alphabet and an interpretation of the symbols of the alphabet as operations on the domain. \textit{F. Drewes} [Grammatical picture generation. A tree-based approach. Berlin: Springer (2006; Zbl 1085.68177)] work on picture generation offers a good example of the use of this paradigm. A delegation network consists of a finite set of tree-generating devices that may delegate generation tasks to each other and an interpretation of the trees generated in some domain. Besides allowing several interacting tree-generators, delegation networks generalize the basic generator-interpretation systems by allowing interpretations in nondeterministic algebras and trees with parameter symbols that are interpreted as relations. A delegation network may also be viewed as an extended IO context-free tree grammar with an interpretation in a nondeterministic algebra. The workings and power of these systems are illustrated by a few picture-generating delegation networks. An operational characterization of the semantics of a delegation network is given in terms of a derivation relation that interleaves derivation and evaluation steps. The first main theorem shows that all the syntactic steps may, in fact, be performed before the semantic ones. To obtain this result, the authors consider certain hypergraphs, called jungles, instead of trees. A second Mezei-Wright-like theorem is proved for networks with deterministic primitives. The tree language generated by a delegation network depends only on the tree languages generated by its component devices, not on the devices themselves. Hence delegation networks define in a natural way an operator DEL on classes of tree languages. The delegation hierarchy studied by the authors is obtained from the class of all finite tree languages by repeated applications of DEL. They show, for example, that the delegation hierarchy is properly contained in the closure of the class of all regular tree languages under nondeterministic macro tree transducers, but that it is not contained in the IO-hierarchy. These facts yield also some decidability results for the delegation hierarchy. Furthermore, the set of paths in the trees of any tree language in the delegation hierarchy is shown to be a context-free language.