{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,13]],"date-time":"2026-01-13T00:01:45Z","timestamp":1768262505911,"version":"3.49.0"},"reference-count":50,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[1992,2,1]],"date-time":"1992-02-01T00:00:00Z","timestamp":696902400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Acta Informatica"],"published-print":{"date-parts":[[1992,2]]},"DOI":"10.1007\/bf01178504","type":"journal-article","created":{"date-parts":[[2005,2,17]],"date-time":"2005-02-17T19:37:37Z","timestamp":1108669057000},"page":"161-210","source":"Crossref","is-referenced-by-count":22,"title":["Context-free hypergraph grammars have the same term-generating power as attribute grammars"],"prefix":"10.1007","volume":"29","author":[{"given":"Joost","family":"Engelfriet","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Linda","family":"Heyker","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"CR1","volume-title":"Compilers; Principles, techniques, and tools","author":"A.V. Aho","year":"1986","unstructured":"[AhoSetUll] Aho, A.V., Sethi, R., Ullman, J.D.: Compilers; Principles, techniques, and tools. Reading, MA: Addison-Wesley 1986"},{"key":"CR2","volume-title":"The theory of parsing, translation, and compiling","author":"A.V. Aho","year":"1972","unstructured":"[AhoUll] Aho, A.V., Ullman, J.D.: The theory of parsing, translation, and compiling. Englewood Cliffs, NJ: Prentice-Hall 1972"},{"key":"CR3","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1007\/BF01692060","volume":"20","author":"M. Bauderon","year":"1987","unstructured":"[BauCou] Bauderon, M., Courcelle, B.: Graph expressions and graph rewritings. Math. Syst. Theory20, 83?127 (1987)","journal-title":"Math. Syst. Theory"},{"key":"CR4","series-title":"Lect. Notes Comput. Sci.","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1007\/3-540-10854-8_5","volume-title":"Fundamentals of computation theory","author":"M. Bartha","year":"1981","unstructured":"[Bar Bartha, M.: An algebraic definition of attributed transformations. In: G\u00e9cseg, F. (ed.) Fundamentals of computation theory. (Lect. Notes Comput. Sci., vol. 117, pp. 51?60) Berlin, Heidelberg, New York: Springer 1981"},{"key":"CR5","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1145\/359997.359999","volume":"19","author":"G.V. Bochmann","year":"1976","unstructured":"[Boc] Bochmann, G.V.: Semantic evaluation from left to right. Commun. ACM19, 55?62 (1976)","journal-title":"Commun. ACM"},{"key":"CR6","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BF01744285","volume":"13","author":"L.M. Chirica","year":"1979","unstructured":"[ChiMar Chirica, L.M., Martin, D.F.: An order-algebraic definition of Knuthian semantics. Math. Syst. Theory.13, 1?27 (1979)","journal-title":"Math. Syst. Theory."},{"key":"CR7","volume-title":"On the power of context-free jungle rewriting for term rewriting systems and logic programming","author":"A. Corradini","year":"1990","unstructured":"[CorRos] Corradini, A., Rossi, F.: On the power of context-free jungle rewriting for term rewriting systems and logic programming, University of Pisa, Italy, June 1990"},{"key":"CR8","series-title":"Lect. Notes Comput. Sci.","doi-asserted-by":"crossref","first-page":"275","DOI":"10.1007\/3-540-53982-4_16","volume-title":"Proceedings CAAP '91","author":"A. Corradini","year":"1991","unstructured":"[CorRosPar Corradini, A., Rossi, F., Parisi-Presicce, F.: Logic programming as hypergraph rewriting. In: Proceedings CAAP '91. (Lect. Notes Comput. Sci., vol. 493, pp. 275?295) Berlin, Heidelberg, New York: Springer 1991"},{"key":"CR9","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0304-3975(86)90050-2","volume":"42","author":"B. Courcelle","year":"1986","unstructured":"[Cou 1] Courcelle, B.: Equivalences and transformations of regular systems, applications to recursive program schemes and grammars. Theor. Comput. Sci.42, 1?122 (1986)","journal-title":"Theor. Comput. Sci."},{"key":"CR10","doi-asserted-by":"crossref","first-page":"141","DOI":"10.1016\/0304-3975(87)90102-2","volume":"55","author":"B. Courcelle","year":"1987","unstructured":"[Cou2] Courcelle, B.: An axiomatic definition of context-free rewriting and its application to NLC graph grammars. Theor. Comput. Sci.55, 141?181 (1987)","journal-title":"Theor. Comput. Sci."},{"key":"CR11","first-page":"83","volume-title":"Programming of future generation computers II","author":"B. Courcelle","year":"1988","unstructured":"[Cou3] Courcelle, B.: On using context-free graph grammars for analyzing recursive definitions. In: Fuchi, K., Kott, L. (eds.) Programming of future generation computers II, pp. 83?122. Amsterdam: Elsevier 1988"},{"key":"CR12","doi-asserted-by":"crossref","first-page":"12","DOI":"10.1016\/0890-5401(90)90043-H","volume":"85","author":"B. Courcelle","year":"1990","unstructured":"[Cou4] Courcelle, B.: The monadic second-order logic of graphs, I: recognizable sets of finite graphs. Inf. Comput.85, 12?75 (1990)","journal-title":"Inf. Comput."},{"key":"CR13","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0890-5401(88)90002-8","volume":"78","author":"B. Courcelle","year":"1988","unstructured":"[Couder] Courcelle, B., Deransart, P.: Proofs of partial correctness for attribute grammars with applications to recursive procedures and logic programming. Inf. Comput.78, 1?55 (1988)","journal-title":"Inf. Comput."},{"issue":"163-191","key":"CR14","doi-asserted-by":"crossref","first-page":"235","DOI":"10.1016\/0304-3975(82)90024-X","volume":"17","author":"B. Courcelle","year":"1982","unstructured":"[CouFra] Courcelle, B., Franchi-Zannettacci, P.: Attribute grammars and recursive program schemes I and II. Theor. Comput. Sci.17, 163-191, 235?257 (1982)","journal-title":"Theor. Comput. Sci."},{"key":"CR15","series-title":"Lect. Notes Comput. Sci.","volume-title":"Attribute grammars; definitions, systems and bibliography.","author":"P. Deransart","year":"1988","unstructured":"[DerJouLor] Deransart, P., Jourdan, M., Lorho, B.: Attribute grammars; definitions, systems and bibliography. (Lect. Notes Comput. Sci., vol. 323) Berlin, Heidelberg, New York: Springer 1988"},{"key":"CR16","doi-asserted-by":"crossref","first-page":"119","DOI":"10.1016\/0743-1066(85)90015-9","volume":"2","author":"P. Deransart","year":"1985","unstructured":"[DerMal] Deransart, P., Maluszynski, J.: Relating logic programs and attribute grammars. J. Logic Program.2, 119?155 (1985)","journal-title":"J. Logic Program."},{"key":"CR17","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1016\/S0019-9958(77)90309-6","volume":"35","author":"J. Duske","year":"1977","unstructured":"[DusParSedSpe] Duske, J., Parchmann, R., Sedello, M., Specht, J.: IO-macrolanguages and attributed translations. Inf. Control35, 87?105 (1977)","journal-title":"Inf. Control"},{"key":"CR18","series-title":"Lect. Notes Comput. Sci.","volume-title":"Graph-grammars and their application to computer science","year":"1987","unstructured":"[EhrNagRosRoz] Ehrig, H., Nagl, M., Rozenberg, G., Rosenfeld, A. (eds.): Graph-grammars and their application to computer science. (Lect. Notes Comput. Sci., vol. 291) Berlin, Heidelberg, New York: Springer 1987"},{"key":"CR19","doi-asserted-by":"crossref","first-page":"241","DOI":"10.1016\/B978-0-12-115350-2.50014-2","volume-title":"Formal language theory: perspectives and open problems","author":"J. Engelfriet","year":"1980","unstructured":"[Eng1] Engelfriet, J.: Some open questions and recent results on tree transducers and tree languages. In: Book, R.V. (ed.). Formal language theory: perspectives and open problems, pp. 241?286. New York: Academic Press 1980"},{"key":"CR20","unstructured":"[Eng2] Engelfriet, J.: Tree transducers and syntax-directed semantics. TW Memorandum 363, Twente University of Technology, 1981, presented at the 7th CAAP, March 1982, Lille"},{"key":"CR21","doi-asserted-by":"crossref","first-page":"70","DOI":"10.1137\/0215005","volume":"15","author":"J. Engelfriet","year":"1986","unstructured":"[Eng3] Engelfriet, J.: The complexity of languages generated by attribute grammars. SIAM J. Comput.15, 70?86 (1986)","journal-title":"SIAM J. Comput."},{"key":"CR22","doi-asserted-by":"crossref","first-page":"275","DOI":"10.1007\/BF00289307","volume":"16","author":"J. Engelfriet","year":"1981","unstructured":"[EngFil] Engelfriet, J., Fil\u00e9, G.: The formal power of one visit attribute grammars. Acta Inf.16, 275?302 (1981)","journal-title":"Acta Inf."},{"key":"CR23","doi-asserted-by":"crossref","first-page":"328","DOI":"10.1016\/0022-0000(91)90018-Z","volume":"43","author":"J. Engelfriet","year":"1991","unstructured":"[EngHey1] Engelfriet, J., Heyker, L. M.: The string generating power of context-free hypergraph grammars. J. Comput. Syst. Sci.43, 328?360 (1991)","journal-title":"J. Comput. Syst. Sci."},{"key":"CR24","series-title":"Lect. Notes Comput. Sci.","doi-asserted-by":"crossref","first-page":"328","DOI":"10.1007\/BFb0017398","volume-title":"Graphgrammars and their application to computer science","author":"J. Engelfriet","year":"1991","unstructured":"[EngHey2] Engelfriet, J., Heyker, L.M.: The term generating power of context-free hypergraph grammars. In: Ehrig, H., Kreowski, H.-J., Rozenberg, G. (eds.) Graphgrammars and their application to computer science. (Lect. Notes Comput. Sci., vol. 532) Berlin, Heidelberg, New York: Springer 1991, pp. 328?343"},{"key":"CR25","doi-asserted-by":"crossref","first-page":"537","DOI":"10.1007\/BF00279953","volume":"25","author":"J. Engelfriet","year":"1988","unstructured":"[EngLeiRoz] Engelfriet, J., Leih, G., Rozenberg, G.: Apex graph grammars and attribute grammars. Acta Inf.25, 537?571 (1988)","journal-title":"Acta Inf."},{"key":"CR26","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1016\/0890-5401(90)90038-J","volume":"84","author":"J. Engelfriet","year":"1990","unstructured":"[EngRoz] Engelfriet, J., Rozenberg, G.: A comparison of boundary graph grammars and context-free hypergraph grammars. Inf. Comput.84, 163?206 (1990)","journal-title":"Inf. Comput."},{"key":"CR27","doi-asserted-by":"crossref","first-page":"71","DOI":"10.1016\/0022-0000(85)90066-2","volume":"31","author":"J. Engelfriet","year":"1985","unstructured":"[EngVog1] Engelfriet, J., Vogler, H.: Macro tree transducers. J. Comput. Syst. Sci.31, 71?146 (1985)","journal-title":"J. Comput. Syst. Sci."},{"key":"CR28","unstructured":"[EngVog2] Engelfriet, J., Vogler, H.: The translation power of top-down tree-to-graph transducers. in preparation"},{"key":"CR29","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1016\/S0020-0255(71)80008-7","volume":"3","author":"J. Feder","year":"1971","unstructured":"[Fed] Feder, J.: Plex languages. Inf. Sci.3, 225?241 (1971)","journal-title":"Plex languages. Inf. Sci."},{"key":"CR30","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1007\/BF00264472","volume":"19","author":"G. Fil\u00e8","year":"1983","unstructured":"[Fil] Fil\u00e8, G.: Interpretation and reduction of attribute grammars. Acta Inf.19, 115?150 (1983)","journal-title":"Acta Inf."},{"key":"CR31","first-page":"261","volume":"5","author":"Z. F\u00fcl\u00f6p","year":"1981","unstructured":"[F\u00fcl] F\u00fcl\u00f6p, Z.: On attributed tree transducers. Acta Cybern.5, 261?279 (1981)","journal-title":"Acta Cybern."},{"key":"CR32","series-title":"Lect. Notes Comput. Sci.","doi-asserted-by":"crossref","first-page":"132","DOI":"10.1007\/3-540-09118-1_15","volume-title":"Theoretical computer science, 4th GI Conference","author":"H. Ganzinger","year":"1979","unstructured":"[Gan] Ganzinger, H.: On storage optimization for automatically generated compilers. In: Weibrauch, K. (ed.) Theoretical computer science, 4th GI Conference. (Lect. Notes Comput. Sci., vol. 67, pp. 132?141) Berlin, Heidelberg, New York: Springer 1979"},{"key":"CR33","doi-asserted-by":"crossref","unstructured":"[G\u00f6t] G\u00f6ttler, H.: Graph-grammars and diagram editing. In [EhrNagRozRoz], pp. 216?231","DOI":"10.1007\/3-540-18771-5_55"},{"key":"CR34","unstructured":"[Hab] Habel, A.: Hyperedge replacement: grammars and languages. Ph.D. Thesis, Bremen, 1989"},{"key":"CR35","series-title":"Lect. Notes Comput. Sci.","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1007\/BFb0039608","volume-title":"STACS'87. Proceedings","author":"A. Habel","year":"1987","unstructured":"[HabKre1] Habel A., Kreowski, H.-J.: Some structral aspects of hypergraph languages generated by hyperedge replacement. In: Brandenburg, F.J., Vidal-Naquet, G., Wirsing, M. (eds.) STACS'87. Proceedings. (Lect. Notes Comput. Sci., vol. 247, pp. 207?219) Berlin, Heidelberg, New York: Springer 1987"},{"key":"CR36","doi-asserted-by":"crossref","unstructured":"[HabKre2] Habel, A., Kreowski, H.-J.: May we introduce to you: hyperedge replacement. In [EhrNagRosRoz], pp. 15?26","DOI":"10.1007\/3-540-18771-5_41"},{"key":"CR37","series-title":"Lect. Notes Comput. Sci.","first-page":"92","volume-title":"Recent trends in data type specification","author":"A. Habel","year":"1987","unstructured":"[HabKrePlu] Habel, A., Kreowski, H.-J., Plump, D.: Jungle evaluation. In: Sanella, D., Tarlecki, A. (eds.) Recent trends in data type specification. (Lect. Notes Comput. Sci., vol. 332, pp. 92?112) Berlin, Heidelberg, New York: Springer 1987"},{"key":"CR38","series-title":"Lect. Notes Comput. Sci.","doi-asserted-by":"crossref","first-page":"159","DOI":"10.1007\/BFb0000105","volume-title":"Graph-grammars and their application to computer science","author":"B. Hoffmann","year":"1983","unstructured":"[Hof] Hoffmann, B.: Modelling compiler generation by graph grammars. In: Ehrig, H., Nagl, M., Rozenberg, G. (eds.) Graph-grammars and their application to computer science. (Lect. Notes Comput. Sci., vol. 153, pp. 159?171) Berlin, Heidelberg, New York: Springer 1983"},{"key":"CR39","series-title":"Lect. Notes Comput. Sci.","doi-asserted-by":"crossref","first-page":"191","DOI":"10.1007\/3-540-50667-5_71","volume-title":"Algebraic and logic programming","author":"B. Hoffmann","year":"1988","unstructured":"[HofPlu] Hoffmann, B., Plump, D.: Jungle evaluation for efficient term rewriting. In: Grabowski, J., Lescanne, P., Wechler, W. (eds.) Algebraic and logic programming. (Lect. Notes Comput. Sci., vol. 343, pp. 191?203) Berlin, Heidelberg, New York: Springer 1988"},{"key":"CR40","series-title":"Lect. Notes Comput. Sci.","doi-asserted-by":"crossref","first-page":"275","DOI":"10.1007\/BFb0022511","volume-title":"Mathematical Foundations of Computer Science 1980","author":"B. Hoffmann","year":"1980","unstructured":"[HofSch] Hoffmann, B., Schmiedecke, I.-R.: Multi-pass parsing for two-level grammars. In: Dembinski, P. (ed.) Mathematical Foundations of Computer Science 1980. (Lect. Notes Comput. Sci., vol. 88, pp. 275?290) Berlin, Heidelberg, New York: Springer 1980"},{"key":"CR41","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1007\/BF01692511","volume":"2","author":"D.E. Knuth","year":"1968","unstructured":"[Knu] Knuth, D.E.: Semantics of context-free languages. Math. Syst. Theory2, 127?145 (1968). Correction: Math. Syst. Theory5, 95?96 (1971)","journal-title":"Math. Syst. Theory"},{"key":"CR42","doi-asserted-by":"crossref","first-page":"217","DOI":"10.1007\/978-3-642-95486-3_18","volume-title":"The Book ofL","author":"H.-J. Kreowski","year":"1986","unstructured":"[Kre] Kreowski, H.-J.: Rule trees represent derivations in edge replacement systems. In: Rozenberg, G., Salomaa, A. (eds.) The Book ofL, pp. 217?232, Berlin, Heidelberg, New York: Springer 1986"},{"key":"CR43","series-title":"Lect. Notes Comput. Sci.","doi-asserted-by":"crossref","first-page":"28","DOI":"10.1007\/BFb0026094","volume-title":"CAAP '88 Proceedings","author":"C. Lautemann","year":"1988","unstructured":"[Lau] Lautemann, C.: Decomposition trees: structured graph representation and efficient algorithms. In: Dauchet, M., Nivat, M. (eds.) CAAP '88 Proceedings. (Lect. Notes Comput. Sci., vol. 299, pp. 28?39) Berlin, Heidelberg, New York: Springer 1988"},{"key":"CR44","series-title":"Lect. Notes Comput. Sci.","doi-asserted-by":"crossref","first-page":"379","DOI":"10.1007\/3-540-19488-6_129","volume-title":"Automata languages and programming. ICALP '88 Proceedings","author":"T. Lengauer","year":"1988","unstructured":"[LenWan] Lengauer, T., Wanke, E.: Effcient analysis of graph properties on context-free graph languages (extended abstract). In: Lepist\u00f6, T., Salomaa, A. (eds.) Automata languages and programming. ICALP '88 Proceedings. (Lect. Notes Comput. Sci., vol. 317, pp. 379?393) Berlin, Heidelberg, New York: Springer 1988"},{"key":"CR45","volume-title":"Methods and tools for compiler construction","year":"1984","unstructured":"[Lor] Lorho, B. (ed.): Methods and tools for compiler construction. New York: Cambridge University Press 1984"},{"key":"CR46","series-title":"Lect. Notes Comput. Sci.","doi-asserted-by":"crossref","first-page":"259","DOI":"10.1007\/3-540-10250-7_25","volume-title":"Semantics-directed compiler generation","author":"O.L. Madsen","year":"1980","unstructured":"[Mad] Madsen, O.L. on defining semantics by means of extended attribute grammars. In: Jones, N.D. (ed.) Semantics-directed compiler generation. (Lect. Notes Comput. Sci., vol. 94, pp. 259?299) Berlin, Heidelberg, New York: Springer 1980"},{"key":"CR47","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1016\/S0019-9958(67)90353-1","volume":"11","author":"J. Mezei","year":"1967","unstructured":"[MezWri] Mezei, J., Wright, J.B.: Algebraic automata and context-free sets. Inf. Control11, 3?29 (1967)","journal-title":"Inf. Control"},{"key":"CR48","doi-asserted-by":"crossref","unstructured":"[MonRos] Montanari, U., Rossi, F.: An efficient algorithm for the solution of hierarchical networks of constraints. In: [EhrNagRosRoz], pp. 440?457","DOI":"10.1007\/3-540-18771-5_69"},{"key":"CR49","doi-asserted-by":"crossref","first-page":"560","DOI":"10.1016\/S0022-0000(71)80016-8","volume":"5","author":"T.W. Pratt","year":"1971","unstructured":"[Pra] Pratt, T.W.: Pair grammars, graph languages and string-to-graph translations. J. Comput. Syst. Sci.5, 560?595 (1971)","journal-title":"J. Comput. Syst. Sci."},{"key":"CR50","volume-title":"Algebraic sets of tree-vectors and rational tree-transductions","author":"J.-C. Raoult","year":"1989","unstructured":"[Rao] Raoult, J.-C.: Algebraic sets of tree-vectors and rational tree-transductions. Publication Nr. 502, IRISA, Rennes, France, 1989"}],"container-title":["Acta Informatica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01178504.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01178504\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01178504","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,1,23]],"date-time":"2024-01-23T15:49:41Z","timestamp":1706024981000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01178504"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1992,2]]},"references-count":50,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1992,2]]}},"alternative-id":["BF01178504"],"URL":"https:\/\/doi.org\/10.1007\/bf01178504","relation":{},"ISSN":["0001-5903","1432-0525"],"issn-type":[{"value":"0001-5903","type":"print"},{"value":"1432-0525","type":"electronic"}],"subject":[],"published":{"date-parts":[[1992,2]]}}}