@inproceedings{0153d96472ea4d0ba4144db51007b418,
title = "Computational Completeness of Programming Languages Based on Graph Transformation",
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.",
author = "Annegret Habel and Detlef Plump and F. Honsell and M. Miculan",
year = "2001",
doi = "10.1007/3-540-45315-6_15",
language = "English",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
pages = "230--245",
booktitle = "Foundations of Software Science and Computation Structures : 4th International Conference (FOSSACS 2001)",
address = "Germany",
note = "ETAPS 2001 ; Conference date: 02-04-2001 Through 06-04-2001",
}