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

Combinatorial aspects of tessellation and tiling problems (05B45)

Related Items

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

• Unnamed Item
• Unnamed Item
• 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