Complexity of boundary graph languages
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 24 (1990) no. 3, pp. 267-274.
@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},
     pages = {267--274},
     publisher = {EDP-Sciences},
     volume = {24},
     number = {3},
     year = {1990},
     mrnumber = {1072994},
     zbl = {0701.68062},
     language = {en},
     url = {http://www.numdam.org/item/ITA_1990__24_3_267_0/}
}
TY  - JOUR
AU  - Engelfriet, Joost
AU  - Leih, George
TI  - Complexity of boundary graph languages
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 1990
SP  - 267
EP  - 274
VL  - 24
IS  - 3
PB  - EDP-Sciences
UR  - http://www.numdam.org/item/ITA_1990__24_3_267_0/
LA  - en
ID  - ITA_1990__24_3_267_0
ER  - 
%0 Journal Article
%A Engelfriet, Joost
%A Leih, George
%T Complexity of boundary graph languages
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 1990
%P 267-274
%V 24
%N 3
%I EDP-Sciences
%U http://www.numdam.org/item/ITA_1990__24_3_267_0/
%G en
%F 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) no. 3, pp. 267-274. http://www.numdam.org/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 | Zbl

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

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 | Zbl

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 | Zbl

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 | Zbl

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

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

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

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

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

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 | Zbl

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 | Zbl

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

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

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

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 | Zbl