Difference between revisions of "Reflections on Tiles (in Self-Assembly)"
m |
m |
||
| Line 1: | Line 1: | ||
{{PaperTemplate | {{PaperTemplate | ||
|date=2015/05/11 | |date=2015/05/11 | ||
| − | |abstract=We define the Reflexive Tile Assembly Model (RTAM), which is obtained from the abstract Tile Assembly Model (aTAM) by allowing tiles to reflect across their horizontal and/or vertical axes. We show that the class of directed temperature-1 RTAM systems is not computationally universal, which is conjectured but unproven for the aTAM, and like the aTAM, the RTAM is computationally universal at temperature 2. We then show that at temperature 1, when starting from a single tile seed, the RTAM is capable of assembling n x n squares for n odd using only n tile types, but incapable of assembling n x n squares for n even. Moreover, we show that n is a lower bound on the number of tile types needed to assemble n x n squares for n odd in the temperature-1 RTAM. The conjectured lower bound for temperature-1 aTAM systems is 2n-1. Finally, we give preliminary results toward the classification of which finite connected shapes in Z^2 can be assembled (strictly or weakly) by a singly seeded (i.e. seed of size 1) RTAM system, including a complete classification of which finite connected shapes be strictly assembled by a "mismatch-free" singly seeded RTAM system. | + | |abstract=We define the Reflexive Tile Assembly Model (RTAM), which is obtained from the abstract Tile Assembly Model (aTAM) by allowing tiles to reflect across their horizontal and/or vertical axes. We show that the class of directed temperature-1 RTAM systems is not computationally universal, which is conjectured but unproven for the aTAM, and like the aTAM, the RTAM is computationally universal at temperature 2. We then show that at temperature 1, when starting from a single tile seed, the RTAM is capable of assembling $n$ x $n$ squares for $n$ odd using only $n$ tile types, but incapable of assembling $n$ x $n$ squares for $n$ even. Moreover, we show that $n$ is a lower bound on the number of tile types needed to assemble $n$ x $n$ squares for $n$ odd in the temperature-1 RTAM. The conjectured lower bound for $temperature-1$ aTAM systems is $2n-1$. Finally, we give preliminary results toward the classification of which finite connected shapes in $Z^2$ can be assembled (strictly or weakly) by a singly seeded (i.e. seed of size 1) RTAM system, including a complete classification of which finite connected shapes be strictly assembled by a "mismatch-free" singly seeded RTAM system. |
|authors=Jacob Hendricks, Matthew J. Patitz, Trent A. Rogers | |authors=Jacob Hendricks, Matthew J. Patitz, Trent A. Rogers | ||
|file=[http://arxiv.org/abs/1404.5985 Reflections on Tiles (in Self-Assembly)] | |file=[http://arxiv.org/abs/1404.5985 Reflections on Tiles (in Self-Assembly)] | ||
}} | }} | ||
Latest revision as of 12:40, 22 June 2021
Published on: 2015/05/11
Abstract
We define the Reflexive Tile Assembly Model (RTAM), which is obtained from the abstract Tile Assembly Model (aTAM) by allowing tiles to reflect across their horizontal and/or vertical axes. We show that the class of directed temperature-1 RTAM systems is not computationally universal, which is conjectured but unproven for the aTAM, and like the aTAM, the RTAM is computationally universal at temperature 2. We then show that at temperature 1, when starting from a single tile seed, the RTAM is capable of assembling \(n\) x \(n\) squares for \(n\) odd using only \(n\) tile types, but incapable of assembling \(n\) x \(n\) squares for \(n\) even. Moreover, we show that \(n\) is a lower bound on the number of tile types needed to assemble \(n\) x \(n\) squares for \(n\) odd in the temperature-1 RTAM. The conjectured lower bound for \(temperature-1\) aTAM systems is \(2n-1\). Finally, we give preliminary results toward the classification of which finite connected shapes in \(Z^2\) can be assembled (strictly or weakly) by a singly seeded (i.e. seed of size 1) RTAM system, including a complete classification of which finite connected shapes be strictly assembled by a "mismatch-free" singly seeded RTAM system.
Authors
Jacob Hendricks, Matthew J. Patitz, Trent A. Rogers
