Intrinsic universality in tile self-assembly requires cooperation

DOI10.1137/1.9781611973402.56zbMath1422.68071arXiv1304.1679OpenAlexW2949497251MaRDI 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 (26)

Unraveling simplicity in elementary cellular automata ⋮ Optimal self-assembly of finite shapes at temperature 1 in 3D ⋮ Strict self-assembly of fractals using multiple hands ⋮ The power of duples (in self-assembly): it's not so hip to be square ⋮ Self-assembly of 4-sided fractals in the two-handed tile assembly model ⋮ On the complexity of two-dimensional signed majority cellular automata ⋮ Scaled Tree Fractals Do not Strictly Self-assemble ⋮ The Simulation Powers and Limitations of Hierarchical Self-Assembly Systems ⋮ 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) ⋮ Binary pattern tile set synthesis is NP-hard ⋮ 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 ⋮ Geometric tiles and powers and limitations of geometric hindrance in self-assembly ⋮ Self-assembly of and optimal encoding within thin rectangles at temperature-1 in 3D ⋮ Scaled pier fractals do not strictly self-assemble ⋮ An introduction to tile-based self-assembly and a survey of recent results ⋮ The two-handed tile assembly model is not intrinsically universal

This page was built for publication: Intrinsic universality in tile self-assembly requires cooperation