zbMATH — the first resource for mathematics

Hypergraph languages of bounded degree. (English) Zbl 0802.68073
Summary: Two types of hypergraph rewriting grammar are considered: the well-known context-free hypergraph grammar (or CFHG grammar, also known as hyperedge replacement system or HR system) and the more recent separated handle hypergraph grammar (or S-HH grammar). It is shown that every S-HH hypergraph language of bounded (hyper-)degree can be generated by a (separated) CFHG grammar. This implies that these two types of grammar generate the same class of graph languages of bounded degree, but incomparable classes of hypergraph languages.

68Q42 Grammars and rewriting systems
68Q45 Formal languages and automata
Full Text: DOI
[1] Bauderon, M.; Courcelle, B., Graph expressions and graph rewriting, Math. systems theory, 20, 83-127, (1987) · Zbl 0641.68115
[2] Brandenburg, F.J., On polynomial time graph grammars, (), 227-236
[3] Brandenburg, F.J., The equivalence of boundary and confluent graph grammars on graph languages of bounded degree, (), 312-322
[4] Courcelle, B., An axiomatic definition of context-free rewriting and its application to NLC graph grammars, Theor. comput. sci., 55, 141-181, (1987) · Zbl 0644.68095
[5] Courcelle, B.; Engelfriet, J., A logical characterization of the sets of hypergraphs defined by hyperedge replacement grammars, Report 91-41, (1991), Bordeaux · Zbl 0830.68098
[6] Courcelle, B.; Engelfriet, J.; Rozenberg, G., Handle-rewriting hypergraph grammars, J. comput. system sci., 46, 218, (1993), Reports 90-08 and 90-09, Leiden; also Report 90-84, Bordeaux, 1990 · Zbl 0825.68446
[7] Courcelle, B.; Engelfriet, J.; Rozenberg, G., Context-free handle-rewriting hypergraph grammars, (), 253-268 · Zbl 0765.68084
[8] Engelfriet, J., Context-free NCE graph grammars, (), 148-161 · Zbl 0756.68070
[9] Engelfriet, J., A greibach normal form for context-free graph grammars, (), 138-149
[10] Engelfriet, J.; Heyker, L.M., Context-free hypergraph grammars have the same term-generating power as attribute grammars, Acta informatica, 29, 161-210, (1992) · Zbl 0769.68072
[11] Engelfriet, J.; Heyker, L.M., The string generating power of context-free hypergraph grammars, J. comput. system sci., 43, 328-360, (1991) · Zbl 0776.68075
[12] Engelfriet, J.; Leih, G., Linear graph grammars: power and complexity, Inform. comput., 81, 88-121, (1989) · Zbl 0684.68088
[13] Engelfriet, J.; Leih, G.; Rozenberg, G., Nonterminal separation in graph grammars, Theoret. comput. sci., 82, 95-111, (1991) · Zbl 0727.68059
[14] Engelfiriet, J.; Leih, G.; Welzl, E., Boundary graph grammars with dynamic edge relabeling, J. comput. system sci., 40, 307-345, (1990) · Zbl 0694.68049
[15] Engelfriet, J.; Rozenberg, G., A comparison of boundary graph grammars and context-free hypergraph grammars, Inform. comput., 84, 163-206, (1990) · Zbl 0706.68067
[16] Habel, A., Hyperedge replacement: grammars and languages, Ph.D. thesis, (1989), Bremen · Zbl 0787.68066
[17] Habel, A.; Kreowski, H.-J., Some structural aspects of hypergraph languages generated by hyperedge replacement, (), 207-219
[18] Habel, A.; Kreowski, H.-J., May we introduce to you: hyperedge replacement, (), 15-26 · Zbl 0643.68106
[19] Kaul, M., Syntaxanalyse von graphen bei präzedenz-graph-grammatiken, Ph.D. thesis, (1985), Osnabrück · Zbl 0587.68076
[20] Lautemann, C., Efficient algorithms on context-free graph languages, (), 362-378
[21] Rozenberg, G.; Welzl, E., Boundary NLC graph grammars—basic definitions, normal forms, and complexity, Inform. control, 69, 136-167, (1986) · Zbl 0608.68060
[22] Schuster, R., Graphgrammatiken und grapheinbettungen: algorithmen und komplexität, Ph.D. thesis, report MIP-8711, (1987), Passau
[23] Vogler, W., On hyperedge replacement and BNLC graph grammars, (), 78-93 · Zbl 0768.68186
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.