2013/08/22 by Mika Göös, Tuomo Lempiäinen, Eugen Czeizler +1
Biochemistry, Genetics and Molecular Biology · Computer Science · Engineering · Mathematics · #Advanced biosensing and bioanalysis techniques #Algorithm #Combinatorics #Computer science #DNA and Biological Computing #Engineering #Materials science #Mathematics #Modular Robots and Swarm Intelligence #Physics #Programming language #Reliability (semiconductor) #Set (abstract data type) #Task (project management) #Tile #acm:68W05 #cs.DS #cs.ET #msc:68W05
paper · pdf · doi:10.1016/j.jcss.2013.08.003
published as J. Comput. Syst. Sci. 80 (2014) 297-319 · 1 + 36 pages, 18 figures. arXiv admin note: text overlap with arXiv:0911.2924
openalex publication_date 2013/08/22 · arxiv created 2014/12/23 · arxiv updated 2014/12/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
The Pattern self-Assembly Tile set Synthesis (PATS) problem, which arises in the theory of structured DNA self-assembly, is to determine a set of coloured tiles that, starting from a bordering seed structure, self-assembles to a given rectangular colour pattern. The task of finding minimum-size tile sets is known to be NP-hard. We explore several complete and incomplete search techniques for finding minimal, or at least small, tile sets and also assess the reliability of the solutions obtained according to the kinetic Tile Assembly Model.