×

zbMATH — the first resource for mathematics

The generative power of delegation networks. (English) Zbl 1337.68152
The starting point of this work is a classical result by J. Mezei and 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. 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.
MSC:
68Q45 Formal languages and automata
68Q42 Grammars and rewriting systems
68Q70 Algebraic theory of languages and automata
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Arbib, M. A.; Give’on, Y., Algebra automata I: parallel programming as a prolegomena to the categorical approach, Inf. Control, 12, 331-345, (1968) · Zbl 0164.32201
[2] Asveld, P. R., Iterated context-independent rewriting - an algebraic approach to families of languages, (1978), Univ. of Twente, PhD thesis
[3] Bauderon, M.; Courcelle, B., Graph expressions and graph rewriting, Math. Syst. Theory, 20, 83-127, (1987) · Zbl 0641.68115
[4] Comon, H.; Dauchet, M.; Gilleron, R.; Jacquemard, F.; Lugiez, D.; Tison, S.; Tommasi, M., Tree automata techniques and applications, (2002), internet publication available at
[5] Corradini, A.; Rossi, F., Hyperedge replacement jungle rewriting for term-rewriting systems and logic programming, Theor. Comput. Sci., 109, 7-48, (1993) · Zbl 0781.68074
[6] Courcelle, B.; Engelfriet, J., Graph structure and monadic second-order logic - A language-theoretic approach, (2012), Cambridge University Press · Zbl 1257.68006
[7] Damm, W., The IO- and OI-hierarchies, Theor. Comput. Sci., 20, 95-208, (1982) · Zbl 0478.68012
[8] Drewes, F., Tree-based picture generation, Theor. Comput. Sci., 246, 1-51, (2000) · Zbl 0949.68148
[9] Drewes, F., Tree-based generation of languages of fractals, Theor. Comput. Sci., 262, 377-414, (2001) · Zbl 0983.68100
[10] Drewes, F., Grammatical picture generation - A tree-based approach, Texts in Theoretical Computer Science. An EATCS Series, (2006), Springer · Zbl 1085.68177
[11] Drewes, F., Delegation networks, (2007), Umeå University, Report UMINF 07.04 · Zbl 1148.68397
[12] Drewes, F., From tree-based generation to delegation networks, (Bozapalidis, S.; Rahonis, G., Proc. 2nd Intl. Conf. on Algebraic Informatics, CAI’07, Lecture Notes in Computer Science, vol. 4728, (2007), Springer), 48-72 · Zbl 1148.68397
[13] Drewes, F.; Engelfriet, J., Decidability of the finiteness of ranges of tree transductions, Inf. Comput., 145, 1-50, (1998) · Zbl 1034.68525
[14] Drewes, F.; Habel, A.; Kreowski, H.-J., Hyperedge replacement graph grammars, (Rozenberg, G., Handbook of Graph Grammars and Computing by Graph Transformation, vol. 1: Foundations, (1997), World Scientific Singapore), 95-162, Chap. 2
[15] Drewes, F.; Klempien-Hinrichs, R., Treebag, (Yu, S.; Păun, A., Proceedings of the 5th Intl. Conf. on Implementation and Application of Automata, CIAA’00, Lecture Notes in Computer Science, vol. 2088, (2001), Springer), 329-330 · Zbl 0989.68568
[16] Drewes, F.; Knirsch, P., Treebag - a short presentation, (Nagl, M.; Schürr, A., Proceedings of the Applications of Graph Transformation with Industrial Relevance, AGTIVE’99, Lecture Notes in Computer Science, vol. 1779, (2000), Springer), 411-417
[17] Engelfriet, J., Context-free graph grammars, (Rozenberg, G.; Salomaa, A., Handbook of Formal Languages, vol. 3: Beyond Words, (1997), Springer), 125-213, Chap. 3
[18] Engelfriet, J.; Heyker, L., Context-free hypergraph grammars have the same term-generating power as attribute grammars, Acta Inform., 29, 161-210, (1992) · Zbl 0769.68072
[19] Engelfriet, J.; Maneth, S., Output string languages of compositions of macro tree transducers, J. Comput. Syst. Sci., 64, 350-395, (2002) · Zbl 1013.68124
[20] Engelfriet, J.; Rozenberg, G.; Slutzki, G., Tree transducers, L systems, and two-way machines, J. Comput. Syst. Sci., 20, 150-202, (1980) · Zbl 0426.68075
[21] Engelfriet, J.; Schmidt, E. M., IO and OI. I, J. Comput. Syst. Sci., 15, 328-353, (1977) · Zbl 0366.68053
[22] Engelfriet, J.; Schmidt, E. M., IO and OI. II, J. Comput. Syst. Sci., 16, 67-99, (1978) · Zbl 0371.68020
[23] Engelfriet, J.; Slutzki, G., Bounded nesting in macro grammars, Inf. Control, 42, 157-193, (1979) · Zbl 0453.68051
[24] Engelfriet, J.; Vogler, H., Macro tree transducers, J. Comput. Syst. Sci., 31, 71-146, (1985) · Zbl 0588.68039
[25] Engelfriet, J.; Vogler, H., The translation power of top-down tree-to-graph transducers, J. Comput. Syst. Sci., 49, 258-305, (1994) · Zbl 0821.68078
[26] Fischer, M. J., Grammars with macro-like productions, (1968), Harvard University, Doctoral dissertation
[27] Fülöp, Z.; Vogler, H., Syntax-directed semantics: formal models based on tree transducers, (1998), Springer · Zbl 0913.68127
[28] Fülöp, Z.; Vogler, H., Weighted tree automata and tree transducers, (Kuich, W.; Droste, M.; Vogler, H., Handbook of Weighted Automata, (2009), Springer), 313-403, Chap. 9
[29] Gécseg, F.; Steinby, M., Tree automata, (1984), Akadémiai Kiadó Budapest · Zbl 0396.68041
[30] Gécseg, F.; Steinby, M., Tree languages, (Rozenberg, G.; Salomaa, A., Handbook of Formal Languages, vol. 3: Beyond Words, (1997), Springer), 1-68, Chap. 1
[31] Habel, A., Hyperedge replacement: grammars and languages, Lecture Notes in Computer Science, vol. 643, (1992), Springer · Zbl 0787.68066
[32] Habel, A.; Kreowski, H.-J., May we introduce to you: hyperedge replacement, (Proceedings of the Third Intl. Workshop on Graph Grammars and Their Application to Computer Science, Lecture Notes in Computer Science, vol. 291, (1987), Springer), 15-26 · Zbl 0643.68106
[33] Habel, A.; Kreowski, H.-J.; Plump, D., Jungle evaluation, Fundam. Inform., 15, 37-60, (1991) · Zbl 0706.68069
[34] Hoffmann, B.; Plump, D., Implementing term rewriting by jungle evaluation, RAIRO Theor. Inform. Appl., (1991) · Zbl 0706.68061
[35] Kepser, S.; Mönnich, U., Closure properties of linear context-free tree languages with an application to optimality theory, Theor. Comput. Sci., 354, 82-97, (2006) · Zbl 1088.68081
[36] Kepser, S.; Rogers, J., The equivalence of tree adjoining grammars and monadic linear context-free tree grammars, J. Log. Lang. Inf., 20, 361-384, (2011) · Zbl 1274.68151
[37] van Leeuwen, J., A generalisation of Parikh’s theorem in formal language theory, (Loeckx, J., Proc. 2nd Intl. Coll. on Automata, Languages, and Programming, ICALP 1974, Lecture Notes in Computer Science, vol. 14, (1974), Springer), 17-26 · Zbl 0297.68062
[38] Lohrey, M.; Maneth, S.; Schmidt-Schausz, M., Parameter reduction and automata evaluation for grammar-compressed trees, J. Comput. Syst. Sci., 78, 1651-1669, (2012) · Zbl 1246.68114
[39] Maibaum, T. S.E., A generalized approach to formal languages, J. Comput. Syst. Sci., 8, 409-502, (1974) · Zbl 0361.68113
[40] Maletti, A.; Engelfriet, J., Strong lexicalization of tree adjoining grammars, (Proc. 50th Annual Meeting of the Association for Computational Linguistics, ACL 2012, (2012)), 506-515, available from
[41] Mezei, J.; Wright, J. B., Algebraic automata and context-free sets, Inf. Control, 11, 3-29, (1967) · Zbl 0155.34301
[42] (Nivat, M.; Podelski, A., Tree Automata and Languages, (1992), Elsevier Amsterdam) · Zbl 0781.00007
[43] Plump, D., Term graph rewriting, (Ehrig, H.; Engels, G.; Kreowski, H.-J.; Rozenberg, G., Handbook of Graph Grammars and Computing by Graph Transformation, vol. II: Applications, Languages, and Tools, (1999), World Scientific Singapore), 3-61, Chap. 1, available also from
[44] Rayward-Smith, V. J., Hypergrammars: an extension of macrogrammars, J. Comput. Syst. Sci., 14, 130-149, (1977) · Zbl 0348.68045
[45] Schwencke, D., A category theoretic view of nondeterministic recursive program schemes, (Bezem, M., Proc. 20th Conf. on Computer Science Logic, CSL 2011, (2011)), 496-511, available from · Zbl 1247.68062
[46] Stamer, H.; Otto, F., Restarting tree automata and linear context-free tree languages, (Bozapalidis, S.; Rahonis, G., Proc. 2nd Intl. Conf. on Algebraic Informatics, CAI’07, Lecture Notes in Computer Science, vol. 4728, (2007)), 275-289 · Zbl 1148.68403
[47] Tarski, A., A lattice-theoretical fixpoint theorem and its applications, Pac. J. Math., 5, 285-309, (1955) · Zbl 0064.26004
[48] Thatcher, J. W., Tree automata: an informal survey, (Aho, A., Currents in the Theory of Computing, (1973), Prentice Hall Englewood Cliffs, NJ), 143-172
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.