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

\(\kappa\)-pad systemsDNA tileslinear assembliesprobabilistic tile assembly modelself-assemblytile assembly modeltile complexityWang tilings

Mathematics Subject Classification ID

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

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)

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

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)