Computability and complexity in self-assembly

DOI10.1007/s00224-010-9252-0zbMath1217.68095MaRDI 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 complexity; computability; molecular computing; self-assembly

Mathematics Subject Classification ID

03D25: Recursively (computably) enumerable sets and degrees

52C20: Tilings in (2) dimensions (aspects of discrete geometry)

Related Items

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

Cites Work

• 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
• Unnamed Item