Abstract
We identify a set of programming constructs ensuring that a programming language based on graph transformation is computationally complete. These constructs are (1) nondeterministic application of a set of graph transformation rules, (2) sequential composition and (3) iteration. This language is minimal in that omitting either sequential composition or iteration results in a computationally incomplete language. By computational completeness we refer to the ability to compute every computable partial function on labelled graphs. Our completeness proof is based on graph transformation programs which encode arbitrary graphs as strings, simulate Turing machines on these strings, and decode the resulting strings back into graphs.
Chapter PDF
Similar content being viewed by others
Keywords
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.
References
Hartmut Ehrig. Introduction to the algebraic theory of graph grammars. In Proc. Graph-Grammars and Their Application to Computer Science and Biology, volume 73 of Lecture Notes in Computer Science, 1–69. Springer-Verlag, 1979.
Claudia Ermel, Michael Rudolf, and Gabi Taentzer. The AGG approach: Language and environment. In H. Ehrig, G. Engels, H.-J. Kreowski, and G. Rozenberg, editors, Handbook of Graph Grammars and Computing by Graph Transformation, volume 2, chapter 14, 551–603. World Scientific, 1999.
Pascal Fradet and Daniel Le Métayer. Structured Gamma. Science of Computer Programming, 31(2-3):263–289, 1998.
John Glauert, Richard Kennaway, and Ronan Sleep. Dactl: An experimental graph rewriting language. In Proc. Graph Grammars and Their Application to Computer Science, volume 532 of Lecture Notes in Computer Science, pages 378–395. Springer-Verlag, 1991.
Annegret Habel, Jürgen Müller, Detlef Plump. Double-pushout graph transformation revisited. Bericht Nr. 7/99, Fachbereich Informatik, Universitat Oldenburg, 1999. Revised version to appear in Mathematical Structures in Computer Science.
Harry R. Lewis and Christos H. Papadimitriou. Elements of the Theory of Computation. Prentice-Hall, second edition, 1998.
Peter J. Rodgers. A graph rewriting programming language for graph drawing. In Proc. 14th IEEE Symposium on Visual Languages. IEEE Computer Society Press, 1998.
Andy Schurr, Andreas Winter, and Albert Zundorf. The PROGRES approach: Language and environment. In H. Ehrig, G. Engels, H.-J. Kreowski, and G. Rozenberg, editors, Handbook of Graph Grammars and Computing by Graph Transformation, volume 2, chapter 13, 487–550. World Scientific, 1999.
Tadahiro Uesu. A system of graph grammars which generates all recursively enumerable sets of labelled graphs. Tsukuba J. Math. 2, 11–26, 1978.
Klaus Weihrauch. Computability. Volume 9 of EATCS Monographs on Theoretical Computer Science. Springer-Verlag, 1987.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2001 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Habel, A., Plump, D. (2001). Computational Completeness of Programming Languages Based on Graph Transformation. In: Honsell, F., Miculan, M. (eds) Foundations of Software Science and Computation Structures. FoSSaCS 2001. Lecture Notes in Computer Science, vol 2030. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45315-6_15
Download citation
DOI: https://doi.org/10.1007/3-540-45315-6_15
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-41864-1
Online ISBN: 978-3-540-45315-4
eBook Packages: Springer Book Archive