Author name cluster

Scott M. Summers

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

9 papers

2 author rows

TCS Journal 2021 Journal Article

On the effects of hierarchical self-assembly for reducing program-size complexity

Sarah Cannon
Erik D. Demaine
Martin L. Demaine
Sarah Eisenstat
David Furcy
Matthew J. Patitz
Robert Schweller
Scott M. Summers

In this paper we present a series of results which show separations between the standard seeded model of self-assembly, Winfree's abstract Tile Assembly Model (aTAM), and the “seedless” 2-Handed Assembly Model (2HAM), which incorporates the dynamics of hierarchical self-assembly. In particular, we focus on the problem of self-assembling various shapes while minimizing the sizes of tile sets, or “programs”, in each of these models in order to compare and contrast the models. A high-level overview of a subset of these results was presented in a paper by the authors in STACS 2013, but in this version we expand and improve the set of results related to showing separations between the two models according to their abilities to self-assemble various shapes. We exhibit classes of finite shapes that can be self-assembled more efficiently in each model. We also demonstrate infinite shapes that can self-assemble in one model but not in the other, as well as a shape which cannot self-assemble in either model.

Details DOI

TCS Journal 2021 Journal Article

Self-assembly of and optimal encoding within thin rectangles at temperature-1 in 3D

David Furcy
Scott M. Summers
Christian Wendlandt

In this paper, we study the self-assembly of rectangles in a non-cooperative, 3D version of Winfree's abstract Tile Assembly Model. We prove two results. First, we give the full details for the proof of a general construction for the efficient self-assembly of thin rectangles that was first reported by Furcy, Summers and Wendlandt (2019). This construction is non-cooperative and “just-barely” 3D in the sense that it places tiles at most one step into the third dimension. Second, we give a non-cooperative, just-barely 3D optimal encoding construction that self-assembles the bits of a given binary string along the perimeter of a thin rectangle of constant height.

Details DOI

TCS Journal 2018 Journal Article

The power of duples (in self-assembly): It's not so hip to be square

Jacob Hendricks
Matthew J. Patitz
Trent A. Rogers
Scott M. Summers

In this paper we define the Dupled abstract Tile Assembly Model (DaTAM), which is a slight extension to the abstract Tile Assembly Model (aTAM) that allows for not only the standard square tiles, but also “duple” tiles which are rectangles pre-formed by the joining of two square tiles. We show that the addition of duples allows for powerful behaviors of self-assembling systems at temperature 1, meaning systems which exclude the requirement of cooperative binding by tiles (i. e. , the requirement that a tile must be able to bind to at least 2 tiles in an existing assembly if it is to attach). Cooperative binding is conjectured to be required in the standard aTAM for Turing universal computation and the efficient self-assembly of shapes, but we show that in the DaTAM these behaviors can in fact be exhibited at temperature 1. We then give a lower bound on the tile complexity for building thin rectangles in the DaTAM that matches the analogous lower bound in the aTAM. Finally, we present a series of results which prove that the temperature-2 aTAM and temperature-1 DaTAM have mutually exclusive powers. That is, each is able to self-assemble shapes that the other can't, and each has systems which cannot be simulated by the other. Beyond being of purely theoretical interest, these results have practical motivation as duples have already proven to be useful in laboratory implementations of DNA-based tiles.

Details DOI

SODA Conference 2014 Conference Paper

Intrinsic universality in tile self-assembly requires cooperation

Pierre-Étienne Meunier
Matthew J. Patitz
Scott M. Summers
Guillaume Theyssier
Andrew Winslow
Damien Woods

We prove a negative result on the power of a model of algorithmic self-assembly for which finding general techniques and results has been notoriously difficult. Specifically, we prove that Winfree's abstract Tile Assembly Model is not intrinsically universal when restricted to use noncooperative tile binding. This stands in stark contrast to the recent result that the abstract Tile Assembly Model is indeed intrinsically universal when cooperative binding is used (FOCS 2012). Noncooperative self-assembly, also known as “temperature 1”, is where all tiles bind to each other if they match on at least one side. On the other hand, cooperative self-assembly requires that some tiles bind on at least two sides. Our result shows that the change from non-cooperative to cooperative binding qualitatively improves the range of dynamics and behaviors found in these models of nanoscale self-assembly. The result holds in both two and three dimensions; the latter being quite surprising given that three-dimensional noncooperative tile assembly systems simulate Turing machines. This shows that Turing universal behavior in self-assembly does not imply the ability to simulate all algorithmic self-assembly processes. In addition to the negative result, we exhibit a three-dimensional noncooperative self-assembly tile set capable of simulating any two-dimensional noncooperative self-assembly system. This tile set implies that, in a restricted sense, non-cooperative self-assembly is intrinsically universal for itself.

Details

FOCS Conference 2012 Conference Paper

The Tile Assembly Model is Intrinsically Universal

David Doty
Jack H. Lutz
Matthew J. Patitz
Robert Schweller
Scott M. Summers
Damien Woods

