{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,13]],"date-time":"2026-01-13T00:04:26Z","timestamp":1768262666339,"version":"3.49.0"},"reference-count":40,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[1994,4,1]],"date-time":"1994-04-01T00:00:00Z","timestamp":765158400000},"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":[[1994,4]]},"DOI":"10.1007\/bf01178511","type":"journal-article","created":{"date-parts":[[2005,2,17]],"date-time":"2005-02-17T16:58:01Z","timestamp":1108659481000},"page":"341-378","source":"Crossref","is-referenced-by-count":13,"title":["Context-free graph languages of bounded degree are generated by apex graph grammars"],"prefix":"10.1007","volume":"31","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"}]},{"given":"George","family":"Leih","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"CR1","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. Systems Theory20, 83?127 (1987)","journal-title":"Math. Systems Theory"},{"key":"CR2","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-663-09367-1","volume-title":"Transductions and context-free languages","author":"J. Berstel","year":"1979","unstructured":"[Ber] Berstel, J.: Transductions and context-free languages. Stuttgart: Teubner 1979"},{"key":"CR3","series-title":"Lect. Notes Comput. Sci.","doi-asserted-by":"crossref","first-page":"227","DOI":"10.1007\/BFb0035847","volume-title":"Proceedings STACS 88","author":"F.J. Brandenburg","year":"1988","unstructured":"[Bra88] Brandenburg, F.J.: On polynomial time graph grammars. Proceedings STACS 88 (Lect. Notes Comput. Sci., vol. 294, pp. 227?236) Berlin, Heidelberg, New York: Springer 1988"},{"key":"CR4","series-title":"Lect. Notes Comput. Sci.","doi-asserted-by":"crossref","first-page":"312","DOI":"10.1007\/3-540-53904-2_106","volume-title":"Rewriting techniques and applications","author":"F.J. Brandenburg","year":"1991","unstructured":"[Bra91] Brandenburg, F.J.: The equivalence of boundary and confluent graph grammars on graph languages of bounded degree. In: Book, R.V. (ed.) Rewriting techniques and applications (Lect. Notes Comput. Sci., vol. 488, pp. 312?322) Berlin, Heidelberg, New York: Springer 1991"},{"key":"CR5","doi-asserted-by":"crossref","first-page":"141","DOI":"10.1016\/0304-3975(87)90102-2","volume":"55","author":"B. Courcelle","year":"1987","unstructured":"[Cou87] 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":"CR6","first-page":"83","volume-title":"Programming of future generation computers II","author":"B. Courcelle","year":"1988","unstructured":"[Cou88] 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":"CR7","doi-asserted-by":"crossref","first-page":"12","DOI":"10.1016\/0890-5401(90)90043-H","volume":"85","author":"B. Courcelle","year":"1990","unstructured":"[Cou90] 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":"CR8","volume-title":"On the structure of context-free sets of graphs generated by vertex replacement","author":"B. Courcelle","year":"1991","unstructured":"[Cou91] Courcelle, B.: On the structure of context-free sets of graphs generated by vertex replacement. Report 91-44, University of Bordeaux, France, December 1991."},{"key":"CR9","volume-title":"A logical characterization of the sets of hypergraphs defined by hyperedge replacement grammars","author":"B. Courcelle","year":"1991","unstructured":"[CouEng] Courcelle, B., Engelfriet, J.: A logical characterization of the sets of hypergraphs defined by hyperedge replacement grammars. Report 91-41, University of Bordeaux, France, June 1991"},{"key":"CR10","doi-asserted-by":"crossref","first-page":"211","DOI":"10.1016\/0304-3975(84)90135-X","volume":"31","author":"A. Ehrenfeucht","year":"1984","unstructured":"[EhrMaiRoz] Ehrenfeucht, A., Main, M.G., Rozenberg, G.: Restrictions on NLC grammars. Theor. Comput. Sci.31, 211?223 (1984)","journal-title":"Theor. Comput. Sci."},{"key":"CR11","series-title":"Lect. Notes Comput. Sci.","doi-asserted-by":"crossref","first-page":"148","DOI":"10.1007\/3-540-51498-8_15","volume-title":"Proceedings FCT'89","author":"J. Engelfriet","year":"1989","unstructured":"[Eng89] Engelfriet, J.: Context-free NCE graph grammars. Proceedings FCT'89 (Lect. Notes Comput. Sci., vol. 380, pp. 148?161) Berlin, Heidelberg, New York: Springer 1989"},{"key":"CR12","series-title":"Lect. Notes Comput. Sci.","doi-asserted-by":"crossref","first-page":"311","DOI":"10.1007\/BFb0017397","volume-title":"Graph-grammars and their application to computer science","author":"J. Engelfriet","year":"1991","unstructured":"[Eng91] Engelfriet, J.: A characterization of context-free NCE graph languages by monadic second-order logic on trees. In: Ehrig, H., Kreowski, H.-J., Rozenberg, G., Rosenfeld, A. (eds.) Graph-grammars and their application to computer science (Lect. Notes Comput. Sci., vol. 532, pp. 311?327) Berlin, Heidelberg, New York: Springer 1991"},{"key":"CR13","series-title":"Lect. Notes Comput. Sci.","doi-asserted-by":"crossref","first-page":"138","DOI":"10.1007\/3-540-55719-9_70","volume-title":"ICALP'92 Proceedings","author":"J. Engelfriet","year":"1992","unstructured":"[Eng92] Engelfriet, J.: A Greibach Normal Form for context-free graph grammars. In: Kuich, W. (ed.) ICALP'92 Proceedings (Lect. Notes Comput. Sci., vol. 623, pp. 138?149) Berlin, Heidelberg, New York: Springer 1992"},{"key":"CR14","doi-asserted-by":"crossref","first-page":"328","DOI":"10.1016\/0022-0000(91)90018-Z","volume":"43","author":"J. Engelfriet","year":"1991","unstructured":"[EngHey91a] Engelfriet, J., Heyker, L.M.: The string generating power of context-free hypergraph grammars. J. Comput. System Sci.43, 328?360 (1991)","journal-title":"J. Comput. System Sci."},{"key":"CR15","unstructured":"[EngHey91b] Engelfriet, J., Heyker, L.M.: Hypergraph languages of bounded degree. Report 91-01, University of Leiden, January 1991."},{"key":"CR16","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1007\/BF01178504","volume":"29","author":"J. Engelfriet","year":"1992","unstructured":"[EngHey92] Engelfriet, J., Heyker, L.M.: Context-free hypergraph grammars have the same term-generating power as attribute grammars. Acta Inf.29, 161?210 (1992)","journal-title":"Acta Inf."},{"key":"CR17","doi-asserted-by":"crossref","first-page":"88","DOI":"10.1016\/0890-5401(89)90030-8","volume":"81","author":"J. Engelfriet","year":"1989","unstructured":"[EngLei] Engelfriet, J., Leih, G.: Linear graph grammars: power and complexity. Inf. Comput.81, 88?121 (1989)","journal-title":"Inf. Comput."},{"key":"CR18","series-title":"Lect. Notes Comput. Sci.","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1007\/3-540-18771-5_52","volume-title":"Graph-grammars and their application to computer science","author":"J. Engelfriet","year":"1987","unstructured":"[EngLeiRoz87] Engelfriet, J., Leih, G., Rozenberg, G.: Apex graph grammars. In: Ehrig, H., Nagl, M., Rozenberg, G., Rosenfeld, A. (eds.) Graph-grammars and their application to computer science (Lect. Notes Comput. Sci., vol. 291, pp. 167?185) Berlin, Heidelberg, New York: Springer 1987"},{"key":"CR19","doi-asserted-by":"crossref","first-page":"537","DOI":"10.1007\/BF00279953","volume":"25","author":"J. Engelfriet","year":"1988","unstructured":"[EngLeiRoz88] Engelfriet, J., Leih, G., Rozenberg, G.: Apex graph grammars and attribute grammars. Acta Inf.25, 537?571 (1988)","journal-title":"Acta Inf."},{"key":"CR20","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1016\/0304-3975(91)90174-Z","volume":"82","author":"J. Engelfriet","year":"1991","unstructured":"[EngLeiRoz91] Engelfriet, J., Leih, G., Rozenberg, G.: Nonterminal separation in graph grammars. Theor. Comput. Sci.82, 95?111 (1991)","journal-title":"Theor. Comput. Sci."},{"key":"CR21","doi-asserted-by":"crossref","first-page":"307","DOI":"10.1016\/0022-0000(90)90002-3","volume":"40","author":"J. Engelfriet","year":"1990","unstructured":"[EngLeiWel] Engelfriet, J., Leih, G., Welzl, E.: Boundary graph grammars with dynamic edge relabeling. J. Comput. System Sci.40, 307?345 (1990)","journal-title":"J. Comput. System Sci."},{"key":"CR22","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1016\/0890-5401(90)90038-J","volume":"84","author":"J. Engelfriet","year":"1990","unstructured":"[EngRoz90] 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":"CR23","series-title":"Lect. Notes Comput. Sci.","doi-asserted-by":"crossref","first-page":"12","DOI":"10.1007\/BFb0017374","volume-title":"Graph-grammars and their application to computer science","author":"J. Engelfriet","year":"1991","unstructured":"[EngRoz91] Engelfriet, J., Rozenberg, G.: Graph grammars based on node rewriting: an introduction to NLC graph grammars. In: Ehrig, H., Kreowski, H.-J., Rozenberg, G., Rosenfeld, A. (eds.) Graph-grammars and their application to computer science (Lect. Notes Comput. Sci., vol. 532, pp. 12?23) Berlin, Heidelberg, New York: Springer 1991"},{"key":"CR24","doi-asserted-by":"crossref","first-page":"429","DOI":"10.1137\/0304034","volume":"4","author":"S. Ginsburg","year":"1966","unstructured":"[GinSpa66] Ginsburg, S., Spanier, E.H.: Finite-turn pushdown automata. SIAM J. Control4, 429?453 (1966).","journal-title":"SIAM J. Control"},{"key":"CR25","doi-asserted-by":"crossref","first-page":"228","DOI":"10.1016\/S0022-0000(68)80009-1","volume":"2","author":"S. Ginsburg","year":"1968","unstructured":"[GinSpa68] Ginsburg, S., Spanier, E.H.: Derivation bounded languages. J. Comput. System Sci.2, 228?250 (1968)","journal-title":"J. Comput. System Sci."},{"key":"CR26","doi-asserted-by":"crossref","first-page":"42","DOI":"10.1145\/321250.321254","volume":"12","author":"S.A. Greibach","year":"1965","unstructured":"[Gre] Greibach, S.A.: A new normal-form theorem for context-free phrase structure grammars. J. ACM12, 42?52 (1965)","journal-title":"J. ACM"},{"key":"CR27","series-title":"Lect. Notes Comput. Sci.","volume-title":"Hyperedge replacement: grammars and languages","author":"A. Habel","year":"1992","unstructured":"[Hab] Habel, A.: Hyperedge replacement: grammars and languages (Lect. Notes Comput. Sci., vol. 643) Berlin, Heidelberg, New York: Springer 1992"},{"key":"CR28","series-title":"Lect. Notes Comput. Sci.","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1007\/BFb0039608","volume-title":"Proceedings STACS '87","author":"A. Habel","year":"1987","unstructured":"[HabKre87a] Habel, A., Kreowski, H.-J.: Some structural aspects of hypergraph languages generated by hyperedge replacement. Proceedings STACS '87 (Lect. Notes Comput. Sci., vol. 247, pp. 207?219) Berlin Heidelberg, New York: Springer 1987"},{"key":"CR29","series-title":"Lect. Notes Comput. Sci.","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1007\/3-540-18771-5_41","volume-title":"Graph-grammars and their application to computer science","author":"A. Habel","year":"1987","unstructured":"[HabKre87b] Habel, A., Kreowski, H.-J.: May we introduce to you: hyperedge replacement. In: Ehrig, H., Nagl, M., Rozenberg, G., Rosenfeld, A. (eds.) Graph-grammars and their application to computer science (Lect. Notes Comput. Sci., vol. 291, pp. 15?26) Berlin, Heidelberg, New York: Springer 1987"},{"key":"CR30","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1016\/0304-3975(90)90106-R","volume":"89","author":"A. Habel","year":"1991","unstructured":"[HabKreVog] Habel, A., Kreowski, H.-J., Vogler, W.: Decidable boundedness problems for sets of graphs generated by hyperedge-replacement. Theor. Comput. Sci.89, 33?62 (1991)","journal-title":"Theor. Comput. Sci."},{"key":"CR31","doi-asserted-by":"crossref","first-page":"415","DOI":"10.1016\/0022-0000(86)90060-7","volume":"33","author":"D. Jassens","year":"1986","unstructured":"[JanRozWel] Jassens, D., Rozenberg, G., Welzl, E.: The bounded degree problem for NLC grammars is decidable. J. Comput. System Sci.33, 415?422 (1986)","journal-title":"J. Comput. System Sci."},{"key":"CR32","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":"[Lau88a] 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":"CR33","series-title":"Lect. Notes Comput. Sci.","doi-asserted-by":"crossref","first-page":"362","DOI":"10.1007\/3-540-19488-6_128","volume-title":"ICALP '88 Proceedings","author":"C. Lautemann","year":"1988","unstructured":"[Lau88b] Lautemann, C.: Efficient algorithms on context-free graph languages. In: ICALP '88 Proceedings (Lect. Notes Comput. Sci., vol. 317, pp. 362?378) Berlin, Heidelberg, New York: Springer 1988"},{"key":"CR34","volume-title":"Tree automata, tree decomposition and hyperedge replacement","author":"C. Lautemann","year":"1990","unstructured":"[Lau90] Lautemann, C.: Tree automata, tree decomposition and hyperedge replacement. Report 2\/90, Johannes Gutenberg-Universit\u00e4t, Mainz, Germany, 1990"},{"key":"CR35","doi-asserted-by":"crossref","first-page":"368","DOI":"10.1145\/151261.151268","volume":"40","author":"T. Lengauer","year":"1993","unstructured":"[LenWan]: Lengauer, T., Wanke, E.: Efficient decision procedures for graph properties on context-free graph languages. J. ACM40, 368?393 (1993)","journal-title":"J. ACM"},{"key":"CR36","series-title":"Lect. Notes Comput. Sci.","doi-asserted-by":"crossref","first-page":"440","DOI":"10.1007\/3-540-18771-5_69","volume-title":"Graph-grammars and their application to computer science","author":"U. Montanari","year":"1987","unstructured":"[MonRos] Montanari, U., Rossi, F.: An efficient algorithm for the solution of hierarchical networks of constraints. In: Ehrig, H., Nagl, M., Rozenberg, G., Rosenfeld, A. (eds.) Graph-grammars and their application to computer science (Lect. Notes Comput. Sci., vol. 291, pp. 440?457) Berlin, Heidelberg, New York: Springer 1987"},{"key":"CR37","doi-asserted-by":"crossref","first-page":"501","DOI":"10.1145\/321406.321412","volume":"14","author":"D.J. Rosenkrantz","year":"1967","unstructured":"[Ros] Rosenkrantz, D.J.: Matrix equations and normal forms for context-free grammars. J. ACM14, 501?507 (1967)","journal-title":"J. ACM"},{"key":"CR38","doi-asserted-by":"crossref","first-page":"136","DOI":"10.1016\/S0019-9958(86)80045-6","volume":"69","author":"G. Rozenberg","year":"1986","unstructured":"[RozWel] Rozenberg, G., Welzl, E.: Boundary NLC graph grammars ? basic definitions, normal forms, and complexity. Inf. Control.69, 136?167 (1986)","journal-title":"Inf. Control."},{"key":"CR39","doi-asserted-by":"crossref","first-page":"315","DOI":"10.1016\/0304-3975(85)90173-2","volume":"40","author":"F.J. Urbanek","year":"1985","unstructured":"[Urb] Urbanek, F.J.: On Greibach normal form construction. Theor. Comput. Sci.40, 315?317 (1985)","journal-title":"Theor. Comput. Sci."},{"key":"CR40","series-title":"Lect. Notes Comput. Sci.","first-page":"78","volume-title":"Graph-theoretic concepts in computer science WG '89","author":"W. Vogler","year":"1989","unstructured":"[Vog] Vogler, W.: On hyperedge replacement and BNLC graph grammars. In: Graph-theoretic concepts in computer science WG '89 (Lect. Notes Comput. Sci., vol. 411, pp. 78?93) Berlin, Heidelberg, New York: Springer 1989"}],"container-title":["Acta Informatica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01178511.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01178511\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01178511","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,1,23]],"date-time":"2024-01-23T15:39:18Z","timestamp":1706024358000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01178511"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994,4]]},"references-count":40,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1994,4]]}},"alternative-id":["BF01178511"],"URL":"https:\/\/doi.org\/10.1007\/bf01178511","relation":{},"ISSN":["0001-5903","1432-0525"],"issn-type":[{"value":"0001-5903","type":"print"},{"value":"1432-0525","type":"electronic"}],"subject":[],"published":{"date-parts":[[1994,4]]}}}