Running time and program size for self-assembled squares
From MaRDI portal
Publication:5176033
DOI10.1145/380752.380881zbMath1323.68267OpenAlexW1981863124MaRDI QIDQ5176033
Ashish Goel, Qi Cheng, Leonard M. Adleman, 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
Analysis of algorithms and problem complexity (68Q25) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)
Related Items
Exploring programmable self-assembly in non-DNA based molecular computing ⋮ Triangular and Hexagonal Tile Self-assembly Systems ⋮ Self assembly of rectangular shapes on concentration programming and probabilistic tile assembly models ⋮ Optimal self-assembly of finite shapes at temperature 1 in 3D ⋮ A Brief Tour of Theoretical Tile Self-Assembly ⋮ The power of duples (in self-assembly): it's not so hip to be square ⋮ Self-assembling rulers for approximating generalized Sierpinski carpets ⋮ Arithmetic computation in the tile assembly model: addition and multiplication ⋮ Synthesizing minimal tile sets for complex patterns in the framework of patterned DNA 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 ⋮ 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 ⋮ 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 ⋮ Linear Bounds on the Size of Conformations in Greedy Deterministic Oritatami ⋮ Reducing tile complexity for the self-assembly of scaled shapes through temperature programming ⋮ The need for seed (in the abstract Tile Assembly Model) ⋮ Complexity of graph self-assembly in accretive systems and self-destructible systems ⋮ Tile complexity of approximate squares ⋮ Nondeterministic polynomial time factoring in the tile assembly model ⋮ Solving NP-complete problems in the tile assembly model ⋮ A Limit to the Power of Multiple Nucleation in Self-assembly ⋮ On the complexity of graph self-assembly in accretive systems ⋮ Counting Infinitely by Oritatami Co-transcriptional Folding ⋮ Toward minimum size self-assembled counters ⋮ Staged self-assembly: nanomanufacture of arbitrary shapes with \(O(1)\) glues ⋮ Program size and temperature in self-assembly ⋮ Tilt assembly: algorithms for micro-factories that build objects with uniform external forces ⋮ Networks of picture processors as problem solvers ⋮ On the effects of hierarchical self-assembly for reducing program-size complexity ⋮ 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 ⋮ Iterative Self-assembly with Dynamic Strength Transformation and Temperature Control ⋮ Fast arithmetic in algorithmic self-assembly ⋮ Staged self-assembly and polyomino context-free grammars ⋮ 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 ⋮ Parallelism and Time in Hierarchical Self-Assembly ⋮ Polyomino-safe DNA self-assembly via block replacement ⋮ Self-assembly of decidable sets ⋮ 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 ⋮ 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 ⋮ 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 ⋮ Exact Shapes and Turing Universality at Temperature 1 with a Single Negative Glue ⋮ Activatable tiles for compact robust programmable molecular assembly and other applications ⋮ 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 ⋮ Resiliency to Multiple Nucleation in Temperature-1 Self-Assembly ⋮ Time Complexity of Computation and Construction in the Chemical Reaction Network-Controlled Tile Assembly Model ⋮ Unnamed Item ⋮ Turing patterns with Turing machines: emergence and low-level structure formation ⋮ An introduction to tile-based self-assembly and a survey of recent results
Cites Work
