The program-size complexity of self-assembled squares (extended abstract)

DOI10.1145/335305.335358zbMath1296.68051OpenAlexW1983241546MaRDI QIDQ3192015

Erik Winfree, Paul Wilhelm Karl Rothemund

Publication date: 26 September 2014

Published in: Proceedings of the thirty-second annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/335305.335358

Mathematics Subject Classification ID

Related Items (only showing first 100 items - show all)

Exploring programmable self-assembly in non-DNA based molecular computing ⋮ Triangular and Hexagonal Tile Self-assembly Systems ⋮ Unraveling simplicity in elementary cellular automata ⋮ Simple evolution of complex crystal species ⋮ Self assembly of rectangular shapes on concentration programming and probabilistic tile assembly models ⋮ 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 ⋮ The complexity of multiple handed self-assembly ⋮ Fractal dimension of assemblies in the abstract tile assembly model ⋮ A Brief Tour of Theoretical Tile Self-Assembly ⋮ Terminating distributed construction of shapes and patterns in a fair solution of automata ⋮ The power of duples (in self-assembly): it's not so hip to be square ⋮ Self-assembly of shapes at constant scale using repulsive forces ⋮ Self-assembly of 4-sided fractals in the two-handed tile assembly model ⋮ Self-assembling rulers for approximating generalized Sierpinski carpets ⋮ Arithmetic computation in the tile assembly model: addition and multiplication ⋮ Replication of Arbitrary Hole-Free Shapes via Self-assembly with Signal-Passing Tiles ⋮ Non-cooperative Algorithms in Self-assembly ⋮ Pushing lines helps: efficient universal centralised transformations for programmable matter ⋮ Synthesizing minimal tile sets for complex patterns in the framework of patterned DNA self-assembly ⋮ Enumeration approach to computing chemical equilibria ⋮ Computational modelling of the kinetic tile assembly model using a rule-based approach ⋮ 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 ⋮ Search methods for tile sets in patterned DNA self-assembly ⋮ Limitations of self-assembly at temperature 1 ⋮ Self-assembly of infinite structures: a survey ⋮ Identifying shapes using self-assembly ⋮ Computability and Complexity in Self-assembly ⋮ Reducing tile complexity for the self-assembly of scaled shapes through temperature programming ⋮ Complexity of graph self-assembly in accretive systems and self-destructible systems ⋮ Tile complexity of approximate squares ⋮ Negative interactions in irreversible self-assembly ⋮ Network Constructors: A Model for Programmable Matter ⋮ Polyominoes simulating arbitrary-neighborhood zippers and tilings ⋮ Nondeterministic polynomial time factoring in the tile assembly model ⋮ Solving NP-complete problems in the tile assembly model ⋮ Transformations and Preservation of Self-assembly Dynamics through Homotheties ⋮ A Limit to the Power of Multiple Nucleation in Self-assembly ⋮ Self-assembly of Decidable Sets ⋮ On the complexity of graph self-assembly in accretive systems ⋮ Toward minimum size self-assembled counters ⋮ Staged self-assembly: nanomanufacture of arbitrary shapes with \(O(1)\) glues ⋮ Program size and temperature in self-assembly ⋮ On the transformation capability of feasible mechanisms for programmable matter ⋮ Tilt assembly: algorithms for micro-factories that build objects with uniform external forces ⋮ On the effects of hierarchical self-assembly for reducing program-size complexity ⋮ Concentration independent random number generation in tile self-assembly ⋮ Non-explosivity of stochastically modeled reaction networks that are complex balanced ⋮ 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 ⋮ New geometric algorithms for fully connected staged self-assembly ⋮ Connectivity preserving network transformers ⋮ Nearly constant tile complexity for any shape in two-handed tile assembly ⋮ Approximate self-assembly of the Sierpinski triangle ⋮ Producibility in hierarchical self-assembly ⋮ Doubles and negatives are positive (in self-assembly) ⋮ Size-separable tile self-assembly: a tight bound for temperature-1 mismatch-free systems ⋮ Parallel computation using active self-assembly ⋮ 3-color bounded patterned self-assembly ⋮ Staged self-assembly and polyomino context-free grammars ⋮ On stoichiometry for the assembly of flexible tile DNA complexes ⋮ Step-wise tile assembly with a constant number of tile types ⋮ 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 ⋮ Polyomino-safe DNA self-assembly via block replacement ⋮ Self-assembly of discrete self-similar fractals ⋮ Robust self-assembly of graphs ⋮ The emerging discipline of biomolecular computation in the US ⋮ Self-assembly of decidable sets ⋮ Self-assembly of and optimal encoding within thin rectangles at temperature-1 in 3D ⋮ 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 ⋮ Synthesizing Minimal Tile Sets for Patterned DNA Self-assembly ⋮ Triangular Tile Self-assembly Systems ⋮ Randomized Self Assembly of Rectangular Nano Structures ⋮ Complexity classes for self-assembling flexible tiles ⋮ Strict self-assembly of discrete Sierpinski triangles ⋮ Self-correcting Self-assembly: Growth Models and the Hammersley Process ⋮ Possibilities of constructing two dimensional pictures in DNA computing: Part II ⋮ Path finding in the tile assembly model ⋮ Pictures worth a thousand tiles, a geometrical programming language for self-assembly ⋮ On the complexity of asynchronous freezing cellular automata ⋮ Localized Hybridization Circuits ⋮ Less Haste, Less Waste: On Recycling and Its Limits in Strand Displacement Systems ⋮ Synthesizing Small and Reliable Tile Sets for Patterned DNA Self-assembly ⋮ Exact Shapes and Turing Universality at Temperature 1 with a Single Negative Glue ⋮ Reflections on tiles (in self-assembly) ⋮ Theory of tailor automata ⋮ Resiliency to Multiple Nucleation in Temperature-1 Self-Assembly ⋮ Time Complexity of Computation and Construction in the Chemical Reaction Network-Controlled Tile Assembly Model ⋮ Turing patterns with Turing machines: emergence and low-level structure formation ⋮ An introduction to tile-based self-assembly and a survey of recent results

This page was built for publication: The program-size complexity of self-assembled squares (extended abstract)