The program-size complexity of self-assembled squares (extended abstract)

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

Mathematics Subject Classification ID

Biochemistry, molecular biology (92C40) Analysis of algorithms and problem complexity (68Q25)

Cited In (only showing first 100 items - show all)

• Tilt assembly: algorithms for micro-factories that build objects with uniform external forces
• Randomized Self Assembly of Rectangular Nano Structures
• Non-explosivity of stochastically modeled reaction networks that are complex balanced
• Polyomino-safe DNA self-assembly via block replacement
• Robust self-assembly of graphs
• 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
• 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
• On the effects of hierarchical self-assembly for reducing program-size complexity
• Optimal program-size complexity for self-assembly at temperature 1 in 3D
• Path finding in the tile assembly model
• 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
• Centralised connectivity-preserving transformations for programmable matter: a minimal seed approach
• Centralised connectivity-preserving transformations for programmable matter: a minimal seed approach
• Improved Leader Election for Self-organizing Programmable Matter
• Fractal dimension of assemblies in the abstract tile assembly model
• The complexity of multiple handed self-assembly
• 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
• Self-assembly of 4-sided fractals in the two-handed tile assembly model
• Universal computation and optimal construction in the chemical reaction network-controlled tile assembly model
• Non-cooperative algorithms in self-assembly
• A minimal requirement for self-assembly of lines in polylogarithmic time
• Self-assembly of Discrete Self-similar Fractals
• Robust Self-assembly of Graphs
• Computational modelling of the kinetic tile assembly model using a rule-based approach
• Staged self-assembly and polyomino context-free grammars
• Self-assembly of shapes at constant scale using repulsive forces
• Counting infinitely by oritatami co-transcriptional folding
• Triangular tile self-assembly systems
• Nondeterministic polynomial time factoring in the tile assembly model
• Replication of Arbitrary Hole-Free Shapes via Self-assembly with Signal-Passing Tiles
• A brief tour of theoretical tile self-assembly
• On the complexity of graph self-assembly in accretive systems
• Self-assembly of any shape with constant tile types using high temperature
• Parallel computation using active self-assembly
• Reflections on tiles (in self-assembly)
• Improved lower and upper bounds on the tile complexity of uniquely self-assembling a thin rectangle non-cooperatively in 3D
• Toward minimum size self-assembled counters
• Expectation and Variance of Self-assembled Graph Structures
• Theory of tailor automata
• Parallelism and time in hierarchical self-assembly
• Geometric tiles and powers and limitations of geometric hindrance in self-assembly
• On geometric shape construction via growth operations
• Pushing lines helps: efficient universal centralised transformations for programmable matter
• 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
• The impacts of dimensionality, diffusion, and directedness on intrinsic cross-model simulation in tile-based self-assembly
• Forming tile shapes with simple robots
• Linear Bounds on the Size of Conformations in Greedy Deterministic Oritatami
• Unique assembly verification in two-handed self-assembly
• The need for seed (in the abstract Tile Assembly Model)
• Particle-based assembly using precise global control
• DNA algorithms for fractal construction—an application of theSInsDelPsystem
• Simplifying the role of signals in tile self-assembly
• Network Constructors: A Model for Programmable Matter
• Transformations and Preservation of Self-assembly Dynamics through Homotheties
• Particle-based assembly using precise global control
• A study on complexity measure of diamond tile self-assembly system
• On efficient connectivity-preserving transformations in a grid
• Distributed transformations of Hamiltonian shapes based on line moves
• Distributed transformations of Hamiltonian shapes based on line moves
• Possibilities of constructing two dimensional pictures in DNA computing: Part II
• Centralised connectivity-preserving transformations by rotation: 3 musketeers for all orthogonal convex shapes
• Optimal staged self-assembly of linear assemblies
• Towards composable computations by RNA co-transcriptional folding: a proof-of-concept demonstration of nested loops in oritatami
• Improving efficiency of 3-SAT-solving tile systems
• On geometric shape construction via growth operations
• Programmable single-stranded architectures for computing
• Iterative self-assembly with dynamic strength transformation and temperature control
• 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

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)