Complexities for Generalized Models of Self-Assembly
From MaRDI portal
Publication:5317208
DOI10.1137/S0097539704445202zbMath1088.68067OpenAlexW1990819744MaRDI QIDQ5317208
Gagan Aggarwal, Pablo Moisset de Espanés, Robert T. Schweller, Qi Cheng, Michael H. Goldwasser, Ming-Yang Kao
Publication date: 16 September 2005
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/s0097539704445202
Analysis of algorithms and problem complexity (68Q25) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Combinatorial aspects of tessellation and tiling problems (05B45) Tilings in (2) dimensions (aspects of discrete geometry) (52C20) Polyominoes (05B50) Combinatorial complexity of geometric structures (52C45)
Related Items
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 ⋮ A Brief Tour of Theoretical Tile Self-Assembly ⋮ Strict self-assembly of fractals using multiple hands ⋮ 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 ⋮ Verification in staged tile self-assembly ⋮ Self-assembly of 4-sided fractals in the two-handed tile assembly model ⋮ Arithmetic computation in the tile assembly model: addition and multiplication ⋮ Reversible Limited Automata ⋮ The Simulation Powers and Limitations of Hierarchical Self-Assembly Systems ⋮ Deterministic polynomial-time algorithms for designing short DNA words ⋮ Universal Computation and Optimal Construction in the Chemical Reaction Network-Controlled Tile Assembly Model ⋮ Flipping Tiles: Concentration Independent Coin Flips in Tile Self-Assembly ⋮ 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 ⋮ Hierarchical self-assembly of fractals with signal-passing tiles ⋮ 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 ⋮ Unique assembly verification in two-handed self-assembly ⋮ The need for seed (in the abstract Tile Assembly Model) ⋮ Simplifying the role of signals in tile self-assembly ⋮ Unnamed Item ⋮ Tile complexity of approximate squares ⋮ Negative interactions in irreversible self-assembly ⋮ Nondeterministic polynomial time factoring in the tile assembly model ⋮ Solving NP-complete problems in the tile assembly model ⋮ Staged self-assembly: nanomanufacture of arbitrary shapes with \(O(1)\) glues ⋮ Program size and temperature in self-assembly ⋮ Networks of picture processors as problem solvers ⋮ On the effects of hierarchical self-assembly for reducing program-size complexity ⋮ Concentration independent random number generation in tile self-assembly ⋮ 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 ⋮ Dipole codes attractively encode glue functions ⋮ Nearly constant tile complexity for any shape in two-handed tile assembly ⋮ Parallel Computation Using Active Self-assembly ⋮ Iterative Self-assembly with Dynamic Strength Transformation and Temperature Control ⋮ Producibility in hierarchical self-assembly ⋮ Fast arithmetic in algorithmic self-assembly ⋮ Parallel computation using active self-assembly ⋮ Signal transmission across tile assemblies: 3D static tiles simulate active self-assembly by 2D signal-passing tiles ⋮ Step-wise tile assembly with a constant number of tile types ⋮ 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 ⋮ Optimal staged self-assembly of linear assemblies ⋮ Self-assembly of decidable sets ⋮ Self-assembly of and optimal encoding within thin rectangles at temperature-1 in 3D ⋮ Randomized Self Assembly of Rectangular Nano Structures ⋮ Path finding in the tile assembly model ⋮ The 4-way deterministic tiling problem is undecidable ⋮ Connecting the Dots: Molecular Machinery for Distributed Robotics ⋮ Polyomino-Safe DNA Self-assembly via Block Replacement ⋮ Time Complexity of Computation and Construction in the Chemical Reaction Network-Controlled Tile Assembly Model ⋮ Unnamed Item ⋮ An introduction to tile-based self-assembly and a survey of recent results ⋮ The two-handed tile assembly model is not intrinsically universal
