May we introduce to you: Hyperedge replacement

  • Annegret Habel
  • Hans-Jörg Kreowski
Part I Tutorial Introductions
Part of the Lecture Notes in Computer Science book series (LNCS, volume 291)


In this kind of tutorial note, we explain how graphs can be rewritten by edge replacement. The formal definitions are accompanied by intuitive descriptions and a series of examples.


Natural Rubber Graph Grammar External Node Graph Language Data Flow Analysis 
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.


  1. /BC 86/.
    M. Bauderon, B. Courcelle: An Algebraic Formalism for Graphs, Lect. Not. Comp. Sci. 214, 74–84 (1986)Google Scholar
  2. /DG 78/.
    P. Della Vigna, C. Ghezzi: Context-free Graph Grammars, Inf. Contr. 37 (1978), 207–233CrossRefGoogle Scholar
  3. /Eh 79/.
    H. Ehrig: Introduction to the Algebraic Theory of Graph Grammars, Lect. Not. Comp. Sci. 73, 1–69 (1979)Google Scholar
  4. /FKZ 76/.
    R. Farrow, K. Kennedy, L. Zucconi: Graph Grammars and Global Program Data Flow Analysis, Proc. 17th Ann. IEEE Symp. on Found of Comp. Sci., Houston, Texas, Oct. 1976, 42–56Google Scholar
  5. /Fe 71/.
    J. Feder: Plex Languages, Inform. Sci. 3 (1971), 225–241Google Scholar
  6. /Fr 78/.
    R. Franck: A Class of Linearly Parsable Graph Grammars, Acta Informatica 10, 175–201 (1978)CrossRefGoogle Scholar
  7. /GR 62/.
    S. Ginsburg, G. Rice: Two Families of Languages Related to ALGOL, Journ. ACM, vol. 9 (1962), 350–371CrossRefGoogle Scholar
  8. /Gr 71/.
    J. Gruska: A Characterization of Context-free Languages, Journ. Comp. Syst. Sci. 5 (1971), 353–364Google Scholar
  9. /HK 83/.
    A. Habel, H.-J. Kreowski: On Context-Free Graph Languages Generated by Edge Replacement, Lect. Not. Comp. Sci. 153, 143–158 (1983)Google Scholar
  10. /HK 85/.
    —: Characteristics of Graph Languages Generated by Edge Replacement, University of Bremen, Comp. Sci. Report No. 3/85 (1985), also in Theor. Comp. Sci. 51, 81–115 (1987)Google Scholar
  11. /HK 87/.
    — Some Structural Aspects of Hypergraph Languages Generated by Hyperedge Replacement, Lect. Not. Comp. Sci. 247, 207–219 (1987)Google Scholar
  12. /JR 80/.
    D. Janssens, G. Rozenberg: On the Structure of Node-Label-Controlled Graph Grammars, Information Science 20, 191–216 (1980)CrossRefGoogle Scholar
  13. /JR 81/.
    — Decision Problems for NLC Grammars, Journal of Comp. and System Sciences 20 (1981), 144–177Google Scholar
  14. /Ka 83/.
    M. Kaul: Parsing of Graphs in Linear Time, Lect. Not. Comp. Sci. 153, 206–218 (1983)Google Scholar
  15. /Kr 77/.
    H.-J. Kreowski: Manipulationen von Graphmanipulationen, Ph. D. Thesis, Techn. Univ. Berlin, Comp. Sci. Dept., 1977Google Scholar
  16. /Kr 79/.
    —: A Pumping Lemma for Context-Free Graph Languages, Lect. Not. Comp. Sci. 73, 270–283 (1979)Google Scholar
  17. /Kr 86/.
    — Rule Trees Represent Derivations in Edge Replacement Systems, in G. Rozenberg, A. Salomaa (eds.): The Book of L, Springer Verlag, Berlin-Heidelberg 1986, 217–232Google Scholar
  18. /KR 84/.
    H.-J. Kreowski, G. Rozenberg: Note on Node-Rewriting Graph Grammars, Information Processing Letters 18, 21–24 (1984)Google Scholar
  19. /Li 85/.
    U. Lichtblau: Decompilation of Control Structures by Means of Graph Transformations, Lect. Not. Comp. Sci. 185, 284–297 (1985)Google Scholar
  20. /Pa 72/.
    T. Pavlidis: Linear and Context-Free Graph Grammars, Journ. ACM 19, 1, 11–23 (1972)Google Scholar
  21. /Pr 71/.
    T.W. Pratt: Pair Grammars, Graph Languages and String-to-Graph Translations, Journ. Comp. Syst. Sci. 5 (1971), 560–595Google Scholar
  22. /RW 86a/.
    G. Rozenberg, E. Welzl: Boundary NLC Graph Grammars-Basic Definitions, Normal Forms and Complexity, Information and Control 69, 136–167 (1986)CrossRefGoogle Scholar
  23. /RW 86b/.
    — Graph Theoretic Closure Properties of the Family of Boundary NLC Graph Languages, Acta Informatica 23, 289–309 (1986)CrossRefGoogle Scholar
  24. /SM 80/.
    I. Suzuki, T. Murata: Stepwise Refinements of Transitions and Places, Informatik-Fachberichte 52, Springer, 136–141 (1980)Google Scholar
  25. /Tu 83/.
    G. Turán: On the Complexity of Graph Grammars, Acta Cybern, 6, 271–281 (1983)Google Scholar
  26. /Va 79/.
    R. Valette: Analysis of Petri Nets by Stepwise Refinements, Journ. Comp. Syst. Sci. 18, 35–46 (1979)Google Scholar
  27. /Yn 71/.
    M.K. Yntema: Cap Expressions for Context-Free Languages, Inf. Contr. 18 (1971), 311–318Google Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 1987

Authors and Affiliations

  • Annegret Habel
    • 1
  • Hans-Jörg Kreowski
    • 1
  1. 1.Universität Bremen Fachbereich Mathematik/InformatiBremen

Personalised recommendations