On aggregation in multiset-based self-assembly of graphs

Francesco Bernardini, Robert Brijder, Matteo Cavaliere, Giuditta Franco, HendrikJan Hoogeboom, Grzegorz Rozenberg

Research output: Contribution to journalArticlepeer-review

Abstract / Description of output

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.
Original languageEnglish
Pages (from-to)17-38
Number of pages22
JournalNatural Computing
Volume10
Issue number1
DOIs
Publication statusPublished - 2011

Keywords / Materials (for Non-textual outputs)

  • Self-assembly
  • Multiset guided graph transformations
  • Cell aggregation

Fingerprint

Dive into the research topics of 'On aggregation in multiset-based self-assembly of graphs'. Together they form a unique fingerprint.

Cite this