Optimal program-size complexity for self-assembled squares at temperature 1 in 3D

DOI10.1007/s00453-016-0147-6zbMath1364.68196OpenAlexW2315676627MaRDI QIDQ524381

David Furcy, Samuel Micka, Scott M. Summers

Publication date: 2 May 2017

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-016-0147-6

zbMATH Keywords

DNA computingoptimal encodingalgorithmic self-assemblyprogram-size complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10)

Related Items

Improved lower and upper bounds on the tile complexity of uniquely self-assembling a thin rectangle non-cooperatively in 3D, Resiliency to multiple nucleation in temperature-1 self-assembly, Self-assembly of and optimal encoding within thin rectangles at temperature-1 in 3D

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Limitations of self-assembly at temperature 1
• Approximate self-assembly of the Sierpinski triangle
• The program-size complexity of self-assembled squares (extended abstract)
• Polyomino-Safe DNA Self-assembly via Block Replacement
• Running time and program size for self-assembled squares
• Complexities for Generalized Models of Self-Assembly
• Complexity of Self‐Assembled Shapes
• An introduction to Kolmogorov complexity and its applications