Intrinsic universality in tile self-assembly requires cooperation

DOI10.1137/1.9781611973402.56zbMath1422.68071arXiv1304.1679MaRDI QIDQ5384017

Andrew Winslow, Pierre-Étienne Meunier, Guillaume Theyssier, Damien Woods, Scott M. Summers, Matthew J. Patitz

Publication date: 20 June 2019

Published in: Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Related Items

Geometric tiles and powers and limitations of geometric hindrance in self-assembly, Improved lower and upper bounds on the tile complexity of uniquely self-assembling a thin rectangle non-cooperatively in 3D, Resiliency to multiple nucleation in temperature-1 self-assembly, Communication complexity meets cellular automata: necessary conditions for intrinsic universality, Building squares with optimal state complexity in restricted active self-assembly, Tight bounds on the directed tile complexity of a just-barely 3D \(2 \times N\) rectangle at temperature 1, Particle computation: complexity, algorithms, and logic, The need for seed (in the abstract Tile Assembly Model), An introduction to tile-based self-assembly and a survey of recent results, The two-handed tile assembly model is not intrinsically universal, Strict self-assembly of fractals using multiple hands, Binary pattern tile set synthesis is NP-hard, Optimal self-assembly of finite shapes at temperature 1 in 3D, The power of duples (in self-assembly): it's not so hip to be square, Nearly constant tile complexity for any shape in two-handed tile assembly, Doubles and negatives are positive (in self-assembly), Fast arithmetic in algorithmic self-assembly, Size-separable tile self-assembly: a tight bound for temperature-1 mismatch-free systems, Parallel computation using active self-assembly, Self-assembly of and optimal encoding within thin rectangles at temperature-1 in 3D, Scaled pier fractals do not strictly self-assemble, Self-assembly of 4-sided fractals in the two-handed tile assembly model, On the complexity of two-dimensional signed majority cellular automata, Unraveling simplicity in elementary cellular automata, Scaled Tree Fractals Do not Strictly Self-assemble, The Simulation Powers and Limitations of Hierarchical Self-Assembly Systems