×

Linear graph grammars: Power and complexity. (English) Zbl 0684.68088

The authors consider linear graph grammars with neighbourhood controlled embedding and with dynamic edge relabelling, linear eNCE grammars. With respect to generative power they are shown to be equivalent to eNCE grammars that can generate only graphs with a bounded number of non- terminal nodes and to graph grammars in whose language every graph has at least one derivation involving graphs with a bounded number of non- terminal nodes. This is in direct contrast to the corresponding situation for context-free string grammars. The membership problem for linear eNCE languages with only connected graph of bounded degree is in NSPACE(log n) and hence in P, where n is the number of symbols needed to encode the graph (the paper does not clarify which encodings are permitted; however, the algorithm given seems to assume a “simple” encoding as usual in graph algorithms). This result has an interesting application in proving complexity bounds for certain properties of graphs.
Reviewer: H.Jürgensen

MSC:

68Q45 Formal languages and automata
68R10 Graph theory (including graph drawing) in computer science
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aalbersberg, I. J.J.; Engelfriet, J.; Rozenberg, G., The Complexity of Regular DNLC Graph Languages (1986), Report 86-03, Leiden
[2] See also Ehriget al.; See also Ehriget al.
[3] Aalbersberg, I. J.J.; Rozenberg, G.; Ehrenfeucht, A., On the membership problem for regular DNLC grammars, Discrete Appl. Math., 13, 79-85 (1986) · Zbl 0602.68064
[4] Berstel, J., (Transductions and Context-free languages (1979), Teubner: Teubner Stuttgart) · Zbl 0424.68040
[5] Chinn, P. Z.; Chvátalová, J.; Dewdney, A. K.; Gibbs, N. E., The bandwidth problem for graphs and matrices—A survey, J. Graph Theory, 6, 223-254 (1982) · Zbl 0494.05057
[6] Courcelle, B., Recognizability and Second-Order Definability for Sets of Finite Graphs (1987), Report I-8634, Bordeaux
[7] (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
[8] (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
[9] Engelfriet, J.; Leih, G., Nonterminal bounded NLC graph grammars, Theoret. Comput. Sci., 59, 309-315 (1988) · Zbl 0662.68074
[10] Engelfriet, J.; Leih, G., Complexity of Boundary Graph Languages (1988), Report 88-07, Leiden
[11] Engelfriet, J.; Leih, G.; Rozenberg, G., Apex graph grammars and attribute grammars, Acta Inform., 25, 537-571 (1987) · Zbl 0659.68096
[12] Engelfriet, J.; Leih, G.; Rozenberg, G., Apex graph grammars, (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), 167-185, 1987 · Zbl 0643.68112
[13] Engelfriet, J.; Leih, G.; Welzl, E., Boundary Graph Grammars with Dynamic Edge Relabeling (1987), Report 87-30, Leiden · Zbl 0694.68049
[14] Ginsburg, S.; Spanier, E., Finite-turn pushdown automata, SIAM J. Control, 4, 429-453 (1966) · Zbl 0147.25302
[15] Ginsburg, S.; Spanier, E., Derivation-bounded languages, J. Comput. System Sci., 2, 228-250 (1968) · Zbl 0176.16703
[16] Gurari, E. M.; Sudborough, I. H., Improved dynamic programming algorithms for bandwidth minimization and the min-cut linear arrangement problem, J. Algorithms, 5, 531-546 (1984) · Zbl 0556.68012
[17] Harary, F., (Graph Theory (1969), Addison-Wesley: Addison-Wesley Reading, MA) · Zbl 0182.57702
[18] Hopcroft, J. E.; Ullman, J. D., (Introduction to Automata Theory, Languages and Computation (1979), Addison-Wesley: Addison-Wesley Reading, MA) · Zbl 0426.68001
[19] Immermann, N., (Nondeterministic Space Is Closed under Complement (1987), Yale University), Technical Report YALEU/DCS/TR 552
[20] Janssens, D.; Rozenberg, G., On the structure of node-label-controlled graph languages, Inform. Sci., 20, 191-216 (1980) · Zbl 0452.68073
[21] Janssens, D.; Rozenberg, G., Decision problems for node label controlled graph grammars, J. Comput. System Sci., 22, 144-177 (1981) · Zbl 0466.68067
[22] Janssens, D.; Rozenberg, G., A characterization of context-free string languages by directed node-label controlled graph gammars, Acta Inform., 16, 63-85 (1981) · Zbl 0464.68077
[23] Janssens, D.; Rozenberg, G., Graph grammars with neighbourhood-controlled embedding, Theoret. Comput. Sci., 21, 55-74 (1982) · Zbl 0486.68075
[24] Janssens, D.; Rozenberg, G., Graph grammars with node-label controlled rewriting and embedding, (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 (1983), Springer-Verlag: Springer-Verlag Berlin), 186-205, 1983 · Zbl 0522.68072
[25] Janssens, D.; Rozenberg, G., Hypergraph systems and their extensions, RAIRO Inform. Théor., 17, 163-196 (1983) · Zbl 0512.68062
[26] 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
[27] Kaul, M., Syntaxanalyse von Graphen bei Präzedenz-Graph-Grammatiken, (Ph.D. thesis (1985), University of Osnabrück) · Zbl 0587.68076
[28] Lautemann, C., (Proceedings, 15th ICALP (1988))
[29] Lengauer, T., Upper and lower bounds on the complexity of the min-cut linear arrangement problem on trees, SIAM J. Algebraic Discrete Methods, 3, 99-113 (1982) · Zbl 0489.68060
[30] Makedon, F. S.; Papadimitriou, C. H.; Sudborough, I. H., Topological bandwidth, SIAM J. Algebraic Discrete Methods, 6, 418-444 (1985) · Zbl 0573.05052
[31] Nagl, M., Graph-grammatiken (1979), Vieweg: Vieweg Braunschweig · Zbl 0517.68069
[32] Pavlidis, T., Linear and context-free graph grammars, J. Assoc. Comput. Mach., 19, 11-22 (1972) · Zbl 0229.68027
[33] Rosenfeld, A.; Milgram, D. L., Web automata and web grammars, Mach. Intell., 7, 307-324 (1972) · Zbl 0259.68037
[34] Rozenberg, G.; Welzl, E., Boundary NLC graph grammars—Basic definitions, normal forms, and complexity, Inform. Control, 69, 136-167 (1986) · Zbl 0608.68060
[35] 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
[36] Rozenberg, G.; Welzl, E., Combinatorial properties of the boundary NLC graph languages, Discrete Appl. Math., 16, 58-73 (1987) · Zbl 0619.68063
[37] Ruzzo, W. L., Tree-size bounded alternation, J. Comput. System Sci., 21, 218-235 (1980) · Zbl 0445.68034
[38] Salomaa, A., (Formal Languages (1973), Academic Press: Academic Press New York) · Zbl 0262.68025
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.