The program-size complexity of self-assembled squares (extended abstract)
From MaRDI portal
Publication:3192015
DOI10.1145/335305.335358zbMath1296.68051MaRDI 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
Related Items
Turing patterns with Turing machines: emergence and low-level structure formation, An introduction to tile-based self-assembly and a survey of recent results, Exploring programmable self-assembly in non-DNA based molecular computing, Self-assembling rulers for approximating generalized Sierpinski carpets, Synthesizing minimal tile sets for complex patterns in the framework of patterned DNA self-assembly, Enumeration approach to computing chemical equilibria, Search methods for tile sets in patterned DNA self-assembly, 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 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, 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, Self-assembly of decidable sets, Limitations of self-assembly at temperature 1, Self-assembly of infinite structures: a survey, Complexity of graph self-assembly in accretive systems and self-destructible systems, Polyominoes simulating arbitrary-neighborhood zippers and tilings, Approximate self-assembly of the Sierpinski triangle, The emerging discipline of biomolecular computation in the US, Error suppression mechanisms for DNA tile self-assembly and their simulation, Arithmetic computation in the tile assembly model: addition and multiplication, Nondeterministic polynomial time factoring in the tile assembly model, Solving NP-complete problems in the tile assembly model, 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, Polyomino-safe DNA self-assembly via block replacement, Self-assembly of discrete self-similar fractals, Robust self-assembly of graphs, Complexity classes for self-assembling flexible tiles, Strict self-assembly of discrete Sierpinski triangles, Path finding in the tile assembly model, Pictures worth a thousand tiles, a geometrical programming language for self-assembly, Optimal self-assembly of finite shapes at temperature 1 in 3D, 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, Computational modelling of the kinetic tile assembly model using a rule-based approach, On the transformation capability of feasible mechanisms for programmable matter, Optimal staged self-assembly of general shapes, On stoichiometry for the assembly of flexible tile DNA complexes, Step-wise tile assembly with a constant number of tile types, Identifying shapes using self-assembly, Tile complexity of approximate squares, Negative interactions in irreversible self-assembly, Non-explosivity of stochastically modeled reaction networks that are complex balanced, Nearly constant tile complexity for any shape in two-handed tile assembly, 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, Reflections on tiles (in self-assembly), Theory of tailor automata, Reducing tile complexity for the self-assembly of scaled shapes through temperature programming, 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, Resiliency to Multiple Nucleation in Temperature-1 Self-Assembly, Time Complexity of Computation and Construction in the Chemical Reaction Network-Controlled Tile Assembly Model, Triangular and Hexagonal Tile Self-assembly Systems, Replication of Arbitrary Hole-Free Shapes via Self-assembly with Signal-Passing Tiles, Non-cooperative Algorithms in Self-assembly, 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, Network Constructors: A Model for Programmable Matter, 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, 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, A Brief Tour of Theoretical Tile Self-Assembly, Possibilities of constructing two dimensional pictures in DNA computing: Part II, Computability and Complexity in Self-assembly, 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, Self-correcting Self-assembly: Growth Models and the Hammersley Process, Expectation and Variance of Self-assembled Graph Structures, Complexity of Graph Self-assembly in Accretive Systems and Self-destructible Systems, A Self-assembly Model of Time-Dependent Glue Strength, Complexity of Compact Proofreading for Self-assembled Patterns, Connecting the Dots: Molecular Machinery for Distributed Robotics, Polyomino-Safe DNA Self-assembly via Block Replacement, Robust Self-assembly of Graphs, Time Optimal Self-assembly for 2D and 3D Shapes: The Case of Squares and Cubes, Self-assembly of Discrete Self-similar Fractals, Parallel Computation Using Active Self-assembly, 3-Color Bounded Patterned Self-assembly, Iterative Self-assembly with Dynamic Strength Transformation and Temperature Control, DNA algorithms for fractal construction—an application of theSInsDelPsystem, Unnamed Item, Parallelism and Time in Hierarchical Self-Assembly, Simple and efficient local codes for distributed stable network construction
