Non-cooperative algorithms in self-assembly

DOI10.1007/978-3-319-21819-9_20zbMATH Open1465.68088arXiv1406.6889OpenAlexW2963510217MaRDI QIDQ2945574FDOQ2945574

Authors: Pierre Meunier 

Publication date: 14 September 2015

Published in: Unconventional Computation and Natural Computation (Search for Journal in Brave)

Abstract: We show the first non-trivial positive algorithmic results (i.e. programs whose output is larger than their size), in a model of self-assembly that has so far resisted many attempts of formal analysis or programming: the planar non-cooperative variant of Winfree's abstract Tile Assembly Model. This model has been the center of several open problems and conjectures in the last fifteen years, and the first fully general results on its computational power were only proven recently (SODA 2014). These results, as well as ours, exemplify the intricate connections between computation and geometry that can occur in self-assembly. In this model, tiles can stick to an existing assembly as soon as one of their sides matches the existing assembly. This feature contrasts with the general cooperative model, where it can be required that tiles match on emph{several} of their sides in order to bind. In order to describe our algorithms, we also introduce a generalization of regular expressions called Baggins expressions. Finally, we compare this model to other automata-theoretic models.

Full work available at URL: https://arxiv.org/abs/1406.6889

Recommendations

• The non-cooperative tile assembly model is not intrinsically universal or capable of bounded Turing machine simulation
• Intrinsic universality in tile self-assembly requires cooperation
• Universal computation with arbitrary polyomino tiles in non-cooperative self-assembly
• The power of nondeterminism in self-assembly

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Other nonclassical models of computation (68Q09)

Cites Work

• The program-size complexity of self-assembled squares (extended abstract)
• Temperature 1 self-assembly: deterministic assembly in 3D and probabilistic assembly in 2D
• Families of prudent self-avoiding walks

Cited In (2)

• Non-determinism reduces construction time in active self-assembly using an insertion primitive
• Title not available (Why is that?)

This page was built for publication: Non-cooperative algorithms in self-assembly

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2945574)