Complexity of boundary graph languages
Engelfriet, Joost ; Leih, George
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 24 (1990), p. 267-274 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)
Publié le : 1990-01-01
@article{ITA_1990__24_3_267_0,
     author = {Engelfriet, Joost and Leih, George},
     title = {Complexity of boundary graph languages},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     volume = {24},
     year = {1990},
     pages = {267-274},
     mrnumber = {1072994},
     zbl = {0701.68062},
     language = {en},
     url = {http://dml.mathdoc.fr/item/ITA_1990__24_3_267_0}
}

Engelfriet, Joost; Leih, George. Complexity of boundary graph languages. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 24 (1990) pp. 267-274. http://gdmltest.u-ga.fr/item/ITA_1990__24_3_267_0/

1. Ij. J. Aalbersberg, J. Engelfriet and G. Rozenberg, The Complexity of Regular DNLC Graph Languages, Report 86-03, Leiden, April 1986, JCSS (to appear). | MR 1056583 | Zbl 0694.68045

2. J. Engelfriet and G. Leih, Linear Graph Grammars: Power and Complexity, Information and Computation, 81, 1989, pp. 88-121. | MR 992305 | Zbl 0684.68088

3. J. Engelfriet, G. Leih and G. Rozenberg, Apex Graph Grammars, in Graph-Grammars and their Application to Computer Science, H. EHRIG, M. NAGL, G. ROZENBERG and A. ROSENFELD Eds., Lecture Notes in Computer Science, 291, Springer-Verlag, Berlin, 1987, pp. 167-185. | MR 943173 | Zbl 0643.68112

4. J. Engelfriet, G. Leih and E. Welzl, Boundary Graph Grammars with Dynamic Edge Relabeling, Report 87-30, Leiden, December 1987, J. Comput. System Sci. (to appear). | MR 1056581 | Zbl 0694.68049

5. J. Engelfriet and G. Rozenberg, A Comparison of Boundary Graph Grammars and Context-Free Hypergraph Grammars, Information and Computation, 84, 1990, pp. 163-206. | MR 1035865 | Zbl 0706.68067

6. N. Immermann, Nondeterministic Space is Closed Under Complement, Yale University, Technical Report, YALEU/DCS/TR 552, July 1987. | MR 961049

7. D. Janssens and G. Rozenberg, On the Structure of Node-Label-Controlled Graph Languages, Information Sciences, 20, 1980, pp. 191-216. | MR 563981 | Zbl 0452.68073

8. D. Janssens and G. Rozenberg, Graph Grammars with Neighbourhood-Controlled Embedding, Theor. Comp. Science, 21, 1982, pp. 55-74. | MR 672102 | Zbl 0486.68075

9. D. Janssens, G. Rozenberg and R. Verraedt, On Sequential and Parallel Node-Rewriting Graph Grammars, Computer Graphics and Image Processing, 18, 1982, pp. 279-304. | Zbl 0531.68030

10. M. Kaul, Syntaxanalyse von Graphen bei Präzedenz-Graph-Grammatiken, Dissertation, Universität Osnabrück, 1985. | Zbl 0587.68076

11. C. Lautemann, Efficient Algorithms on Context-Free Graph Languages, in Proc. 15th I.C.A.L.P., T. LEPISTÖ and A. SALOMMA Eds., Lecture Notes in Computer Science, 317, Springer-Verlag, Berlin, 1988, pp. 362-378. | MR 1023648 | Zbl 0649.68075

12. G. Rozenberg and E. Welzl, Boundary NLC Graph Grammars-Basic Definitions, Normal Forms, and Complexity, Inform. Contr., Vol. 69, 1986, pp. 136-167. | MR 848438 | Zbl 0608.68060

13. W. L. Ruzzo, Tree-Size Bounded Alternation, J.C.S.S., 21, 1980, pp. 218-235. | MR 597795 | Zbl 0445.68034

14. I. H. Sudborough, On the Tape Complexity of Deterministic Context-Free Languages, J.A.C.M., Vol. 25, 1978, pp. 405-414. | MR 498563 | Zbl 0379.68054

15. R. Szelepcsényi, The Method of Forcing for Nondeterministic Automata Bulletin of the E.A.T.C.S., Vol. 33, 1987, pp. 96-99. | Zbl 0664.68082

16. E. Welzl, Boundary NLC and Partition Controlled Graph Grammars, in "Graph-Grammars and their Application to Computer Science", H. EHRIG M. NAGL, G. ROZENBERG and A. ROSENFELD Eds., Lecture Notes in Computer Science, 291, Springer-Verlag, Berlin, 1987, pp. 593-609. | MR 943182 | Zbl 0643.68109