Randomized self-assembly for approximate shapes

Ming-Yang Kao*, Robert Schweller

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

45 Citations (Scopus)

Abstract

In this paper we design tile self-assembly systems which assemble arbitrarily close approximations to target squares with arbitrarily high probability. This is in contrast to previous work which has only considered deterministic assemblies of a single shape. Our technique takes advantage of the ability to assign tile concentrations to each tile type of a self-assembly system. Such an assignment yields a probability distribution over the set of possible assembled shapes. We show that by considering the assembly of close approximations to target shapes with high probability, as opposed to exact deterministic assembly, we are able to achieve significant reductions in tile complexity. In fact, we restrict ourselves to constant sized tile systems, encoding all information about the target shape into the tile concentration assignment. In practice, this offers a potentially useful tradeoff, as large libraries of particles may be infeasible or require substantial effort to create, while the replication of existing particles to adjust relative concentration may be much easier. To illustrate our technique we focus on the assembly of n×n squares, a special case class of shapes whose study has proven fruitful in the development of new self-assembly systems.

Original languageEnglish (US)
Title of host publicationAutomata, Languages and Programming - 35th International Colloquium, ICALP 2008, Proceedings
Pages370-384
Number of pages15
EditionPART 1
DOIs
StatePublished - Aug 14 2008
Event35th International Colloquium on Automata, Languages and Programming, ICALP 2008 - Reykjavik, Iceland
Duration: Jul 7 2008Jul 11 2008

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
NumberPART 1
Volume5125 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other35th International Colloquium on Automata, Languages and Programming, ICALP 2008
CountryIceland
CityReykjavik
Period7/7/087/11/08

Fingerprint

Self-assembly
Tile
Self assembly
Assembly Systems
Target
Assignment
Approximation
Probability distributions
Replication
Assign
Encoding
Probability Distribution
Trade-offs

Keywords

  • Approximation Algorithms
  • Randomized Algorithms
  • Self-Assembly

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this

Kao, M-Y., & Schweller, R. (2008). Randomized self-assembly for approximate shapes. In Automata, Languages and Programming - 35th International Colloquium, ICALP 2008, Proceedings (PART 1 ed., pp. 370-384). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5125 LNCS, No. PART 1). https://doi.org/10.1007/978-3-540-70575-8_31
Kao, Ming-Yang ; Schweller, Robert. / Randomized self-assembly for approximate shapes. Automata, Languages and Programming - 35th International Colloquium, ICALP 2008, Proceedings. PART 1. ed. 2008. pp. 370-384 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); PART 1).
@inproceedings{543cf8f8b379489c9479681e500efe66,
title = "Randomized self-assembly for approximate shapes",
abstract = "In this paper we design tile self-assembly systems which assemble arbitrarily close approximations to target squares with arbitrarily high probability. This is in contrast to previous work which has only considered deterministic assemblies of a single shape. Our technique takes advantage of the ability to assign tile concentrations to each tile type of a self-assembly system. Such an assignment yields a probability distribution over the set of possible assembled shapes. We show that by considering the assembly of close approximations to target shapes with high probability, as opposed to exact deterministic assembly, we are able to achieve significant reductions in tile complexity. In fact, we restrict ourselves to constant sized tile systems, encoding all information about the target shape into the tile concentration assignment. In practice, this offers a potentially useful tradeoff, as large libraries of particles may be infeasible or require substantial effort to create, while the replication of existing particles to adjust relative concentration may be much easier. To illustrate our technique we focus on the assembly of n×n squares, a special case class of shapes whose study has proven fruitful in the development of new self-assembly systems.",
keywords = "Approximation Algorithms, Randomized Algorithms, Self-Assembly",
author = "Ming-Yang Kao and Robert Schweller",
year = "2008",
month = "8",
day = "14",
doi = "10.1007/978-3-540-70575-8_31",
language = "English (US)",
isbn = "3540705740",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
number = "PART 1",
pages = "370--384",
booktitle = "Automata, Languages and Programming - 35th International Colloquium, ICALP 2008, Proceedings",
edition = "PART 1",

}

Kao, M-Y & Schweller, R 2008, Randomized self-assembly for approximate shapes. in Automata, Languages and Programming - 35th International Colloquium, ICALP 2008, Proceedings. PART 1 edn, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), no. PART 1, vol. 5125 LNCS, pp. 370-384, 35th International Colloquium on Automata, Languages and Programming, ICALP 2008, Reykjavik, Iceland, 7/7/08. https://doi.org/10.1007/978-3-540-70575-8_31

Randomized self-assembly for approximate shapes. / Kao, Ming-Yang; Schweller, Robert.

Automata, Languages and Programming - 35th International Colloquium, ICALP 2008, Proceedings. PART 1. ed. 2008. p. 370-384 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5125 LNCS, No. PART 1).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

TY - GEN

T1 - Randomized self-assembly for approximate shapes

AU - Kao, Ming-Yang

AU - Schweller, Robert

PY - 2008/8/14

Y1 - 2008/8/14

N2 - In this paper we design tile self-assembly systems which assemble arbitrarily close approximations to target squares with arbitrarily high probability. This is in contrast to previous work which has only considered deterministic assemblies of a single shape. Our technique takes advantage of the ability to assign tile concentrations to each tile type of a self-assembly system. Such an assignment yields a probability distribution over the set of possible assembled shapes. We show that by considering the assembly of close approximations to target shapes with high probability, as opposed to exact deterministic assembly, we are able to achieve significant reductions in tile complexity. In fact, we restrict ourselves to constant sized tile systems, encoding all information about the target shape into the tile concentration assignment. In practice, this offers a potentially useful tradeoff, as large libraries of particles may be infeasible or require substantial effort to create, while the replication of existing particles to adjust relative concentration may be much easier. To illustrate our technique we focus on the assembly of n×n squares, a special case class of shapes whose study has proven fruitful in the development of new self-assembly systems.

AB - In this paper we design tile self-assembly systems which assemble arbitrarily close approximations to target squares with arbitrarily high probability. This is in contrast to previous work which has only considered deterministic assemblies of a single shape. Our technique takes advantage of the ability to assign tile concentrations to each tile type of a self-assembly system. Such an assignment yields a probability distribution over the set of possible assembled shapes. We show that by considering the assembly of close approximations to target shapes with high probability, as opposed to exact deterministic assembly, we are able to achieve significant reductions in tile complexity. In fact, we restrict ourselves to constant sized tile systems, encoding all information about the target shape into the tile concentration assignment. In practice, this offers a potentially useful tradeoff, as large libraries of particles may be infeasible or require substantial effort to create, while the replication of existing particles to adjust relative concentration may be much easier. To illustrate our technique we focus on the assembly of n×n squares, a special case class of shapes whose study has proven fruitful in the development of new self-assembly systems.

KW - Approximation Algorithms

KW - Randomized Algorithms

KW - Self-Assembly

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

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

U2 - 10.1007/978-3-540-70575-8_31

DO - 10.1007/978-3-540-70575-8_31

M3 - Conference contribution

AN - SCOPUS:49049117841

SN - 3540705740

SN - 9783540705741

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

SP - 370

EP - 384

BT - Automata, Languages and Programming - 35th International Colloquium, ICALP 2008, Proceedings

ER -

Kao M-Y, Schweller R. Randomized self-assembly for approximate shapes. In Automata, Languages and Programming - 35th International Colloquium, ICALP 2008, Proceedings. PART 1 ed. 2008. p. 370-384. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); PART 1). https://doi.org/10.1007/978-3-540-70575-8_31