Self-assembly of decidable sets

DOI10.1007/s11047-010-9218-9zbMath1217.68097OpenAlexW1972005206MaRDI QIDQ553922

Matthew J. Patitz, Scott M. Summers

Publication date: 28 July 2011

Published in: Natural Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s11047-010-9218-9

zbMATH Keywords

universalitydecidabilityDNA computingcomputabilityself-assemblyspace complexitytile assembly

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Combinatorial aspects of tessellation and tiling problems (05B45)

Related Items

Fractal dimension of assemblies in the abstract tile assembly model, Strict self-assembly of fractals using multiple hands, 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, Replication of Arbitrary Hole-Free Shapes via Self-assembly with Signal-Passing Tiles, Binary pattern tile set synthesis is NP-hard, Doubles and negatives are positive (in self-assembly), An introduction to tile-based self-assembly and a survey of recent results

Cites Work

• Unnamed Item
• Unnamed Item
• Staged self-assembly: nanomanufacture of arbitrary shapes with \(O(1)\) glues
• Strict self-assembly of discrete Sierpinski triangles
• The program-size complexity of self-assembled squares (extended abstract)
• Randomized Self-assembly for Approximate Shapes
• Reducing tile complexity for self-assembly through temperature programming
• The Undecidability of the Infinite Ribbon Problem: Implications for Computing by Self-Assembly
• A Domain-Specific Language for Programming in the Tile Assembly Model
• Randomized Self-Assembly for Exact Shapes
• Running time and program size for self-assembled squares
• Complexities for Generalized Models of Self-Assembly
• Self-assemblying Classes of Shapes with a Minimum Number of Tiles, and in Optimal Time
• Complexity of Self‐Assembled Shapes