The bounded degree problem for non-obstructing eNCE graph grammars | SpringerLink
Skip to main content
Springer Nature Link
Log in

The bounded degree problem for non-obstructing eNCE graph grammars

  • Algorithms and Architectures
  • Conference paper
  • First Online:
Graph Grammars and Their Application to Computer Science (Graph Grammars 1994)

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

  • 161 Accesses

Abstract

A graph grammar is called non-obstructing if each graph G derivable from the axiom can derive a terminal graph. In this paper, the bounded degree problem for non-obstructing eNCE graph grammars is proved to be in the complexity class NL.

The work of the first author was supported by the German Research Association (DFG) grant Br-835-3/2

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.

Similar content being viewed by others

References

  1. F.J. Brandenburg. On partially ordered graph grammars. In H. Ehrig, M. Nagl, A. Rosenfeld, and G. Rozenberg, editors, Proceedings of Graph-Grammars and Their Application to Computer Science, volume 291 of LNCS, pages 99–111. Springer-Verlag, 1987.

    Google Scholar 

  2. J. Engelfriet, G. Leih, and E. Welzl. Boundary graph grammars with dynamic edge relabeling. Journal of Computer and System Sciences, 40:307–345, 1990.

    Google Scholar 

  3. A. Habel. Hyperedge Replacement: Grammars and Languages, volume 643 of LNCS. Springer-Verlag, 1992.

    Google Scholar 

  4. N. Immerman. Languages that capture complexity classes. SIAM Journal on Computing, 16(4):760–778, 1987.

    Google Scholar 

  5. D. Janssens and G. Rozenberg. On the structure of node label controlled graph languages. Information Science, 20:191–216, 1980.

    Google Scholar 

  6. D. Janssens and G. Rozenberg. Restrictions, extensions, and variations of NLC grammars. Information Science, 20:217–244, 1980.

    Google Scholar 

  7. D. Janssens, G. Rozenberg, and E. Welzl. The bounded degree problem for NLC graph grammars is decidable. Journal of Computer and System Sciences, 33:415–422, 1986.

    Google Scholar 

  8. M. Kaul. Syntaxanalyse von Graphen bei Präzedenz-Graphgrammatiken. Dissertation, Universität Osnabrück, Osnabrück, Germany, 1985.

    Google Scholar 

  9. M. Kaul. Practical applications of precedence graph grammars. In H. Ehrig, M. Nagl, A. Rosenfeld, and G. Rozenberg, editors, Proceedings of Graph-Grammars and Their Application to Computer Science, volume 291 of LNCS, pages 326–342. Springer-Verlag, 1987.

    Google Scholar 

  10. A. Monti and A. Roncato. On the computational complexity of some decidable problems for EOL systems and BSTA. Technical Report 12/93, University of Pisa, I-56125 Pisa,Italy, 1993.

    Google Scholar 

  11. K. Skodinis and E. Wanke. The Complexity of Emptiness Problems of eNCE Graph Languages. LNCS, 903:180–192, 1994, to appear in Journal of Computer and System Sciences.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. University of Passau, 94032, Passau, Germany

    K. Skodinis

  2. University of Düsseldorf, 40225, Düsseldorf, Germany

    E. Wanke

Authors
  1. K. Skodinis
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. E. Wanke
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Janice Cuny Hartmut Ehrig Gregor Engels Grzegorz Rozenberg

Rights and permissions

Reprints and permissions

Copyright information

© 1996 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Skodinis, K., Wanke, E. (1996). The bounded degree problem for non-obstructing eNCE graph grammars. In: Cuny, J., Ehrig, H., Engels, G., Rozenberg, G. (eds) Graph Grammars and Their Application to Computer Science. Graph Grammars 1994. Lecture Notes in Computer Science, vol 1073. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-61228-9_89

Download citation

  • DOI: https://doi.org/10.1007/3-540-61228-9_89

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

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

  • Online ISBN: 978-3-540-68388-9

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation