Assemblies as Graph Processes

Abstract

This paper explores the potential of graph rewriting and graph processes as a tool for understanding natural computing, and in particular self-assembly. The basic point of view is that aggregation steps in self-assembly can be adequately described by graph rewriting steps in a graph transformation system: the building blocks of an assembly correspond to occurrences of rewriting rules, and hence assemblies correspond to graph processes. However, meaningful algorithms do not consist only of aggregation steps, but also of global steps in which assemblies are modified or partially destroyed. Thus a number of further operations acting on processes are proposed and it is shown that both kinds of operations (assembly and partial destruction) can be combined to yield meaningful algorithms.