Linear graph grammars: Power and complexity

Aalbersberg, 1986, The Complexity of Regular DNLC Graph Languages See also Ehrig et al. (1987), pp.147–166 Aalbersberg, 1986, On the membership problem for regular DNLC grammars, Discrete Appl. Math., 13, 79, 10.1016/0166-218X(86)90070-3 Berstel, 1979 Chinn, 1982, The bandwidth problem for graphs and matrices—A survey, J. Graph Theory, 6, 223, 10.1002/jgt.3190060302 Courcelle, 1987, Recognizability and Second-Order Definability for Sets of Finite Graphs 1983, Vol. 153 1987, Vol. 291 Engelfriet, 1988, Nonterminal bounded NLC graph grammars, Theoret. Comput. Sci., 59, 309, 10.1016/0304-3975(88)90148-X Engelfriet, 1988, Complexity of Boundary Graph Languages Engelfriet, 1987, Apex graph grammars and attribute grammars, Acta Inform., 25, 537, 10.1007/BF00279953 Engelfriet, 1987, Apex graph grammars, Vol. 291, 167 Engelfriet, 1987, Boundary Graph Grammars with Dynamic Edge Relabeling Ginsburg, 1966, Finite-turn pushdown automata, SIAM J. Control, 4, 429, 10.1137/0304034 Ginsburg, 1968, Derivation-bounded languages, J. Comput. System Sci., 2, 228, 10.1016/S0022-0000(68)80009-1 Gurari, 1984, Improved dynamic programming algorithms for bandwidth minimization and the min-cut linear arrangement problem, J. Algorithms, 5, 531, 10.1016/0196-6774(84)90006-3 Harary, 1969 Hopcroft, 1979 Immermann, 1987 Janssens, 1980, On the structure of node-label-controlled graph languages, Inform. Sci., 20, 191, 10.1016/0020-0255(80)90038-9 Janssens, 1981, Decision problems for node label controlled graph grammars, J. Comput. System Sci., 22, 144, 10.1016/0022-0000(81)90025-8 Janssens, 1981, A characterization of context-free string languages by directed node-label controlled graph gammars, Acta Inform., 16, 63, 10.1007/BF00289591 Janssens, 1982, Graph grammars with neighbourhood-controlled embedding, Theoret. Comput. Sci., 21, 55, 10.1016/0304-3975(82)90088-3 Janssens, 1983, Graph grammars with node-label controlled rewriting and embedding, Vol. 291, 186 Janssens, 1983, Hypergraph systems and their extensions, RAIRO Inform. Théor., 17, 163, 10.1051/ita/1983170201631 Janssens, 1982, On sequential and parallel node-rewriting graph grammars, Comput. Graphics Image Process., 18, 279, 10.1016/0146-664X(82)90036-3 Kaul, 1985, Syntaxanalyse von Graphen bei Präzedenz-Graph-Grammatiken Lautemann, 1988 Lautemann, 1988 Lengauer, 1982, Upper and lower bounds on the complexity of the min-cut linear arrangement problem on trees, SIAM J. Algebraic Discrete Methods, 3, 99, 10.1137/0603010 Makedon, 1985, Topological bandwidth, SIAM J. Algebraic Discrete Methods, 6, 418, 10.1137/0606044 Nagl, 1979 Pavlidis, 1972, Linear and context-free graph grammars, J. Assoc. Comput. Mach., 19, 11, 10.1145/321679.321682 Rosenfeld, 1972, Web automata and web grammars, Mach. Intell., 7, 307 Rozenberg, 1986, Boundary NLC graph grammars—Basic definitions, normal forms, and complexity, Inform. Control, 69, 136, 10.1016/S0019-9958(86)80045-6 Rozenberg, 1986, Graph theoretic closure properties of the family of boundary NLC graph languages, Acta Inform., 23, 289, 10.1007/BF00289115 Rozenberg, 1987, Combinatorial properties of the boundary NLC graph languages, Discrete Appl. Math., 16, 58, 10.1016/0166-218X(87)90054-0 Ruzzo, 1980, Tree-size bounded alternation, J. Comput. System Sci., 21, 218, 10.1016/0022-0000(80)90036-7 Salomaa, 1973