×

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
PDFBibTeX XMLCite
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., (Classes of Graphs with Bounded Tree-width (1986), University of Utrecht), Report RUU-CS-86-22
[5] Brandenburg, F. J., On partially ordered graph-grammars, (Ehrig; Nagl; Rozenberg; Rosenfeld (1987)), 99-111, 1987 · Zbl 0643.68107
[6] (Claus, V.; Ehrig, H.; Rozenberg, G., Graph-Grammars and Their Application to Computer Science and Biology. Graph-Grammars and Their Application to Computer Science and Biology, Lecture Notes in Computer Science, Vol. 73 (1979), Springer-Verlag: Springer-Verlag Berlin) · Zbl 0398.00019
[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).; 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., (Ehrig; Nagl; Rozenberg; Rosenfeld, A representation of graphs by algebraic expressions and its use for graph rewriting systems (1987)), 112-132, 1987 · Zbl 0643.68104
[11] (Ehrig, H.; Nagl, M.; Rozenberg, G.; Rosenfeld, A., Graph-Grammars and Their Application to Computer Science. Graph-Grammars and Their Application to Computer Science, Lecture Notes in Computer Science, Vol. 291 (1987), Springer-Verlag: Springer-Verlag Berlin) · Zbl 0636.00013
[12] (Ehrig, H.; Nagl, M.; Rozenberg, G., Graph-Grammars and Their Application to Computer Science. Graph-Grammars and Their Application to Computer Science, Lecture Notes in Computer Science, Vol. 153 (1983), Springer-Verlag: Springer-Verlag Berlin) · Zbl 0512.00027
[13] Engelfriet, J., Generating strings with hypergraph grammars, (Asveld, P. R.J.; Nijholt, A., Essays on Concepts, Formalisms, and Tools. Essays on Concepts, Formalisms, and Tools, CWI Tract 42 (1987), Centre for Mathematics and Computer Science: Centre for Mathematics and Computer Science Amsterdam), 43-58 · Zbl 0638.68079
[14] Engelfriet, J.; Leih, G., Complexity of Boundary Graph Languages, (Report 88-07. Report 88-07, RAIRO (1988), Institute of Applied Math. and Computer Science, University of Leiden), 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., (Ehrig; Nagl; Rozenberg; Rosenfeld, Apex graph grammars (1987)), 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., (Nonterminal Separation in Graph Grammars (1988), Institute of Applied Math. and Computer Science, University of Leiden), Report 88-29
[19] Engelfriet, J.; Leih, G.; Welzl, E., Boundary Graph Grammars with Dynamic Edge Relabeling, (Report 87-30. Report 87-30, J. Comput. System Sci. (1987), Institute of Applied Math. and Computer Science, University of Leiden), 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, (Proceedings, STACS ’87. Proceedings, STACS ’87, Lecture Notes in Computer Science, Vol. 247 (1987), Springer-Verlag: Springer-Verlag Berlin), 207-219 · Zbl 0635.68077
[22] Habel, A.; Kreowski, H.-J., (Ehrig; Nagl; Rozenberg; Rosenfeld, May we introduce to you: Hyperedge replacement (1987)), 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).; see also (Ehrig, Nagl, Rozenberg, and Rosenfeld, 1987, pp. 326-342). · Zbl 0587.68076
[28] Lautemann, C., Efficient algorithms on context-free graph languages, (Proceedings, ICALP ’88. Proceedings, ICALP ’88, Lecture Notes in Computer Science, Vol. 317 (1988), Springer-Verlag: Springer-Verlag Berlin), 362-378 · Zbl 0649.68075
[29] Montanari, U.; Rossi, F., (Ehrig; Nagl; Rozenberg; Rosenfeld, An efficient algorithm for the solution of hierarchical networks of constraints (1987)), 440-457, 1987 · Zbl 0643.68157
[30] Rozenberg, G., (Ehrig; Nagl; Rozenberg; Rosenfeld, An introduction to the NLC way of rewriting graphs (1987)), 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., (Graphgrammatiken und Grapheinbettungen: Algorithmen und Komplexität (1987), Universität Passau), 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, (Rozenberg, G.; Salomaa, A., The Book of \(L (1986)\), Springer-Verlag: Springer-Verlag Berlin), 445-459 · Zbl 0587.68074
[37] Welzl, E., (Ehrig; Nagl; Rozenberg; Rosenfeld, Boundary NLC and partition controlled graph grammars (1987)), 593-609, 1987 · Zbl 0643.68109
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.