Tile Complexity of Linear Assemblies

DOI10.1137/110822487MaRDI QIDQ3143302zbMATH OpenOpenAlexFDO

Authors Harish Chandran, Nikhil Gopalkrishnan, J. Reif

Publication date 29 November 2012

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/110822487

zbMATH Keywords

tile assembly modelself-assemblyDNA tilestile complexityWang tilings\(\kappa\)-pad systemslinear assembliesprobabilistic tile assembly model

Mathematics Subject Classification ID

Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Combinatorics in computer science (68R05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10)

Recommendations

• The Tile Complexity of Linear Assemblies
• Nearly constant tile complexity for any shape in two-handed tile assembly
• Tile complexity of approximate squares
• Solving NP-complete problems in the tile assembly model
• Nondeterministic polynomial time factoring in the tile assembly model
• Aspects of a multivariate complexity analysis for rectangle tiling
• Complexity classes for self-assembling flexible tiles
• Complexity of tile rotation problems

Cited in

(9)

• Aspects of a multivariate complexity analysis for rectangle tiling
• Flipping tiles: concentration independent coin flips in tile self-assembly
• Nearly constant tile complexity for any shape in two-handed tile assembly
• DNA Computing
• Tile complexity of approximate squares
• Optimal staged self-assembly of linear assemblies
• Program size and temperature in self-assembly
• The Tile Complexity of Linear Assemblies
• Concentration independent random number generation in tile self-assembly

This page was built for publication: Tile Complexity of Linear Assemblies

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3143302)