Running time and program size for self-assembled squares

DOI10.1145/380752.380881MaRDI QIDQ5176033zbMATH OpenOpenAlexFDO

Authors Leonard M. Adleman, Qi Cheng, Ashish Goel, Ming-Deh A. Huang

Publication date 27 February 2015

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

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

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Recommendations

• Complexity of Self‐Assembled Shapes
• The program-size complexity of self-assembled squares (extended abstract)
• Program size and temperature in self-assembly
• Self-assemblying Classes of Shapes with a Minimum Number of Tiles, and in Optimal Time
• Program size and temperature in self-assembly

Cites work

• A constant-factor approximation algorithm for the \(k\)-median problem (extended abstract)

Cited in

(68)

• The power of duples (in self-assembly): it's not so hip to be square
• Networks of picture processors as problem solvers
• Optimal staged self-assembly of general shapes
• Identifying shapes using self-assembly
• Tile complexity of approximate squares
• Tilt assembly: algorithms for micro-factories that build objects with uniform external forces
• Nearly constant tile complexity for any shape in two-handed tile assembly
• Self-assembly of and optimal encoding within thin rectangles at temperature-1 in 3D
• On the effects of hierarchical self-assembly for reducing program-size complexity
• Activatable tiles for compact robust programmable molecular assembly and other applications
• Reducing tile complexity for the self-assembly of scaled shapes through temperature programming
• Turing patterns with Turing machines: emergence and low-level structure formation
• An introduction to tile-based self-assembly and a survey of recent results
• Self assembly of rectangular shapes on concentration programming and probabilistic tile assembly models
• Exploring programmable self-assembly in non-DNA based molecular computing
• 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
• 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
• Optimizing tile concentrations to minimize errors and time for DNA tile self-assembly systems
• Triangular tile self-assembly systems
• Randomized Self Assembly of Rectangular Nano Structures
• Exact shapes and Turing universality at temperature 1 with a single negative glue
• A brief tour of theoretical tile self-assembly
• The program-size complexity of self-assembled squares (extended abstract)
• Counting infinitely by oritatami co-transcriptional folding
• A Limit to the Power of Multiple Nucleation in Self-assembly
• Self-correcting Self-assembly: Growth Models and the Hammersley Process
• 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
• Time Optimal Self-assembly for 2D and 3D Shapes: The Case of Squares and Cubes
• Self-assembling rulers for approximating generalized Sierpinski carpets
• Synthesizing minimal tile sets for complex patterns in the framework of patterned DNA self-assembly
• Program size and temperature in self-assembly
• Iterative self-assembly with dynamic strength transformation and temperature control
• Optimal program-size complexity for self-assembled squares at temperature 1 in 3D
• 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
• Activatable Tiles: Compact, Robust Programmable Assembly and Other Applications
• Toward Minimum Size Self-Assembled Counters
• Self-assembly of decidable sets
• Parallelism and time in hierarchical self-assembly
• Parallelism and time in hierarchical self-assembly
• Improved lower and upper bounds on the tile complexity of uniquely self-assembling a thin rectangle non-cooperatively in 3D
• Resiliency to multiple nucleation in temperature-1 self-assembly
• A minimal requirement for self-assembly of lines in polylogarithmic time
• Counting infinitely by oritatami co-transcriptional folding
• 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
• Self-assembly of infinite structures: a survey
• Linear Bounds on the Size of Conformations in Greedy Deterministic Oritatami
• The need for seed (in the abstract Tile Assembly Model)
• Complexity of graph self-assembly in accretive systems and self-destructible systems
• On the simulation power of surface chemical reaction networks
• Self-assembly of patterns in the abstract tile assembly model
• 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

This page was built for publication: Running time and program size for self-assembled squares

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5176033)