Apex graph grammars and attribute grammars | Acta Informatica Skip to main content
Springer Nature Link
Log in

Apex graph grammars and attribute grammars

  • Published:
Acta Informatica Aims and scope Submit manuscript

Summary

Apex graph grammars are a particular type of directed node-label controlled (DNLC) graph grammars: the embedding edges are established between terminal nodes only. Apex graph grammars, slightly generalized, can generate the sets of dependency graphs of attribute grammars. The other way around, every apex graph language can be obtained from such a dependency graph language by a graph replacement (which is an operation analogous to a string homomorphism).

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

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Aalbersberg, IJ.J., Engelfriet, J., Rozenberg, G.: The complexity of regular DNLC graph languages, Report 86-03, Leiden, April 1986

  2. Aalbersberg, I.J.J., Rozenberg, G.: Traces, dependency graphs and DNLC grammars. Discrete Appl. Math. 11, 299–306 (1985)

    Google Scholar 

  3. Aalbersberg, I.J.J., Rozenberg, G., Ehrenfeucht, A.: On the membership problem for regular DNLC grammars. Discrete Appl. Math. 13, 79–85 (1986)

    Google Scholar 

  4. Alblas, H.: A characterization of attribute evaluation in passes. Acta Informatica 16, 427–464 (1981)

    Google Scholar 

  5. Claus, V., Ehrig, H., Rozenberg, G. (eds.): Graph-grammars and their application to computer science and biology (Lect. Notes Comput. Sci., vol. 73). Berlin Heidelberg New York: Springer 1979

    Google Scholar 

  6. Courcelle, B.: Equivalences and transformations of regular systems, applications to recursive program schemes and grammars. Theor. Comput. Sci. 42, 1–122 (1986)

    Google Scholar 

  7. Courcelle, B.: An axiomatic definition of context-free rewriting and its application to NLC graph grammars, Report I-8706, University of Bordeaux, 1987

  8. Courcelle, B., Franchi-Zannettacci, P.: Attribute grammars and recursive program schemes. Theor. Comput. Sci. 17, 163–191, 235–257 (1982)

    Google Scholar 

  9. Culik II, K., Lindenmayer, A.: Graph OL-Systems and recurrence systems on graphs. Proceedings of the 8th Hawaii Conference on Systems Science, January 1975

  10. Culik II, K., Wood, D.: A mathematical investigation of propagating graph OL systems. Inf. Contr. 43, 50–82 (1979)

    Google Scholar 

  11. Ehrig, H., Nagl, M., Rozenberg, G., Rosenfeld, A. (eds.): Graph-grammars and their application to computer science (Lect. Notes Comput. Sci., vol. 291). Berlin Heidelberg New York: Springer 1987

    Google Scholar 

  12. Ehrig, H., Nagl, M., Rozenberg, G. (eds.): Graph-grammars and their application to computer science (Lect. Notes Comput. Sci., vol. 153). Berlin Heidelberg New York: Springer 1983

    Google Scholar 

  13. Engelfriet, J., File, G.: The formal power of one-visit attribute grammars. Acta Informatica 16, 275–302 (1981)

    Google Scholar 

  14. Engelfriet, J., Leih, G.: Linear graph grammars: power and complexity, Report 87-15, Leiden, May 1987

  15. Engelfriet, J., Leih, G., Rozenberg, G.: Apex graph grammars, in [EhrNagRosRoz] Ehrig, H., Nagl, M., Rozenberg, G. (eds.): Graph-grammars and their application to computer science (Lect. Notes Comput. Sci., vol. 153). Berlin Heidelberg New York: Springer 1983, pp. 167–185

  16. Ganzinger, H.: On storage optimization for automatically generated compilers. In: Theoretical Computer Science, 4th GI Conference (Lect. Notes Comput. Sci., vol. 67, pp. 132–141). Berlin Heidelberg New York: Springer 1975

    Google Scholar 

  17. Gecseg, F., Steinby, M.: Tree automata. Budapest: Akademiai Kiado 1984

    Google Scholar 

  18. Harary, F.: Graph theory. Reading, Mass.: Addison-Wesley 1969

    Google Scholar 

  19. Harrison, M.A.: Introduction to formal language theory. Reading, Mass.: Addison-Wesley 1978

    Google Scholar 

  20. Hoffmann, B.: Modelling compiler generation by graph grammars, in [EhrNagRoz] Ehrig, H., Nagl, M., Rozenberg, G. (eds.): Graph-grammars and their application to computer science (Lect. Notes Comput. Sci., vol. 153). Berlin Heidelberg New York: Springer 1983, pp. 159–171

  21. Hopcroft, J.E., Ullman, J.D.: Introduction to automata theory, languages, and computation. Reading, Mass.: Addison-Wesley 1979

    Google Scholar 

  22. Janssens, D., Rozenberg, G.: On the structure of node-label-controlled graph languages. Inform. Sci. 20, 191–216 (1980)

    Google Scholar 

  23. Janssens, D., Rozenberg, G.: Decision problems for node label controlled graph grammars. JCSS 22, 144–177 (1981)

    Google Scholar 

  24. Janssens, D., Rozenberg, G.: A characterization of context-free string languages by directed node-label controlled graph grammars. Acta Informatica 16, 63–85 (1981)

    Google Scholar 

  25. Janssens, D., Rozenberg, G.: Graph grammars with node-label controlled rewriting and embedding, in [EhrNagRoz] Ehrig, H., Nagl, M., Rozenberg, G. (eds.): Graph-grammars and their application to computer science (Lect. Notes Comput. Sci., vol. 153). Berlin Heidelberg New York: Springer 1983, pp. 186–205

  26. Janssens, D., Rozenberg, G.: Graph grammars with neighbourhood-controlled embedding. Theor. Comput. Sci. 21, 55–74 (1982)

    Google Scholar 

  27. Janssens, D., Rozenberg, G., Verraedt, R.: On sequential and parallel node-rewriting graph grammars. Comput. Graphics Image Proc. 18, 279–304 (1982)

    Google Scholar 

  28. Jazayeri, M., Ogden, W.F., Rounds, W.C.: The intrinsically exponential complexity of the circularity problem for attribute grammars. CACM 18, 697–706 (1975)

    Google Scholar 

  29. Knuth, D.E.: Semantics of context-free languages. Math. Syst. Theory 2, 127–145 (1968); correction: Math. Syst. Theory 5, 95–96 (1971)

    Google Scholar 

  30. Kreowski, H.-J.: Rule trees represent derivations in edge replacement systems. In: Rozenberg, G., Salomaa, A. (eds.) The book of L. pp. 217–232. Berlin Heidelberg New York: Springer 1986

    Google Scholar 

  31. Kreowski, H.-J., Rozenberg, G.: Note on node-rewriting graph grammars. Inf. Proc. Lett. 18, 21–24 (1984)

    Google Scholar 

  32. Lautemann, C.: Decomposition trees: structured graph representation and efficient algorithms. Proceedings of CAAP '88

  33. Lorho, B. (ed.): Methods and tools for compiler construction. Cambridge: Cambridge University Press 1984

    Google Scholar 

  34. Räihä, K.-J., Ukkonen, E.: Minimizing the number of evaluation passes for attribute grammars. SIAM J. Comput. 10, 772–786 (1981)

    Google Scholar 

  35. Rosenfeld, A., Milgram, D.L.: Web automata and web grammars. Machine Intell. 7, 307–324 (1972)

    Google Scholar 

  36. Rozenberg, G., Welzl, E.: Boundary NLC graph grammars — basic definitions, normal forms, and complexity. Inform. Contr. 69, 136–167 (1986)

    Google Scholar 

  37. Rozenberg, G., Welzl, E.: Graph theoretic closure properties of the family of boundary NLC graph languages, Acta Informatica 23, 289–309 (1986)

    Google Scholar 

  38. Rozenberg, G., Welzl, E.: Combinatorial properties of boundary NLC graph languages. Discrete Appl. Math. 16, 59–73 (1987)

    Google Scholar 

  39. Seese, D.: Tree-partite graphs and the complexity of algorithms. In: Budach, L. (ed.) Fundamentals of computation theory (Lect. Notes Comput. Sci., vol. 199, pp. 412–421) Berlin Heidelberg New York: Springer 1985

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science, Leiden University, P.O. Box 9512, NL-2300, RA Leiden, The Netherlands

    Joost Engelfriet, George Leih & Grzegorz Rozenberg

Authors
  1. Joost Engelfriet
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. George Leih
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Grzegorz Rozenberg
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Engelfriet, J., Leih, G. & Rozenberg, G. Apex graph grammars and attribute grammars. Acta Informatica 25, 537–571 (1988). https://doi.org/10.1007/BF00279953

Download citation

  • Received:

  • Issue Date:

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

Keywords

Search

Navigation