TY - GEN
T1 - Randomized self-assembly for approximate shapes
AU - Kao, Ming-Yang
AU - Schweller, Robert
PY - 2008
Y1 - 2008
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
T2 - 35th International Colloquium on Automata, Languages and Programming, ICALP 2008
Y2 - 7 July 2008 through 11 July 2008
ER -