Complexity classes for self-assembling flexible tiles

DOI10.1016/j.tcs.2008.09.054zbMath1169.68019MaRDI QIDQ1004079

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-assembly; assembling complexes; complexity classes of self-assembly; DNA junction molecules; DNA-based graph structures

Mathematics Subject Classification ID

68Q10: Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)

92D20: Protein sequences, DNA sequences

68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)

Related Items

Parallel Computation Using Active Self-assembly, Self-assembly of 3-D structures using 2-D folding tiles, Graph-theoretic formalization of hybridization in DNA sticker complexes, An introduction to tile-based self-assembly and a survey of recent results, On stoichiometry for the assembly of flexible tile DNA complexes, Counter machines and crystallographic structures, Parallel computation using active self-assembly, Design formalism for DNA self-assembly of polyhedral skeletons using rigid tiles

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The polynomial-time hierarchy
• The program-size complexity of self-assembled squares (extended abstract)
• Combinatorial optimization problems in self-assembly
• Expectation and Variance of Self-assembled Graph Structures
• Flexible Versus Rigid Tile Assembly
• Spectrum of a Pot for DNA Complexes
• Unconventional Computation
• DNA Computing
• The complexity of theorem-proving procedures