Non-cooperative algorithms in self-assembly

DOI10.1007/978-3-319-21819-9_20MaRDI QIDQ2945574zbMATH OpenOpenAlexFDO

Authors Pierre Meunier

Publication date 14 September 2015

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

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

Mathematics Subject Classification ID

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

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.

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

Cites work

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

Cited in

(3)

• Non-determinism reduces construction time in active self-assembly using an insertion primitive
• Non-cooperatively assembling large structures
• scientific article; zbMATH DE number 6351478 (Why is no real title available?)

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)