Skip to main content
SpringerLink
Log in

Programmed graph grammars

  • List Of Contributions
  • Conference paper
  • First Online:
Book cover Graph-Grammars and Their Application to Computer Science and Biology (Graph Grammars 1978)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 73))

Abstract

Let [enum], [exp-i] and [pr-i] denote the class of recursively enumerable, typ-i expression and typ-i programmed graph languages respectively. The following hierarchy is known from [5]:

[enum] = [exp-unrestricted] ⫌ [exp-monotone] = [exp-context free]

The proof of section 3 holds true also for unrestricted productions, so

[enum] = [exp-unrestricted] ⫅ [pr-unrestricted].

At the other hand, from Def. 2.11 it follows immediately that

[pr-unrestricted] ⫅ [enum].

Summarizing these results including the theorems of section 3, 4 and 5 we get the Corollary 6.1 : The following diagram of relations holds true:

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

References

  1. BUNKE, H.: Beschreibung eines syntaxgesteuerten inkrementellen Compilers durch Graph-Grammatiken, Arbeitsbericht des Instituts für Math.Masch.u. Datenverarbeitung 7, 7, Erlangen 1974

    Google Scholar 

  2. BUNKE, H.: Sequentielle und parallele programmierte Graph-Grammatiken, Dissertation to appear

    Google Scholar 

  3. BRENDEL, W./BUNKE, H./NAGL, M.: Syntaxgesteuerte Programmierung und inkrementelle Compilation, Informatik-Fachberichte 10, 55–74, Berlin, Springer-Verlag, 1977

    Google Scholar 

  4. CULIK,K. II/FARAH,M.: Linked forest manipulation systems, a tool for computational semantics, Techn.Rep.CS-77-18, University of Waterloo, 1977

    Google Scholar 

  5. EHRIG,H.: Introduction to the Algebraic Theory of Graph Grammars, this volume

    Google Scholar 

  6. NAGL,M.: Graph-Ersetzungssysteme: Theorie, Anwendungen, Implementierung, Habilitationsschrift, University of Erlangen, 1978

    Google Scholar 

  7. NAGL,M.: A Tutorial and Bibliographical Survey on Graph Grammars, this volume

    Google Scholar 

  8. ROSENKRANTZ, D.J.: Programmend Grammars and Classes of Formal Languages, JACM 16, 1969, 107–131

    Google Scholar 

  9. SCHNEIDER, H.J.: Chomsky-System für partielle Ordnungen, Arbeitsbericht des Instituts für Math.Masch.und Datenverarbeitung 3, 3, Erlangen, 1970

    Google Scholar 

  10. SCHNEIDER, H.J.: Conceptual data base description using graph grammars, in H. Noltemeier (Ed.): Graphen, Algorithmen, Datenstrukturen, Applied Computer Science 4, 77–98, München, Hauser-Verlag, 1976

    Google Scholar 

  11. UESU,T.: A system of graph grammars which generates all recursively enumberable sets of labelled graphs, private communication 1977

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Lehrstuhl für Informatik 5 (Mustererkennung), Universität Erlangen-Nürnberg, Martensstr. 3, 8520, Erlangen

    Horst Bunke

Authors
  1. Horst Bunke
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Volker Claus Hartmut Ehrig Grzegorz Rozenberg

Rights and permissions

Reprints and permissions

Copyright information

© 1979 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Bunke, H. (1979). Programmed graph grammars. In: Claus, V., Ehrig, H., Rozenberg, G. (eds) Graph-Grammars and Their Application to Computer Science and Biology. Graph Grammars 1978. Lecture Notes in Computer Science, vol 73. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0025718

Download citation

  • DOI: https://doi.org/10.1007/BFb0025718

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-09525-5

  • Online ISBN: 978-3-540-35091-0

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation