×

zbMATH — the first resource for mathematics

A comparison of boundary graph grammars and context-free hypergraph grammars. (English) Zbl 0706.68067
The purpose of this paper is to compare the (language) generative power of context-free hypergraph grammars (CFHG) and boundary graph grammars (B-edNCE). These generative mechanisms are different in nature: edge placing versus node placing and, much more, directed hypergraphs generators versus graph generators. Some technical results are thus in order: normal forms for B-edNCE, some closure properties of B-edNCE and, of course, a definition of hypergraphs representations as graphs (and vice-versa). CFHG and B-edNCE (of bounded nonterminal degree) are shown to have the same power (as graphs, and also as hypergraphs generators). Arbitrary B-edNCE have the same hypergraph generative power as the CFHG, but, as graph generators, their power strictly increases. The paper is almost self-contained, partly because of the lack of widely accepted definitions for the studied classes of grammars.
Reviewer: C.Masalagiu

MSC:
68Q42 Grammars and rewriting systems
68Q45 Formal languages and automata
PDF BibTeX Cite
Full Text: DOI
References:
[1] Aho, A.V.; Ullman, J.D., Translations on a context-free grammar, Inform, and control, 19, 439-475, (1971) · Zbl 0244.68035
[2] Arnbord, S.; Corneil, D.G.; Proskurowski, A., Complexity of finding embeddings in a k-tree, SIAM J. algebra discrete methods, 8, 277-284, (1987) · Zbl 0611.05022
[3] Bauderon, M.; Courcelle, B., Graph expressions and graph rewritings, Math. systems theory, 20, 83-127, (1987) · Zbl 0641.68115
[4] Bodlaender, H.L., (), Report RUU-CS-86-22
[5] Brandenburg, F.J., On partially ordered graph-grammars, (), 99-111, 1987
[6] ()
[7] Cook, S.A., A taxonomy of problems with fast parallel algorithms, Inform. and control, 64, 2-22, (1985) · Zbl 0575.68045
[8] see also (Ehrig, Nagl, Rozenberg, and Rosenfeld, 1987, pp. 133-146).
[9] Courcelle, B., An axiomatic definition of context-free rewriting and its applications to NLC graph grammars, Theoret. comput. sci., 55, 1987, 141-181, (1987) · Zbl 0644.68095
[10] Courcelle, B., (), 112-132, 1987
[11] ()
[12] ()
[13] Engelfriet, J., Generating strings with hypergraph grammars, (), 43-58
[14] Engelfriet, J.; Leih, G., Complexity of boundary graph languages, (), in press · Zbl 0701.68062
[15] Engelfriet, J.; Leih, G., Linear graph grammars: power and complexity, Inform. and comput., 81, 88-121, (1989) · Zbl 0684.68088
[16] Engelfriet, J.; Leih, G.; Rozenberg, G., (), 167-185, 1987
[17] Engelfriet, J.; Leih, G.; Rozenberg, G., Apex graph grammars and attribute grammars, Acta inform., 25, 537-571, (1988) · Zbl 0659.68096
[18] Engelfriet, J.; Leih, G.; Rozenberg, G., (), Report 88-29
[19] Engelfriet, J.; Leih, G.; Welzl, E., Boundary graph grammars with dynamic edge relabeling, (), in press · Zbl 0694.68049
[20] Engelfriet, J.; Rozenberg, G.; Slutzki, G., Tree transducers, L systems, and two-way machines, J. comput. system sci., 20, 150-202, (1980) · Zbl 0426.68075
[21] Habel, A.; Kreowski, H.-J., Some structural aspects of hypergraph languages generated by hyperedge replacement, (), 207-219
[22] Habel, A.; Kreowski, H.-J., (), 15-26, 1987
[23] Janssens, D.; Rozenberg, G., On the structure of node-label-controlled graph languages, Inform. sci., 20, 191-216, (1980) · Zbl 0452.68073
[24] Janssens, D.; Rozenberg, G., Graph grammars with neighbourhood-controlled embedding, Theoret. comput. sci., 21, 55-74, (1982) · Zbl 0486.68075
[25] Janssens, D.; Rozenberg, G.; Verraedt, R., On sequential and parallel node-rewriting graph grammars, Comput. graphics image process., 18, 279-304, (1982) · Zbl 0531.68030
[26] Johnson, D.S., The NP-completeness column: an ongoing guide, J. algorithms, 6, 434-451, (1985) · Zbl 0608.68032
[27] see also (Ehrig, Nagl, Rozenberg, and Rosenfeld, 1987, pp. 326-342). · Zbl 0587.68076
[28] Lautemann, C., Efficient algorithms on context-free graph languages, (), 362-378
[29] Montanari, U.; Rossi, F., (), 440-457, 1987
[30] Rozenberg, G., (), 55-65, 1987
[31] Rozenberg, G.; Welzl, E., Boundary NLC graph grammars—basic definitions, normal forms, and complexity, Inform. and control., 69, 136-167, (1986) · Zbl 0608.68060
[32] Rozenberg, G.; Welzl, E., Graph theoretic closure properties of the family of boundary NLC graph languages, Acta inform., 23, 289-309, (1986) · Zbl 0606.68070
[33] Rozenberg, G.; Welzl, E., Combinatorial properties of boundary NLC graph languages, Discrete appl. math., 16, 59-73, (1987) · Zbl 0619.68063
[34] Schuster, R., (), Report MIP-8711
[35] Vogler, W., A note on hyperedge replacement and BNLC graph grammars, (1988), preprint, Munich
[36] Welzl, E., On the set of all subgraphs of the graphs in a boundary NLC graph language, (), 445-459
[37] Welzl, E., (), 593-609, 1987
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.