3-Color bounded patterned self-assembly (Extended abstract)

Lila Kari; Steffen Kopecki; Shinnosuke Seki

doi:10.1007/978-3-319-01928-4_8

3-Color bounded patterned self-assembly (Extended abstract)

Lila Kari, Steffen Kopecki, Shinnosuke Seki

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Scientific › peer-review

1 Citation (Scopus)

Abstract

Patterned self-assembly tile set synthesis (Pats) is the problem of finding a minimal tile set which uniquely self-assembles into a given pattern. Czeizler and Popa proved the NP-completeness of Pats and Seki showed that the Pats problem is already NP-complete for patterns with 60 colors. In search for the minimal number of colors such that Pats remains NP-complete, we introduce multiple bound Pats (mbPats) where we allow bounds for the numbers of tile types of each color. We show that mbPats is NP-complete for patterns with just three colors and, as a byproduct of this result, we also obtain a novel proof for the NP-completeness of pats which is more concise than the previous proofs.

Original language	English
Title of host publication	DNA Computing and Molecular Programming - 19th International Conference, DNA 2013, Proceedings
Pages	105-117
Number of pages	13
Volume	8141 LNCS
DOIs	https://doi.org/10.1007/978-3-319-01928-4_8
Publication status	Published - 2013
MoE publication type	A4 Article in a conference publication
Event	International Conference on DNA Computing and Molecular Programming - Arizona State University, Tempe, United States Duration: 22 Sep 2013 → 27 Sep 2013 Conference number: 19

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	8141 LNCS
ISSN (Print)	03029743
ISSN (Electronic)	16113349

Conference

Conference	International Conference on DNA Computing and Molecular Programming
Abbreviated title	DNA
Country	United States
City	Tempe
Period	22/09/2013 → 27/09/2013

Access to Document

10.1007/978-3-319-01928-4_8

Link to publication in Scopus

Fingerprint Dive into the research topics of '3-Color bounded patterned self-assembly (Extended abstract)'. Together they form a unique fingerprint.

Cite this

Kari, L., Kopecki, S., & Seki, S. (2013). 3-Color bounded patterned self-assembly (Extended abstract). In DNA Computing and Molecular Programming - 19th International Conference, DNA 2013, Proceedings (Vol. 8141 LNCS, pp. 105-117). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8141 LNCS). https://doi.org/10.1007/978-3-319-01928-4_8

Kari, Lila ; Kopecki, Steffen ; Seki, Shinnosuke. / 3-Color bounded patterned self-assembly (Extended abstract). DNA Computing and Molecular Programming - 19th International Conference, DNA 2013, Proceedings. Vol. 8141 LNCS 2013. pp. 105-117 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{1d7f4e37ae6a467bad23821e398f96ee,

title = "3-Color bounded patterned self-assembly (Extended abstract)",

abstract = "Patterned self-assembly tile set synthesis (Pats) is the problem of finding a minimal tile set which uniquely self-assembles into a given pattern. Czeizler and Popa proved the NP-completeness of Pats and Seki showed that the Pats problem is already NP-complete for patterns with 60 colors. In search for the minimal number of colors such that Pats remains NP-complete, we introduce multiple bound Pats (mbPats) where we allow bounds for the numbers of tile types of each color. We show that mbPats is NP-complete for patterns with just three colors and, as a byproduct of this result, we also obtain a novel proof for the NP-completeness of pats which is more concise than the previous proofs.",

author = "Lila Kari and Steffen Kopecki and Shinnosuke Seki",

year = "2013",

doi = "10.1007/978-3-319-01928-4_8",

language = "English",

isbn = "9783319019277",

volume = "8141 LNCS",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "105--117",

booktitle = "DNA Computing and Molecular Programming - 19th International Conference, DNA 2013, Proceedings",

note = "International Conference on DNA Computing and Molecular Programming, DNA ; Conference date: 22-09-2013 Through 27-09-2013",

}

Kari, L, Kopecki, S & Seki, S 2013, 3-Color bounded patterned self-assembly (Extended abstract). in DNA Computing and Molecular Programming - 19th International Conference, DNA 2013, Proceedings. vol. 8141 LNCS, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 8141 LNCS, pp. 105-117, International Conference on DNA Computing and Molecular Programming, Tempe, United States, 22/09/2013. https://doi.org/10.1007/978-3-319-01928-4_8

3-Color bounded patterned self-assembly (Extended abstract). / Kari, Lila; Kopecki, Steffen; Seki, Shinnosuke.

DNA Computing and Molecular Programming - 19th International Conference, DNA 2013, Proceedings. Vol. 8141 LNCS 2013. p. 105-117 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8141 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Scientific › peer-review

TY - GEN

T1 - 3-Color bounded patterned self-assembly (Extended abstract)

AU - Kari, Lila

AU - Kopecki, Steffen

AU - Seki, Shinnosuke

N1 - Conference code: 19

PY - 2013

Y1 - 2013

N2 - Patterned self-assembly tile set synthesis (Pats) is the problem of finding a minimal tile set which uniquely self-assembles into a given pattern. Czeizler and Popa proved the NP-completeness of Pats and Seki showed that the Pats problem is already NP-complete for patterns with 60 colors. In search for the minimal number of colors such that Pats remains NP-complete, we introduce multiple bound Pats (mbPats) where we allow bounds for the numbers of tile types of each color. We show that mbPats is NP-complete for patterns with just three colors and, as a byproduct of this result, we also obtain a novel proof for the NP-completeness of pats which is more concise than the previous proofs.

AB - Patterned self-assembly tile set synthesis (Pats) is the problem of finding a minimal tile set which uniquely self-assembles into a given pattern. Czeizler and Popa proved the NP-completeness of Pats and Seki showed that the Pats problem is already NP-complete for patterns with 60 colors. In search for the minimal number of colors such that Pats remains NP-complete, we introduce multiple bound Pats (mbPats) where we allow bounds for the numbers of tile types of each color. We show that mbPats is NP-complete for patterns with just three colors and, as a byproduct of this result, we also obtain a novel proof for the NP-completeness of pats which is more concise than the previous proofs.

UR - http://www.scopus.com/inward/record.url?scp=84888335504&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-01928-4_8

DO - 10.1007/978-3-319-01928-4_8

M3 - Conference contribution

AN - SCOPUS:84888335504

SN - 9783319019277

VL - 8141 LNCS

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 105

EP - 117

BT - DNA Computing and Molecular Programming - 19th International Conference, DNA 2013, Proceedings

T2 - International Conference on DNA Computing and Molecular Programming

Y2 - 22 September 2013 through 27 September 2013

ER -

Kari L, Kopecki S, Seki S. 3-Color bounded patterned self-assembly (Extended abstract). In DNA Computing and Molecular Programming - 19th International Conference, DNA 2013, Proceedings. Vol. 8141 LNCS. 2013. p. 105-117. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/978-3-319-01928-4_8