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)
- 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
- 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
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)
