{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,13]],"date-time":"2026-01-13T07:20:30Z","timestamp":1768288830257,"version":"3.49.0"},"reference-count":36,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[1990,4,1]],"date-time":"1990-04-01T00:00:00Z","timestamp":638928000000},"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":[[1990,4]]},"DOI":"10.1007\/bf00289017","type":"journal-article","created":{"date-parts":[[2004,10,4]],"date-time":"2004-10-04T16:23:48Z","timestamp":1096907028000},"page":"399-421","source":"Crossref","is-referenced-by-count":41,"title":["The complexity of graph languages generated by hyperedge replacement"],"prefix":"10.1007","volume":"27","author":[{"given":"Clemens","family":"Lautemann","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"CR1","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1137\/0608024","volume":"8","author":"S. Arnborg","year":"1987","unstructured":"Arnborg, S., Corneil, D.G., Proskurowski, A.: Complexity of finding embeddings in a k-tree. SIAM J. Alg. Discrete Meth. 8, 277?284 (1987)","journal-title":"SIAM J. Alg. Discrete Meth."},{"key":"CR2","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1007\/BF01692060","volume":"20","author":"M. Bauderon","year":"1987","unstructured":"Bauderon, M., Courcelle, B.: Graph Expressions and graph rewriting. Math. Syst. Theory 20, 83?127 (1987)","journal-title":"Math. Syst. Theory"},{"key":"CR3","unstructured":"Bodlaender, H.: NC-algorithms for graphs with small treewidth. Report RUU-CS-88-4, Rijksuniversiteit Utrecht, vakgroep informatica, 1988"},{"key":"CR4","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1007\/3-540-18771-5_48","volume":"291","author":"F.-J. Brandenburg","year":"1987","unstructured":"Brandenburg, F.-J.: On partially ordered graph grammars. Lect. Notes Comput. Sci. 291, 99?111 (1987)","journal-title":"Lect. Notes Comput. Sci."},{"key":"CR5","doi-asserted-by":"crossref","first-page":"114","DOI":"10.1145\/322234.322243","volume":"28","author":"A.K. Chandra","year":"1981","unstructured":"Chandra, A.K., Kozen, D.C., Stockmeyer, L.J.: Alternation. J. ACM 28, 114?133 (1981)","journal-title":"J. ACM"},{"key":"CR6","doi-asserted-by":"crossref","unstructured":"Claus, V., Ehrig, H., Rozenberg, G. (eds.): Graph grammars and their application to Computer Science and Biology. Lect. Notes Comput. Sci. 73 (1979)","DOI":"10.1007\/BFb0025713"},{"key":"CR7","first-page":"99","volume":"27","author":"S.A. Cook","year":"1981","unstructured":"Cook, S.A.: Towards a complexity theory of synchronous parallel computation. L'Enseignement Math. 27, 99?124 (1981)","journal-title":"L'Enseignement Math."},{"key":"CR8","doi-asserted-by":"crossref","first-page":"141","DOI":"10.1016\/0304-3975(87)90102-2","volume":"55","author":"B. Courcelle","year":"1987","unstructured":"Courcelle, B.: An axiomatic definition of context-free rewriting and its application to NLC graph grammars. TCS 55, 141?181 (1987)","journal-title":"TCS"},{"key":"CR9","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1016\/S0019-9958(78)90528-4","volume":"37","author":"P. Della Vigna","year":"1978","unstructured":"Della Vigna, P., Ghezzi, C.: Context-free graph grammars. Inf. Control 37, 207?233 (1978)","journal-title":"Inf. Control"},{"key":"CR10","series-title":"Lect. Notes Comput. Sci., vol. 153","volume-title":"Graph grammars and their application to Computer Science","year":"1983","unstructured":"Ehrig, H., Nagl, M., Rozenberg, G. (eds.): Graph grammars and their application to Computer Science. (Lect. Notes Comput. Sci., vol. 153). Berlin Heidelberg New York: Springer 1983"},{"key":"CR11","unstructured":"Engelfriet, J. (personal communication)"},{"key":"CR12","doi-asserted-by":"crossref","unstructured":"Engelfriet, J., Leih, G.: Complexity of boundary graph languages. Report 88-07, Leiden 1988","DOI":"10.1016\/0890-5401(89)90030-8"},{"key":"CR13","unstructured":"Engelfriet, J., Rozenberg, G.: A comparison of boundary graph grammars, and context-free hypergraph grammars. Report 88-06, Leiden 1988"},{"key":"CR14","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1016\/S0020-0255(71)80008-7","volume":"3","author":"J. Feder","year":"1971","unstructured":"Feder, J.: Plex languages. Inf. Sci. 3, 225?241 (1971)","journal-title":"Inf. Sci."},{"key":"CR15","doi-asserted-by":"crossref","first-page":"175","DOI":"10.1007\/BF00289155","volume":"10","author":"R. Franck","year":"1978","unstructured":"Franck, R.: A class of linearly parsable graph grammars. Acta Inf. 10, 175?201 (1978)","journal-title":"Acta Inf."},{"key":"CR16","doi-asserted-by":"crossref","unstructured":"Habel, A.: Hyperedge replacement: Grammars and languages. Dissertation, Bremen 1989","DOI":"10.1007\/BF00288976"},{"key":"CR17","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1007\/BFb0039608","volume":"247","author":"A. Habel","year":"1987","unstructured":"Habel, A., Kreowski, H.-J.: Some structural aspects of hypergraph languages generated by hyperedge replacement. Lect. Notes Comput. Sci. 247, 207?219 (1987)","journal-title":"Lect. Notes Comput. Sci."},{"key":"CR18","doi-asserted-by":"crossref","first-page":"275","DOI":"10.1007\/3-540-50939-9_138","volume":"351","author":"A. Habel","year":"1989","unstructured":"Habel, A., Kreowski, H.-J., Vogler, W.: Decidable boundedness problems for hyperedge-replacement graph grammars. Lect. Notes Comput. Sci. 351, 275?289 (1989)","journal-title":"Lect. Notes Comput. Sci."},{"key":"CR19","first-page":"310","volume":"34","author":"J. Hromkovi?","year":"1988","unstructured":"Hromkovi?, J.: Two independent solutions of the 23-years old open problem in one year. EATCS Bull. 34, 310?313 (1988)","journal-title":"EATCS Bull."},{"key":"CR20","volume-title":"Introduction to automata theory, languages, and computation","author":"J.E. Hopcroft","year":"1979","unstructured":"Hopcroft, J.E., Ullman, J.D.: Introduction to automata theory, languages, and computation. Reading, Mass.: Addison-Wesley 1979"},{"key":"CR21","doi-asserted-by":"crossref","unstructured":"Immerman, N.: Nondeterministic space is closed under complement. TR 552, Yale University, July 1987, also in: Proc. 3rd Ann. Conf. on Structure in Complexity Theory, 1988, revised in SIAM J. Comput. 17, 935?938 (1988)","DOI":"10.1137\/0217058"},{"key":"CR22","doi-asserted-by":"crossref","first-page":"326","DOI":"10.1007\/3-540-18771-5_62","volume":"291","author":"M. Kaul","year":"1987","unstructured":"Kaul, M.: Practical applications of precedence graph grammars. Lect. Notes Comput. Sci. 291, 326?342 (1987)","journal-title":"Lect. Notes Comput. Sci."},{"key":"CR23","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1016\/0166-218X(87)90051-5","volume":"16","author":"K.-J. Lange","year":"1987","unstructured":"Lange, K.-J., Welzl, E.: String grammars with disconnection. Discrete Appl. Math. 16, 17?30 (1987)","journal-title":"Discrete Appl. Math."},{"key":"CR24","doi-asserted-by":"crossref","first-page":"28","DOI":"10.1007\/BFb0026094","volume":"299","author":"C. Lautemann","year":"1988","unstructured":"Lautemann, C.: Decomposition trees: structured graph representation and efficient algorithms. Lect. Notes Comput. Sci. 299, 28?39 (1988)","journal-title":"Lect. Notes Comput. Sci."},{"key":"CR25","doi-asserted-by":"crossref","first-page":"362","DOI":"10.1007\/3-540-19488-6_128","volume":"317","author":"C. Lautemann","year":"1988","unstructured":"Lautemann, C.: Efficient algorithms on context-free graph languages. Lect. Notes Comput. Sci. 317, 362?378 (1988)","journal-title":"Lect. Notes Comput. Sci."},{"key":"CR26","doi-asserted-by":"crossref","first-page":"650","DOI":"10.1137\/0213040","volume":"13","author":"J.Y.-T. Leung","year":"1984","unstructured":"Leung, J.Y.-T., Witthof, J., Vornberger, O.: On some variations of the bandwidth minimization problem. SIAM J. Comput. 13, 650?667 (1984)","journal-title":"SIAM J. Comput."},{"key":"CR27","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1145\/321679.321682","volume":"19","author":"T. Pavlidis","year":"1972","unstructured":"Pavlidis, T.: Linear and context-free graph grammars. J. ACM 19, 11?22 (1972)","journal-title":"J. ACM"},{"key":"CR28","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1016\/0196-6774(86)90023-4","volume":"7","author":"N. Robertson","year":"1986","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. II. Algorithmic aspects of treewidth. J. Algorithms 7, 309?322 (1986)","journal-title":"J. Algorithms"},{"key":"CR29","doi-asserted-by":"crossref","first-page":"136","DOI":"10.1016\/S0019-9958(86)80045-6","volume":"69","author":"G. Rozenberg","year":"1986","unstructured":"Rozenberg, G., Welzl, E.: Boundary NLC grammars ? basic definitions, normal forms and complexity. Inf. Control 69, 136?167 (1986)","journal-title":"Inf. Control"},{"key":"CR30","doi-asserted-by":"crossref","first-page":"218","DOI":"10.1016\/0022-0000(80)90036-7","volume":"20","author":"W.L. Ruzzo","year":"1980","unstructured":"Ruzzo, W.L.: Tree-size bounded alternation. J. Comput. Syst. Sci. 20, 218?235 (1980)","journal-title":"J. Comput. Syst. Sci."},{"key":"CR31","unstructured":"Schuster, R.: Graphgrammatiken und Grapheinbettungen: Algorithmen und Komplexit\u00e4t. Dissertation, Passau 1987"},{"key":"CR32","doi-asserted-by":"crossref","first-page":"52","DOI":"10.1016\/0020-0190(82)90086-2","volume":"14","author":"A.O. Slisenko","year":"1982","unstructured":"Slisenko, A.O.: Context-free graph grammars as a tool for describing polynomial-time subclasses of hard problems. Inf. Proc. Lett. 14, 52?56 (1982)","journal-title":"Inf. Proc. Lett."},{"key":"CR33","doi-asserted-by":"crossref","first-page":"405","DOI":"10.1145\/322077.322083","volume":"25","author":"I.H. Sudborough","year":"1978","unstructured":"Sudborough, I.H.: On the tape complexity of deterministic context-free languages. J. ACM 25, 405?414 (1978)","journal-title":"J. ACM"},{"key":"CR34","first-page":"96","volume":"33","author":"R. Szelepcs\u00e9nyi","year":"1987","unstructured":"Szelepcs\u00e9nyi, R.: The method of forcing for nondeterministic automata. EATCS Bull. 33, 96?99 (1987) (revised in Acta Inf. 26, 279?284 (1988))","journal-title":"EATCS Bull."},{"key":"CR35","doi-asserted-by":"crossref","unstructured":"Venkateswaran, H.: Properties that characterize LOGCFL. Proc. 19th ACM-STOC, pp. 141?150, 1987","DOI":"10.1145\/28395.28411"},{"key":"CR36","unstructured":"Vogler, W.: A note on hyperedge replacement and BNLC graph grammars. Preprint, M\u00fcnchen 1988"}],"container-title":["Acta Informatica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF00289017.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF00289017\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF00289017","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,3]],"date-time":"2020-04-03T07:59:25Z","timestamp":1585900765000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF00289017"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1990,4]]},"references-count":36,"journal-issue":{"issue":"5","published-print":{"date-parts":[[1990,4]]}},"alternative-id":["BF00289017"],"URL":"https:\/\/doi.org\/10.1007\/bf00289017","relation":{},"ISSN":["0001-5903","1432-0525"],"issn-type":[{"value":"0001-5903","type":"print"},{"value":"1432-0525","type":"electronic"}],"subject":[],"published":{"date-parts":[[1990,4]]}}}