Limitations of self-assembly at temperature 1

DOI10.1016/j.tcs.2010.08.023zbMath1234.05052OpenAlexW2302577799MaRDI QIDQ616501

Matthew J. Patitz, David Doty, Scott M. Summers

Publication date: 10 January 2011

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2010.08.023

zbMATH Keywords

regular languagegrid graphsemilinear settile self-assemblydiscrete Sierpinski trianglegeneral-purpose computationtile assembly system

Mathematics Subject Classification ID

Related Items (21)

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 ⋮ ASYNCHRONOUS SIGNAL PASSING FOR TILE SELF-ASSEMBLY: FUEL EFFICIENT COMPUTATION AND EFFICIENT ASSEMBLY OF SHAPES ⋮ Optimal Program-Size Complexity for Self-Assembly at Temperature 1 in 3D ⋮ Self-assembly of infinite structures: a survey ⋮ 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 ⋮ Linear Bounds on the Size of Conformations in Greedy Deterministic Oritatami ⋮ On the teaching complexity of linear sets ⋮ Tile complexity of approximate squares ⋮ Optimal program-size complexity for self-assembled squares at temperature 1 in 3D ⋮ Doubles and negatives are positive (in self-assembly) ⋮ On the Boundedness Property of Semilinear Sets ⋮ 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 ⋮ Exact Shapes and Turing Universality at Temperature 1 with a Single Negative Glue ⋮ Reflections on tiles (in self-assembly) ⋮ On the Teaching Complexity of Linear Sets ⋮ Resiliency to Multiple Nucleation in Temperature-1 Self-Assembly ⋮ Freezing, Bounded-Change and Convergent Cellular Automata ⋮ An introduction to tile-based self-assembly and a survey of recent results

Cites Work

• Strict self-assembly of discrete Sierpinski triangles
• The program-size complexity of self-assembled squares (extended abstract)
• Randomized Self-assembly for Approximate Shapes
• Self-assembly of Decidable Sets
• The Undecidability of the Infinite Ribbon Problem: Implications for Computing by Self-Assembly
• Reversal-Bounded Multicounter Machines and Their Decision Problems
• Randomized Self-Assembly for Exact Shapes
• Mathematical Foundations of Computer Science 2005
• Unnamed Item
• Unnamed Item

This page was built for publication: Limitations of self-assembly at temperature 1