We continue the formal study of multiset-based self-assembly. The process of self-assembly of graphs, where iteratively new nodes are attached to a given graph, is guided by rules operating on nodes labelled by multisets. In this way, the multisets and rules model connection points (such as "sticky ends") and complementarity/affinity between connection points, respectively. We identify three natural ways (individual, free, and collective) to attach (aggregate) new nodes to the graph, and study the generative power of the corresponding self-assembly systems. For example, it turns out that individual aggregation can be simulated by free or collective aggregation. However, we demonstrate that, for a fixed set of connection points, collective aggregation is rather restrictive. We also give a number of results that are independent of the way that aggregation is performed. © 2010 Springer Science+Business Media B.V.
On aggregation in multiset-based self-assembly of graphs / Bernardini, F.; Brijder, R.; Cavaliere, M.; Franco, G.; Hoogeboom, H. J.; Rozenberg, G.. - In: NATURAL COMPUTING. - ISSN 1567-7818. - 10:1(2011), pp. 17-38. [10.1007/s11047-010-9183-3]
On aggregation in multiset-based self-assembly of graphs
Cavaliere M.;
2011
Abstract
We continue the formal study of multiset-based self-assembly. The process of self-assembly of graphs, where iteratively new nodes are attached to a given graph, is guided by rules operating on nodes labelled by multisets. In this way, the multisets and rules model connection points (such as "sticky ends") and complementarity/affinity between connection points, respectively. We identify three natural ways (individual, free, and collective) to attach (aggregate) new nodes to the graph, and study the generative power of the corresponding self-assembly systems. For example, it turns out that individual aggregation can be simulated by free or collective aggregation. However, we demonstrate that, for a fixed set of connection points, collective aggregation is rather restrictive. We also give a number of results that are independent of the way that aggregation is performed. © 2010 Springer Science+Business Media B.V.
Pubblicazioni consigliate
I metadati presenti in IRIS UNIMORE sono rilasciati con licenza Creative Commons CC0 1.0 Universal, mentre i file delle pubblicazioni sono rilasciati con licenza Attribuzione 4.0 Internazionale (CC BY 4.0), salvo diversa indicazione.
In caso di violazione di copyright, contattare Supporto Iris
