Non-cooperatively Assembling Large Structures

Abstract : Algorithmic self-assembly is the study of the local, distributed, asynchronous algorithms ran by molecules to self-organise, in particular during crystal growth. The general cooperative model, also called temperature 2, uses synchronisation to simulate Turing machines, build shapes using the smallest possible amount of tile types, and other algorithmic tasks. However, in the non-cooperative (temperature 1) model, the growth process is entirely asynchronous, and mostly relies on geometry. Even though the model looks like a generalisation of finite automata to two dimensions, its 3D generalisation is capable of performing arbitrary (Turing) computation [SODA 2011], and of universal simulations [SODA 2014], whereby a single 3D non-cooperative tileset can simulate the dynamics of all possible 3D non-cooperative systems, up to a constant scaling factor. However, the original 2D non-cooperative model is not capable of universal simulations [STOC 2017], and the question of its computational power is still widely open and it is conjectured to be weaker than temperature or its 3D counterpart. Here, we show an unexpected result, namely that this model can reliably grow assemblies of diameter$\varTheta (n \log n)$ with only n tile types, which is the first asymptotically efficient positive construction.
Keywords :
Document type :
Conference papers
Domain :

https://hal.archives-ouvertes.fr/hal-02966179
Contributor : Frédéric Davesne <>
Submitted on : Tuesday, October 13, 2020 - 8:04:03 PM
Last modification on : Thursday, October 15, 2020 - 3:57:54 AM

Citation

Pierre-Étienne Meunier, Damien Regnault. Non-cooperatively Assembling Large Structures. 25th International Conference on DNA Computing and Molecular Programming (DNA 2019), Aug 2019, Seattle, United States. pp.120--139, ⟨10.1007/978-3-030-26807-7_7⟩. ⟨hal-02966179⟩

Record views