The program-size complexity of self-assembled squares (extended abstract)
From MaRDI portal
Publication:3192015
DOI10.1145/335305.335358zbMATH Open1296.68051OpenAlexW1983241546MaRDI QIDQ3192015FDOQ3192015
Authors: Paul Wilhelm Karl Rothemund, Erik Winfree 
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
Recommendations
- Running time and program size for self-assembled squares
- Optimal program-size complexity for self-assembled squares at temperature 1 in 3D
- The program-size complexity of self-assembled paths
- Complexity of Compact Proofreading for Self-assembled Patterns
- Optimal program-size complexity for self-assembly at temperature 1 in 3D
- On the effects of hierarchical self-assembly for reducing program-size complexity
- Computability and complexity in self-assembly
- Computability and Complexity in Self-assembly
- Complexity classes for self-assembling flexible tiles
Cited In (only showing first 100 items - show all)
- Enumeration approach to computing chemical equilibria
- Synthesizing minimal tile sets for complex patterns in the framework of patterned DNA self-assembly
- Search methods for tile sets in patterned DNA self-assembly
- Step-wise tile assembly with a constant number of tile types
- Running time and program size for self-assembled squares
- An introduction to tile-based self-assembly and a survey of recent results
- Turing patterns with Turing machines: emergence and low-level structure formation
- Self-correcting Self-assembly: Growth Models and the Hammersley Process
- Complexity of graph self-assembly in accretive systems and self-destructible systems
- Efficient algorithms for self assembling non-rectangular nano structures
- Distributed agreement in tile self-assembly
- 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
- Computability and complexity in self-assembly
- Self-assembly of decidable sets
- The emerging discipline of biomolecular computation in the US
- Limitations of self-assembly at temperature 1
- Approximate self-assembly of the Sierpinski triangle
- Error suppression mechanisms for DNA tile self-assembly and their simulation
- Exploring programmable self-assembly in non-DNA based molecular computing
- Arithmetic computation in the tile assembly model: addition and multiplication
- 3-color bounded patterned self-assembly (extended abstract)
- Flipping tiles: concentration independent coin flips in tile self-assembly
- Solving NP-complete problems in the tile assembly model
- Staged self-assembly: nanomanufacture of arbitrary shapes with \(O(1)\) glues
- Self-assembly of discrete self-similar fractals
- Complexity classes for self-assembling flexible tiles
- Strict self-assembly of discrete Sierpinski triangles
- Pictures worth a thousand tiles, a geometrical programming language for self-assembly
- Nearly constant tile complexity for any shape in two-handed tile assembly
- Simple and efficient local codes for distributed stable network construction
- 3-color bounded patterned self-assembly
- On stoichiometry for the assembly of flexible tile DNA complexes
- Optimizing tile concentrations to minimize errors and time for DNA tile self-assembly systems
- Efficient 3-SAT algorithms in the tile assembly model
- Exact shapes and Turing universality at temperature 1 with a single negative glue
- Synthesizing small and reliable tile sets for patterned DNA self-assembly
- Triangular and hexagonal tile self-assembly systems
- Parallelism and time in hierarchical self-assembly
- Identifying shapes using self-assembly
- Negative interactions in irreversible self-assembly
- Doubles and negatives are positive (in self-assembly)
- Tile complexity of approximate squares
- Less haste, less waste: on recycling and its limits in strand displacement systems
- Self-assembly of infinite structures: a survey
- Reducing tile complexity for the self-assembly of scaled shapes through temperature programming
- On the complexity of asynchronous freezing cellular automata
- Resiliency to multiple nucleation in temperature-1 self-assembly
- Resiliency to multiple nucleation in temperature-1 self-assembly
- Hierarchical self assembly of patterns from the Robinson tilings: DNA tile design in an enhanced tile assembly model
- Simple evolution of complex crystal species
- Localized hybridization circuits
- Self-assembling rulers for approximating generalized Sierpinski carpets
- Synthesizing Minimal Tile Sets for Patterned DNA Self-assembly
- Computability and Complexity in Self-assembly
- A Limit to the Power of Multiple Nucleation in Self-assembly
- Self-assembly of Decidable Sets
- Optimal self-assembly of finite shapes at temperature 1 in 3D
- A Self-assembly Model of Time-Dependent Glue Strength
- Complexity of Graph Self-assembly in Accretive Systems and Self-destructible Systems
- Complexity of Compact Proofreading for Self-assembled Patterns
- DNA Computing
- Polyomino-Safe DNA Self-assembly via Block Replacement
- Time Optimal Self-assembly for 2D and 3D Shapes: The Case of Squares and Cubes
- Program size and temperature in self-assembly
- Parallel Computation Using Active Self-assembly
- Polyominoes simulating arbitrary-neighborhood zippers and tilings
- Self-assembly of and optimal encoding within thin rectangles at temperature-1 in 3D
- 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
- Connectivity preserving network transformers
- New geometric algorithms for fully connected staged self-assembly
- Geometric tiles and powers and limitations of geometric hindrance in self-assembly
- Tilt assembly: algorithms for micro-factories that build objects with uniform external forces
- Randomized Self Assembly of Rectangular Nano Structures
- On geometric shape construction via growth operations
- Non-explosivity of stochastically modeled reaction networks that are complex balanced
- Pushing lines helps: efficient universal centralised transformations for programmable matter
- Polyomino-safe DNA self-assembly via block replacement
- Robust self-assembly of graphs
- Connecting the Dots: Molecular Machinery for Distributed Robotics
- Tight bounds on the directed tile complexity of a just-barely 3D \(2 \times N\) rectangle at temperature 1
- Producibility in hierarchical self-assembly
- Size-separable tile self-assembly: a tight bound for temperature-1 mismatch-free systems
- Self assembly of rectangular shapes on concentration programming and probabilistic tile assembly models
- The impacts of dimensionality, diffusion, and directedness on intrinsic cross-model simulation in tile-based self-assembly
- Pushing lines helps: efficient universal centralised transformations for programmable matter
- On the transformation capability of feasible mechanisms for programmable matter
- Optimal staged self-assembly of general shapes
- Unraveling simplicity in elementary cellular automata
- Forming tile shapes with simple robots
- On the effects of hierarchical self-assembly for reducing program-size complexity
- Linear Bounds on the Size of Conformations in Greedy Deterministic Oritatami
- Optimal program-size complexity for self-assembly at temperature 1 in 3D
- Path finding in the tile assembly model
- Unique assembly verification in two-handed self-assembly
- Building squares with optimal state complexity in restricted active self-assembly
- Time complexity of computation and construction in the chemical reaction network-controlled tile assembly model
- The need for seed (in the abstract Tile Assembly Model)
This page was built for publication: The program-size complexity of self-assembled squares (extended abstract)
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3192015)
