Improved lower and upper bounds on the tile complexity of uniquely self-assembling a thin rectangle non-cooperatively in 3D

DOI10.1007/S00224-023-10137-9OpenAlexW3045359906MaRDI QIDQ6056633

Scott M. Summers, Logan Withers, David Furcy

Publication date: 30 October 2023

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00224-023-10137-9

zbMATH Keywords

lower bounds self-assembly algorithmic self-assembly tile self-assembly window movie lemma directed tile complexity

Mathematics Subject Classification ID

Discrete geometry (52Cxx) Theory of computing (68Qxx) Designs and configurations (05Bxx)

Cites Work

Unnamed Item
Optimal program-size complexity for self-assembled squares at temperature 1 in 3D
Limitations of self-assembly at temperature 1
Approximate self-assembly of the Sierpinski triangle
Staged self-assembly: nanomanufacture of arbitrary shapes with \(O(1)\) glues
Strict self-assembly of discrete Sierpinski triangles
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
Self-assembly of and optimal encoding within thin rectangles at temperature-1 in 3D
Self-assembly with Geometric Tiles
Exact Shapes and Turing Universality at Temperature 1 with a Single Negative Glue
The program-size complexity of self-assembled squares (extended abstract)
Computing in continuous space with self-assembling polygonal tiles (extended abstract)
The non-cooperative tile assembly model is not intrinsically universal or capable of bounded Turing machine simulation
The program-size complexity of self-assembled paths
Running time and program size for self-assembled squares
Complexities for Generalized Models of Self-Assembly
Universal Computation with Arbitrary Polyomino Tiles in Non-Cooperative Self-Assembly
Intrinsic universality in tile self-assembly requires cooperation
Complexity of Self‐Assembled Shapes

This page was built for publication: Improved lower and upper bounds on the tile complexity of uniquely self-assembling a thin rectangle non-cooperatively in 3D