Computability and complexity in self-assembly

DOI10.1007/s00224-010-9252-0zbMath1217.68095OpenAlexW2013397449MaRDI QIDQ537904

James I. Lathrop, Matthew J. Patitz, Scott M. Summers, Jack H. Lutz

Publication date: 23 May 2011

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00224-010-9252-0

zbMATH Keywords

computational complexitycomputabilitymolecular computingself-assembly

Mathematics Subject Classification ID

Recursively (computably) enumerable sets and degrees (03D25) Tilings in (2) dimensions (aspects of discrete geometry) (52C20)

Related Items

Fractal dimension of assemblies in the abstract tile assembly model, Universality in Molecular and Cellular Computing, The power of duples (in self-assembly): it's not so hip to be square, Replication of Arbitrary Hole-Free Shapes via Self-assembly with Signal-Passing Tiles, Identifying shapes using self-assembly, Counting infinitely by oritatami co-transcriptional folding, Cold dynamics in cellular automata: a tutorial, A Study on Complexity Measure of Diamond Tile Self-assembly System, Binary pattern tile set synthesis is NP-hard, Doubles and negatives are positive (in self-assembly), Geometric tiles and powers and limitations of geometric hindrance in self-assembly, Freezing, Bounded-Change and Convergent Cellular Automata, An introduction to tile-based self-assembly and a survey of recent results

Cites Work

• Unnamed Item
• Strict self-assembly of discrete Sierpinski triangles
• The program-size complexity of self-assembled squares (extended abstract)
• On the time and space complexity of computation using write-once memory or is pen really much worse than pencil?
• On the Computational Complexity of Algorithms
• Complexity of Self‐Assembled Shapes