Complexity of boundary graph languages

Joost Engelfriet; George Leih

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (1990)

  • Volume: 24, Issue: 3, page 267-274
  • ISSN: 0988-3754

How to cite

top

Engelfriet, Joost, and Leih, George. "Complexity of boundary graph languages." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 24.3 (1990): 267-274. <http://eudml.org/doc/92359>.

@article{Engelfriet1990,
author = {Engelfriet, Joost, Leih, George},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},
keywords = {graph languages; graph grammars},
language = {eng},
number = {3},
pages = {267-274},
publisher = {EDP-Sciences},
title = {Complexity of boundary graph languages},
url = {http://eudml.org/doc/92359},
volume = {24},
year = {1990},
}

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
PB - EDP-Sciences
VL - 24
IS - 3
SP - 267
EP - 274
LA - eng
KW - graph languages; graph grammars
UR - http://eudml.org/doc/92359
ER -

References

top
  1. 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). Zbl0694.68045MR1056583
  2. 2. J. ENGELFRIET and G. LEIH, Linear Graph Grammars: Power and Complexity, Information and Computation, 81, 1989, pp. 88-121. Zbl0684.68088MR992305
  3. 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. Zbl0643.68112MR943173
  4. 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). Zbl0694.68049MR1056581
  5. 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. Zbl0706.68067MR1035865
  6. 6. N. IMMERMANN, Nondeterministic Space is Closed Under Complement, Yale University, Technical Report, YALEU/DCS/TR 552, July 1987. MR961049
  7. 7. D. JANSSENS and G. ROZENBERG, On the Structure of Node-Label-Controlled Graph Languages, Information Sciences, 20, 1980, pp. 191-216. Zbl0452.68073MR563981
  8. 8. D. JANSSENS and G. ROZENBERG, Graph Grammars with Neighbourhood-Controlled Embedding, Theor. Comp. Science, 21, 1982, pp. 55-74. Zbl0486.68075MR672102
  9. 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. Zbl0531.68030
  10. 10. M. KAUL, Syntaxanalyse von Graphen bei Präzedenz-Graph-Grammatiken, Dissertation, Universität Osnabrück, 1985. Zbl0587.68076
  11. 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. Zbl0649.68075MR1023648
  12. 12. G. ROZENBERG and E. WELZL, Boundary NLC Graph Grammars-Basic Definitions, Normal Forms, and Complexity, Inform. Contr., Vol. 69, 1986, pp. 136-167. Zbl0608.68060MR848438
  13. 13. W. L. Ruzzo, Tree-Size Bounded Alternation, J.C.S.S., 21, 1980, pp. 218-235. Zbl0445.68034MR597795
  14. 14. I. H. SUDBOROUGH, On the Tape Complexity of Deterministic Context-Free Languages, J.A.C.M., Vol. 25, 1978, pp. 405-414. Zbl0379.68054MR498563
  15. 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. Zbl0664.68082
  16. 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. Zbl0643.68109MR943182

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.