×

Boundary graph grammars with dynamic edge relabeling. (English) Zbl 0694.68049

Summary: Most NLC-like graph grammars generate node-labeled graphs. As one of the exceptions, eNCE graph grammars generate graphs with edge labels as well. We investigate this type of graph grammar and show that the use of edge labels (together with the NCE feature) is responsible for some new properties. Especially boundary eNCE (B-eNCE) grammars are considered. First, although eNCE grammars have the context-sensitive feature of “blocking edges”, we show that B-eNCE grammars do not. Second, we show the existence of a Chomsky normal form and a Greibach normal for B-eNCE grammars. Third, the boundary eNCE languages are characterized in terms of regular tree and string languages. Fourth, we prove that the class of (boundary) eNCE languages properly contains the closure of the class of (boundary) NLC languages under node relabelings. Analogous results are shown for linear eNCE grammars.

MSC:

68Q45 Formal languages and automata
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Berstel, J., Transductions and Context-free Languages (1979), Teubner: Teubner Stuttgart · Zbl 0424.68040
[2] F. J. Brandenburg, On partially ordered graph-grammars, in [EhrNagRozRos], pp. 99-111.; F. J. Brandenburg, On partially ordered graph-grammars, in [EhrNagRozRos], pp. 99-111. · Zbl 0643.68107
[3] Courcelle, B., An axiomatic definition of context-free rewriting and its application to NLC graph grammars, Theoret. Comput. Sci., 55, 141-182 (1988) · Zbl 0644.68095
[4] Ehrenfeucht, A.; Main, M. G.; Rozenberg, G., Restrictions on NLC graph grammars, Theoret. Comput. Sci., 31, 211-223 (1984) · Zbl 0566.68062
[5] (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
[6] (Ehrig, H.; Nagl, M.; Rozenberg, G.; Rosenfeld, A., GraphGrammars and Their Application to Computer Science. GraphGrammars and Their Application to Computer Science, Lecture Notes in Computer Science, Vol. 291 (1987), Springer-Verlag: Springer-Verlag Berlin) · Zbl 0636.00013
[7] Engelfriet, J.; Leih, G., Linear Graph Grammars: Power and Complexity, Inform. and Computation, 81, 88-121 (1989) · Zbl 0684.68088
[8] Engelfriet, J.; Leih, G., Nonterminal bounded NLC graph grammars, Theoret. Comput. Sci., 59, 309-315 (1988) · Zbl 0662.68074
[9] Engelfriet, J.; Leih, G., Complexity of Boundary Graph Languages, Report 88-07, Leiden (March 1988), RAIRO, in press
[10] Engelfriet, J.; Leih, G.; Rozenberg, G., Apex graph grammars and attribute grammars, Acta Inform., 25, 537-571 (1988) · Zbl 0659.68096
[11] J. Engelfriet, G. Leih, and G. Rozenberg, Apex graph grammars, in [EhrNagRozRos], pp. 167-185; J. Engelfriet, G. Leih, and G. Rozenberg, Apex graph grammars, in [EhrNagRozRos], pp. 167-185 · Zbl 0643.68112
[12] Engelfriet, J.; Leih, G.; Welzl, E., Boundary Graph Grammars with Dynamic Edge Relabeling, Report 87-30 (December 1987), Leiden
[13] Engelfriet, J.; Rozenberg, G., A Comparison of Boundary Graph Grammars and Context-free Hypergraph Grammars, Report 88-06 (February 1988), Leiden
[14] Gécseg, F.; Steinby, M., Tree Automata (1984), Akademiai Kiado: Akademiai Kiado Budapest · Zbl 0396.68041
[15] Habel, A.; Kreowski, H.-J., Characteristics of graph languages generated by edge replacement, Theoret. Comput. Sci., 51, 81-115 (1987) · Zbl 0636.68100
[16] Harary, F., Graph Theory (1969), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0797.05064
[17] Hoffmann, J.; Main, M. G., Results on NLC Grammars with One-Letter Terminal Alphabets, Report CU-CS-348-86 (Sept. 1986), Boulder, CO
[18] Janssens, D., Node Label Controlled Graph Grammars, (Ph.D. thesis (1983), University of Antwerp) · Zbl 0455.68042
[19] Janssens, D.; Rozenberg, G., On the structure of node-label-controlled graph languages, Inform. Sci., 20, 191-216 (1980) · Zbl 0452.68073
[20] Janssens, D.; Rozenberg, G., Restrictions, extensions, and variations of NLC grammars, Inform. Sci., 20, 217-244 (1980) · Zbl 0452.68074
[21] Janssens, D.; Rozenberg, G., A characterization of context-free string languages by directed node-label controlled graph grammars, Acta Inform., 16, 63-85 (1981) · Zbl 0464.68077
[22] D. Janssens G. Rozenberg Graph grammars with node-label controlled rewriting and embedding, in [EhrNagRoz], 186-205.; D. Janssens G. Rozenberg Graph grammars with node-label controlled rewriting and embedding, in [EhrNagRoz], 186-205.
[23] Janssens, D.; Rozenberg, G., Graph gramars with neighbourhood-controlled embedding, Theoret. Comput. Sci., 21, 55-74 (1982) · Zbl 0486.68075
[24] 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
[25] J. Jeffs Embedding rule independent theory of graph grammars, in [EhrNagRozRos], pp. 299-308.; J. Jeffs Embedding rule independent theory of graph grammars, in [EhrNagRozRos], pp. 299-308.
[26] Kaul, M., Syntaxanalyse von Graphen bei Prdzedenz-Graph-Grammatiken, (dissertation (1985), Universität Osnabrdck) · Zbl 0587.68076
[27] M. Kaul, Practical applications of precedence graph grammars, in [EhrNagRozRos], pp. 326-342; M. Kaul, Practical applications of precedence graph grammars, in [EhrNagRozRos], pp. 326-342 · Zbl 0643.68108
[28] Nagl, M., Graph-grammatiken (1979), Vieweg: Vieweg Braunschweig · Zbl 0517.68069
[29] Rosenfeld, A.; Milgram, D. L., Web automata and web grammars, Mach. Intell., 7, 307-324 (1972) · Zbl 0259.68037
[30] Rozenberg, G.; Welzl, E., Boundary NLC graph grammars-Basic definitions, normal forms, and complexity, Inform. Control, 69, 136-167 (1986) · Zbl 0608.68060
[31] 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
[32] Rozenberg, G.; Welzl, E., Combinatorial properties of boundary NLC graph languages, Discrete Appl. Math., 16, 58-73 (1987) · Zbl 0619.68063
[33] Salomaa, A., Formal Languages (1973), Academic Press: Academic Press New York · Zbl 0262.68025
[34] Thatcher, J. W., Characterizing derivation trees of context-free grammars through a generalization of finite automata theory, J. Comput. System Sci., 1, 317-322 (1967) · Zbl 0155.01802
[35] Welzl, E., Encoding graphs by derivations and implications for the theory of graph grammars, (Paradaens, J., Proceedings, 11th ICALP. Proceedings, 11th ICALP, Lecture Notes in Computer Science, Vol. 172 (1984), Springer-Verlag: Springer-Verlag Berlin), 503-513 · Zbl 0557.68050
[36] E. Welzl, Boundary NLC and partition controlled graph grammars,in [EhrNagRozRos], pp. 593-609.; E. Welzl, Boundary NLC and partition controlled graph grammars,in [EhrNagRozRos], pp. 593-609.
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.