Directed Self-Assembly Using Graph GrammarsEric Klavins?University of WashingtonElectrical Engineering DepartmentBox 352500Seattle, WA 98195Abstract. In this paper we describe the graph grammar approach tomodeling self-assembly. The approach is used to describe how the topol-ogy of an assembling aggregate changes as it grows. The main purpose ofthe paper is to demonstrate the utility of the approach by giving detailedexamples. We also describe the beginnings of our approach to physicallyembedding graph grammar assembly rules in physical settings, focusingon macro- and micro-scale programmable parts and a simulation envi-ronment.1 IntroductionEngineering in the realm of the very small presents us with the daunting problemof manipulating and coordinating vast numbers of objects so that they performsome global task. Nevertheless, there are examples of sophisticated machines,such as the ribosome or the mechanical motor in the bacterial flagellum, thatseem to be built in bulk spontaneously. It is assumed that in the formation ofthese objects, simple small components self-assemble into more complex aggre-gates which, in turn, self-assemble into larger aggregates.Our starting point in understanding self assembly is the idea of conforma-tional switching [17]: Each part (molecule, robot, etc.) exists in one of severalconformations or shapes. When two parts come into close proximity, they at-tach or not based on whether their conformations are complimentary. If they doattach, their conformations change (mechanically for example), thereby deter-mining in what future assembly interactions the parts may partake.In this paper, as in other work [16, 14], we represent the conformation of apart by a discrete symbol, and we model an assembly as a simple graph labeledby such symbols. Vertices in these graphs represent parts, and the presence of anedge between two parts represents that they are somehow attached. An assemblyrule, then, is a pair of such labeled graphs interpreted as follows. If a subset ofparts with their labels and edges matches the first part of an assembly rule,then it may be replaced by the second part of the rule to achieve a new state ofthe system. We are in particular interested in (1) the situation where the partsdecide in a distributed fashion whether and how to execute an assembly rule;?This work is supported in part by NSF Grant #0347955.(2) how to model natural and artificial assembly processes; (3) how to defineassembly rule sets so that only prespecified assemblies are built.Specifically, the main contribution of this paper is a set of illustrative exam-ples that show (1) how various types of assembly processes can be modeled and(2) how the graph grammars can simulate string grammars [9] and tile assemblysystems [21, 2]. The paper is meant to be complimentary to another paper wherewe investigate some of the formal properties of graph grammars [14]. We also in-clude a brief discussion of how one can embed the graph grammar formalism intophysical assembly systems, including macro-scale robotic “programmable parts”and micro-scale directed tile assembly. Finally, we end with a brief discussion ofrelated work.2 DefinitionsWe begin with basic definitions. Much of this section appeared first elsewhere[14], we include it for completeness. Basic graph-theory definitions are not num-bered, but only recalled [6].A simple labeled graph over an alphabet Σ is a triple G = (V, E, l) whereV is a set of vertices, E is a set of pairs or edges from V , and l : V → Σ is alabeling function. We restrict our discussion to simple labeled graphs and thussimply use the term graph. We denote by VG, EGand lGthe vertex set, edge setand labeling function of the graph G or by V , E and l when there is no dangerof confusion. We will usually use the alphabet Σ = {a, b, c, ...}.Given graphs G1and G2, we write f : G1→ G2and f : VG1→ VG2equivalently to mean that f is a function from the vertex set of G1to the vertexset of G2. A function h : G1→ G2is a label preserving embedding if1. h is injective,2. {x, y} ∈ EG1⇔ {h(x), h(y)} ∈ EG2,3. lG1= lG2◦ h.If h is also surjective then it is called an isomorphism. The graphs G1and G2aresaid to be isomorphic (written G1' G2) if there exists an isomorphism relatingthem.Definition 1. A rule is a pair of graphs r = (L, R) where VL= VR. The graphsL and R are called the left hand side and right hand side of r respectively. Thesize of r is |VL| = |VR|. Rules whose vertex sets have one, two and three verticesare called unary, binary and ternary, respectively.We may refer to rules as being constructive (EL⊂ ER), destructive (EL⊃ ER)or mixed (neither constructive or destructive). A rule is acyclic if its right handside contain no cycles (the left hand side may contain cycles).Definition 2. A rule r is applicable to a graph G if there exists an embeddingh : L → G. In this case the function h is called a witness. An action on a graphG is a pair (r, h) such that r is applicable to G with witness h.Definition 3. Given a graph G = (V, E, l) and an action (r, h) on G with r =(L, R), the application of (r, h) to G yields a new graph G0= (V0, E0, l0) definedbyV0= VE0= (E − {{h(x), h(y)} | {x, y} ∈ L})∪{{h(x), h(y)} | {x, y} ∈ R}l0(x) =l(x) if x 6∈ h(VL)lR◦ h−1(x) otherwise.We write Gr,h−−→G0to denote that G0was obtained from G by the application of(r, h).Definition 4. A graph assembly system is a pair (G0, Φ) where G0is the initialgraph and Φ is a set of rules (called the rule set).We often refer to a system simply by its rule set Φ and assume that the initialgraph is the infinite graph defined byG0, (N, ∅, λx.a) (1)where a ∈ Σ is the initial symbol (here λx.a is the function assigning the labela to all vertices).Definition 5. An assembly sequence of a system (G0, Φ) is a finite sequence{Gi}ki=0such that there exists a sequence of actions {(ri, hi)}ki=1where ri∈ ΦandGiri,hi−−−−→Gi+1for i ∈ {0, ..., k − 1}.Thus, a system (G0, Φ) defines a non-deterministic dynamical system whosestates are labeled graphs over VG0. The system is non-deterministic since, atany step, many rules in Φ may be simultaneously applicable, each possibly viaseveral witnesses.Two vertices in a graph G are connected if there is a path (sequence of edges)connecting them in G. The connectivity relation on V is an equivalence relationpartitioning V into sets {Vi}i∈Iwhere v1and v2are connected if and only ifv1, v2∈ Vifor some i.