Complexity classes for self-assembling flexible tiles

DOI10.1016/j.tcs.2008.09.054zbMath1169.68019OpenAlexW2050604952MaRDI 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-assemblyassembling complexescomplexity classes of self-assemblyDNA junction moleculesDNA-based graph structures

Mathematics Subject Classification ID

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

Related Items

Design formalism for DNA self-assembly of polyhedral skeletons using rigid tiles, Parallel Computation Using Active Self-assembly, Counter machines and crystallographic structures, Parallel computation using active self-assembly, On stoichiometry for the assembly of flexible tile DNA complexes, 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

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