The Complexity of Fixed-Height Patterned Tile Self-assembly

DOI10.1007/978-3-319-40946-7_21zbMath1379.68122arXiv1604.07190OpenAlexW2469098551MaRDI QIDQ2830225

Andrew Winslow, Shinnosuke Seki

Publication date: 9 November 2016

Published in: International Journal of Foundations of Computer Science, Implementation and Application of Automata (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1604.07190

zbMATH Keywords

polynomial-time algorithmDNA computingNP-hardnessfinite state transducertile self-assemblyDNA patterned tile self-assemblyfixed-height pattern

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cites Work

• Unnamed Item
• Synthesizing minimal tile sets for complex patterns in the framework of patterned DNA self-assembly
• A manually-checkable proof for the NP-hardness of 11-color pattern self-assembly tileset synthesis
• Binary pattern tile set synthesis is NP-hard
• A natural encoding scheme proved probabilistic polynomial complete
• Computing Minimum Tile Sets to Self-Assemble Color Patterns
• Synthesizing Minimal Tile Sets for Patterned DNA Self-assembly
• Complexity Results for Multiprocessor Scheduling under Resource Constraints
• On the complexity of minimum inference of regular sets
• An Introduction to Tile-Based Self-assembly
• Combinatorial Optimization in Pattern Assembly

This page was built for publication: The Complexity of Fixed-Height Patterned Tile Self-assembly