Complexity of Self‐Assembled Shapes
From MaRDI portal
Publication:5432361
DOI10.1137/S0097539704446712zbMath1136.68029DBLPjournals/siamcomp/SoloveichikW07OpenAlexW2784847360WikidataQ59328987 ScholiaQ59328987MaRDI QIDQ5432361
Erik Winfree, David Soloveichik
Publication date: 3 January 2008
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/s0097539704446712
Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Tilings in (2) dimensions (aspects of discrete geometry) (52C20) Combinatorial complexity of geometric structures (52C45)
Related Items (66)
Efficient 3-SAT algorithms in the tile assembly model ⋮ Hierarchical self assembly of patterns from the Robinson tilings: DNA tile design in an enhanced tile assembly model ⋮ Optimal self-assembly of finite shapes at temperature 1 in 3D ⋮ Capabilities and limits of compact error resilience methods for algorithmic self-assembly ⋮ Fractal dimension of assemblies in the abstract tile assembly model ⋮ Universality in Molecular and Cellular Computing ⋮ 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 ⋮ Self-assembly of shapes at constant scale using repulsive forces ⋮ Self-assembling rulers for approximating generalized Sierpinski carpets ⋮ Replication of Arbitrary Hole-Free Shapes via Self-assembly with Signal-Passing Tiles ⋮ Universal Computation and Optimal Construction in the Chemical Reaction Network-Controlled Tile Assembly Model ⋮ Optimal Program-Size Complexity for Self-Assembly at Temperature 1 in 3D ⋮ Flipping Tiles: Concentration Independent Coin Flips in Tile Self-Assembly ⋮ 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 ⋮ Identifying shapes using self-assembly ⋮ Resiliency to multiple nucleation in temperature-1 self-assembly ⋮ A coarse-grained model captures the temporal evolution of DNA nanotube length distributions ⋮ Computability and Complexity in Self-assembly ⋮ 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 ⋮ Reducing tile complexity for the self-assembly of scaled shapes through temperature programming ⋮ The need for seed (in the abstract Tile Assembly Model) ⋮ A Study on Complexity Measure of Diamond Tile Self-assembly System ⋮ Unnamed Item ⋮ A Limit to the Power of Multiple Nucleation in Self-assembly ⋮ Self-assembly of Decidable Sets ⋮ Program size and temperature in self-assembly ⋮ Concentration independent random number generation in tile self-assembly ⋮ Tight bounds for active self-assembly using an insertion primitive ⋮ Optimal staged self-assembly of general shapes ⋮ Optimal program-size complexity for self-assembled squares at temperature 1 in 3D ⋮ Nearly constant tile complexity for any shape in two-handed tile assembly ⋮ A minimal requirement for self-assembly of lines in polylogarithmic time ⋮ Approximate self-assembly of the Sierpinski triangle ⋮ Doubles and negatives are positive (in self-assembly) ⋮ Size-separable tile self-assembly: a tight bound for temperature-1 mismatch-free systems ⋮ On aggregation in multiset-based self-assembly of graphs ⋮ Optimization of supply diversity for the self-assembly of simple objects in two and three dimensions ⋮ Efficient algorithms for self assembling non-rectangular nano structures ⋮ Distributed agreement in tile self-assembly ⋮ Computability and complexity in self-assembly ⋮ Parallelism and Time in Hierarchical Self-Assembly ⋮ Particle-based assembly using precise global control ⋮ Self-assembly of discrete self-similar fractals ⋮ Self-assembly of decidable 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 ⋮ Activatable Tiles: Compact, Robust Programmable Assembly and Other Applications ⋮ Error suppression mechanisms for DNA tile self-assembly and their simulation ⋮ Improving Efficiency of 3-SAT-Solving Tile Systems ⋮ Optimizing Tile Concentrations to Minimize Errors and Time for DNA Tile Self-assembly Systems ⋮ Strict self-assembly of discrete Sierpinski triangles ⋮ Complexity of Compact Proofreading for Self-assembled Patterns ⋮ On the complexity of asynchronous freezing cellular automata ⋮ Exact Shapes and Turing Universality at Temperature 1 with a Single Negative Glue ⋮ Unnamed Item ⋮ Connecting the Dots: Molecular Machinery for Distributed Robotics ⋮ Self-assembly of Discrete Self-similar Fractals ⋮ Resiliency to Multiple Nucleation in Temperature-1 Self-Assembly ⋮ A Coarse-Grained Model of DNA Nanotube Population Growth ⋮ Time Complexity of Computation and Construction in the Chemical Reaction Network-Controlled Tile Assembly Model ⋮ Unnamed Item ⋮ A Survey on Analog Models of Computation ⋮ An introduction to tile-based self-assembly and a survey of recent results
This page was built for publication: Complexity of Self‐Assembled Shapes
