Computability and complexity in self-assembly
From MaRDI portal
Publication:537904
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
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