We prove that the abstract Tile Assembly Model (aTAM) of nanoscale self-assembly is intrinsically universal. This means that there is a single tile assembly system U that, with proper initialization, simulates any tile assembly system T. The simulation is "intrinsic" in the sense that the self-assembly process carried out by U is exactly that carried out by T, with each tile of T represented by an m × m "super tile" of U. Our construction works for the full aTAM at any temperature, and it faithfully simulates the deterministic or nondeterministic behavior of each T. Our construction succeeds by solving an analog of the cell differentiation problem in developmental biology: Each super tile of U, starting with those in the seed assembly, carries the "genome" of the simulated system T. At each location of a potential super tile in the self-assembly of U, a decision is made whether and how to express this genome, i. e. , whether to generate a super tile and, if so, which tile of T it will represent. This decision must be achieved using asynchronous communication under incomplete information, but it achieves the correct global outcome(s).

Details

TCS Journal 2011 Journal Article

Limitations of self-assembly at temperature 1

David Doty
Matthew J. Patitz
Scott M. Summers

We prove that if a set X ⊆ Z 2 weakly self-assembles at temperature 1 in a deterministic (Winfree) tile assembly system satisfying a natural condition known as pumpability, then X is a semilinear set. This shows that only the most simple of infinite shapes and patterns can be constructed using pumpable temperature 1 tile assembly systems, and gives evidence for the thesis that temperature 2 or higher is required to carry out general-purpose computation in a deterministic two-dimensional tile assembly system. We employ this result to show that, unlike the case of temperature 2 self-assembly, no discrete self-similar fractal weakly self-assembles at temperature 1 in a pumpable tile assembly system.

Details DOI

TCS Journal 2011 Journal Article

Self-assembly of infinite structures: A survey

Matthew J. Patitz
Scott M. Summers

We survey some recent results related to the self-assembly of infinite structures in Winfree’s abstract Tile Assembly Model. These results include impossibility results, as well as the construction of novel tile assembly systems that produce computationally interesting shapes and patterns. Several open questions are also presented and motivated.

Details DOI

FOCS Conference 2010 Conference Paper

Strong Fault-Tolerance for Self-Assembly with Fuzzy Temperature

David Doty
Matthew J. Patitz
Dustin Reishus
Robert Schweller
Scott M. Summers

We consider the problem of fault-tolerance in nanoscale algorithmic self-assembly. We employ a standard variant of Winfree's abstract Tile Assembly Model (aTAM), the two-handed aTAM, in which square “tiles” - a model of molecules constructed from DNA for the purpose of engineering self-assembled nanostructures - aggregate according to specific binding sites of varying strengths, and in which large aggregations of tiles may attach to each other, in contrast to the seeded aTAM, in which tiles aggregate one at a time to a single specially designated “seed” assembly. We focus on a major cause of errors in tile-based self-assembly: that of unintended growth due to “weak” strength-1 bonds, which if allowed to persist, may be stabilized by subsequent attachment of neighboring tiles in the sense that at least energy 2 is now required to break apart the resulting assembly, i. e. , the errant assembly is stable at temperature 2. We study a common self-assembly benchmark problem, that of assembling an n×n square using O(log n) unique tile types, under the two-handed model of self-assembly. Our main result achieves a much stronger notion of fault-tolerance than those achieved previously. Arbitrary strength-1 growth is allowed, however, any assembly that grows sufficiently to become stable at temperature 2 is guaranteed to assemble into the correct final assembly of an n×n square. In other words, errors due to insufficient attachment, which is the cause of errors studied in earlier papers on fault-tolerance, are prevented absolutely in our main construction, rather than only with high probability and for sufficiently small structures, as in previous fault tolerance studies.

Details

TCS Journal 2009 Journal Article

Strict self-assembly of discrete Sierpinski triangles

James I. Lathrop
Jack H. Lutz
Scott M. Summers

Winfree (1998) showed that discrete Sierpinski triangles can self-assemble in the Tile Assembly Model. A striking molecular realization of this self-assembly, using DNA tiles a few nanometers long and verifying the results by atomic-force microscopy, was achieved by Rothemund, Papadakis, and Winfree (2004). Precisely speaking, the above self-assemblies tile completely filled-in, two-dimensional regions of the plane, with labeled subsets of these tiles representing discrete Sierpinski triangles. This paper addresses the more challenging problem of the strict self-assembly of discrete Sierpinski triangles, i. e. , the task of tiling a discrete Sierpinski triangle and nothing else. We first prove that the standard discrete Sierpinski triangle cannot strictly self-assemble in the Tile Assembly Model. We then define the fibered Sierpinski triangle, a discrete Sierpinski triangle with the same fractal dimension as the standard one but with thin fibers that can carry data, and show that the fibered Sierpinski triangle strictly self-assembles in the Tile Assembly Model. In contrast with the simple XOR algorithm of the earlier, non-strict self-assemblies, our strict self-assembly algorithm makes extensive, recursive use of optimal counters, coupled with measured delay and corner-turning operations. We verify our strict self-assembly using the local determinism method of Soloveichik and Winfree (2007).

Details DOI