Complexity classes for self-assembling flexible tiles

DOI10.1016/J.TCS.2008.09.054MaRDI QIDQ1004079zbMATH OpenOpenAlexFDO

Authors Nataşa Jonoska, Gregory Loren McColm

Publication date 2 March 2009

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2008.09.054

zbMATH Keywords

self-assemblyassembling complexescomplexity classes of self-assemblyDNA junction moleculesDNA-based graph structures

Mathematics Subject Classification ID

Protein sequences, DNA sequences (92D20) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• Self-assemblying Classes of Shapes with a Minimum Number of Tiles, and in Optimal Time
• Unconventional Computation
• Complexity of Self‐Assembled Shapes
• DNA Computing
• On Times to Compute Shapes in 2D Tile Self-assembly
• Computing in continuous space with self-assembling polygonal tiles (extended abstract)
• Computability and Complexity in Self-assembly

Cites work

• scientific article; zbMATH DE number 3474957 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1241374 (Why is no real title available?)
• scientific article; zbMATH DE number 1342100 (Why is no real title available?)
• scientific article; zbMATH DE number 2081010 (Why is no real title available?)
• Combinatorial optimization problems in self-assembly
• DNA Computing
• Expectation and Variance of Self-assembled Graph Structures
• Flexible Versus Rigid Tile Assembly
• Spectrum of a Pot for DNA Complexes
• The complexity of theorem-proving procedures
• The polynomial-time hierarchy
• The program-size complexity of self-assembled squares (extended abstract)
• Unconventional Computation

Cited in

(16)

• Graph-theoretic formalization of hybridization in DNA sticker complexes
• An introduction to tile-based self-assembly and a survey of recent results
• Flexible Versus Rigid Tile Assembly
• Counter machines and crystallographic structures
• Spectrum of a Pot for DNA Complexes
• Self-assembly of 3-D structures using 2-D folding tiles
• Self-assembly of 3-D structures using 2-D folding tiles
• On stoichiometry for the assembly of flexible tile DNA complexes
• Design formalism for DNA self-assembly of polyhedral skeletons using rigid tiles
• Unconventional Computation
• The program-size complexity of self-assembled squares (extended abstract)
• Tile Complexity of Linear Assemblies
• Parallel Computation Using Active Self-assembly
• scientific article; zbMATH DE number 1738642 (Why is no real title available?)
• Parallel computation using active self-assembly
• Improved lower and upper bounds on the tile complexity of uniquely self-assembling a thin rectangle non-cooperatively in 3D

This page was built for publication: Complexity classes for self-assembling flexible tiles

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