BZPEER
More

Discover

About BZPEERSearchGraph

Research tools

HomeCollectionsResearchCollaborationPublish

Network

ExpertsCommunities

Opportunities

Listings

Account

Log inCreate account
Log inCreate account

Source author record

Robert T. Schweller

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record
Computational ComplexityComputational GeometryData Structures and AlgorithmsEmerging TechnologiesDiscrete Mathematics

Catalog footprint

Research overview

12works
5topics
4close collaborators

Actions

Is this your work?

Log in to claim
Open graphBrowse papers

Published work

12 publications

preprint2015arXiv

Size-Dependent Tile Self-Assembly: Constant-Height Rectangles and Stability

We introduce a new model of algorithmic tile self-assembly called size-dependent assembly. In previous models, supertiles are stable when the total strength of the bonds between any two halves exceeds some constant temperature. In this model, this constant temperature requirement is replaced by an nondecreasing temperature function τ:N→Nτ: \mathbb{N} \rightarrow \mathbb{N} that depends on the size of the smaller of the two halves. This generalization allows supertiles to become unstable and break apart, and captures the increased forces that large structures may place on the bonds holding them together. We demonstrate the power of this model in two ways. First, we give fixed tile sets that assemble constant-height rectangles and squares of arbitrary input size given an appropriate temperature function. Second, we prove that deciding whether a supertile is stable is coNP-complete. Both results contrast with known results for fixed temperature.

Open access
preprint2015arXiv

Strict Self-Assembly of Fractals using Multiple Hands

In this paper we consider the problem of the strict self-assembly of infinite fractals within tile self-assembly. In particular, we provide tile assembly algorithms for the assembly of the discrete Sierpinski triangle and the discrete Sierpinski carpet within a class of models we term the \emph{hh-handed assembly model} (hh-HAM), which generalizes the 2-HAM to allow up to hh assemblies to combine in a single assembly step. Despite substantial consideration, no purely growth self-assembly model has yet been shown to strictly assemble an infinite fractal without significant modification to the fractal shape. In this paper we not only achieve this, but in the case of the Sierpinski carpet are able to achieve it within the 2-HAM, one of the most well studied tile assembly models in the literature. Our specific results are as follows. We provide a 66-HAM construction for the Sierpinski triangle that works at scale factor 1, 30 tile types, and assembles the fractal in a \emph{near perfect} way in which all intermediate assemblies are finite-sized iterations of the recursive fractal. We further assemble the Sierpinski triangle within the 33-HAM at scale factor 3 and 990 tile types. For the Sierpinski carpet, we present a 22-HAM result that works at scale factor 3 and uses 1,216 tile types. We further include analysis showing that the aTAM is incapable of strictly assembling the non-tree Sierpinski triangle considered in this paper, and that multiple hands are needed for the near-perfect assembly of the Sierpinski triangle and the Sierpinski carpet.

Open access
preprint2014arXiv

The two-handed tile assembly model is not intrinsically universal

The well-studied Two-Handed Tile Assembly Model (2HAM) is a model of tile assembly in which pairs of large assemblies can bind, or self-assemble, together. In order to bind, two assemblies must have matching glues that can simultaneously touch each other, and stick together with strength that is at least the temperature ττ, where ττ is some fixed positive integer. We ask whether the 2HAM is intrinsically universal, in other words we ask: is there a single universal 2HAM tile set UU which can be used to simulate any instance of the model? Our main result is a negative answer to this question. We show that for all τ′<ττ' < τ, each temperature-τ′τ' 2HAM tile system does not simulate at least one temperature-ττ 2HAM tile system. This impossibility result proves that the 2HAM is not intrinsically universal, in stark contrast to the simpler (single-tile addition only) abstract Tile Assembly Model which is intrinsically universal ("The tile assembly model is intrinsically universal", FOCS 2012). However, on the positive side, we prove that, for every fixed temperature τ≥2τ\geq 2, temperature-ττ 2HAM tile systems are indeed intrinsically universal: in other words, for each ττ there is a single universal 2HAM tile set UU that, when appropriately initialized, is capable of simulating the behavior of any temperature-ττ 2HAM tile system. As a corollary of these results we find an infinite set of infinite hierarchies of 2HAM systems with strictly increasing simulation power within each hierarchy. Finally, we show that for each ττ, there is a temperature-ττ 2HAM system that simultaneously simulates all temperature-ττ 2HAM systems.

Open access
preprint2014arXiv

Universal Computation with Arbitrary Polyomino Tiles in Non-Cooperative Self-Assembly

In this paper we explore the power of geometry to overcome the limitations of non-cooperative self-assembly. We define a generalization of the abstract Tile Assembly Model (aTAM), such that a tile system consists of a collection of polyomino tiles, the Polyomino Tile Assembly Model (polyTAM), and investigate the computational powers of polyTAM systems at temperature 1, where attachment among tiles occurs without glue cooperation. Systems composed of the unit-square tiles of the aTAM at temperature 1 are believed to be incapable of Turing universal computation (while cooperative systems, with temperature > 1, are able). As our main result, we prove that for any polyomino PP of size 3 or greater, there exists a temperature-1 polyTAM system containing only shape-PP tiles that is computationally universal. Our proof leverages the geometric properties of these larger (relative to the aTAM) tiles and their abilities to effectively utilize geometric blocking of particular growth paths of assemblies, while allowing others to complete. To round out our main result, we provide strong evidence that size-1 (i.e. aTAM tiles) and size-2 polyomino systems are unlikely to be computationally universal by showing that such systems are incapable of geometric bit-reading, which is a technique common to all currently known temperature-1 computationally universal systems. We further show that larger polyominoes with a limited number of binding positions are unlikely to be computationally universal, as they are only as powerful as temperature-1 aTAM systems. Finally, we connect our work with other work on domino self-assembly to show that temperature-1 assembly with at least 2 distinct shapes, regardless of the shapes or their sizes, allows for universal computation.

Open access
preprint2013arXiv

Asynchronous Signal Passing for Tile Self-Assembly: Fuel Efficient Computation and Efficient Assembly of Shapes

In this paper we demonstrate the power of a model of tile self-assembly based on active glues which can dynamically change state. We formulate the Signal-passing Tile Assembly Model (STAM), based on the model of Padilla, Liu, and Seeman to be asynchronous, allowing any action of turning a glue on or off, attaching a new tile, or breaking apart an assembly to happen in any order. Within this highly generalized model we provide three new solutions to tile self-assembly problems that have been addressed within the abstract Tile Assembly Model and its variants, showing that signal passing tiles allow for substantial improvement across multiple complexity metrics. Our first result utilizes a recursive assembly process to achieve tile-type efficient assembly of linear structures, using provably fewer tile types than what is possible in standard tile assembly models. Our second system of signal-passing tiles simulates any Turing machine with high fuel efficiency by using only a constant number of tiles per computation step. Our third system assembles the discrete Sierpinski triangle, demonstrating that this pattern can be strictly self-assembled within the STAM. This result is of particular interest in that it is known that this pattern cannot self-assemble within a number of well studied tile self-assembly models. Notably, all of our constructions are at temperature 1, further demonstrating that signal-passing confers the power to bypass many restrictions found in standard tile assembly models.

Open access
preprint2012arXiv

Efficient Squares and Turing Universality at Temperature 1 with a Unique Negative Glue

Is Winfree's abstract Tile Assembly Model (aTAM) "powerful?" Well, if certain tiles are required to "cooperate" in order to be able to bind to a growing tile assembly (a.k.a., temperature 2 self-assembly), then Turing universal computation and the efficient self-assembly of N×NN \times N squares is achievable in the aTAM (Rotemund and Winfree, STOC 2000). So yes, in a computational sense, the aTAM is quite powerful! However, if one completely removes this cooperativity condition (a.k.a., temperature 1 self-assembly), then the computational "power" of the aTAM (i.e., its ability to support Turing universal computation and the efficient self-assembly of N×NN \times N squares) becomes unknown. On the plus side, the aTAM, at temperature 1, isn't only Turing universal but also supports the efficient self-assembly N×NN \times N squares if self-assembly is allowed to utilize three spatial dimensions (Fu, Schweller and Cook, SODA 2011). We investigate the theoretical "power" of a seemingly simple, restrictive class of tile assembly systems (TASs) in which (1) the absolute value of every glue strength is 1, (2) there's a single negative strength glue type and (3) unequal glues can't interact. We call these the \emph{restricted glue} TASs (rgTAS). We first show the tile complexity of producing an N×NN \times N square with an rgTAS is O(log⁡nlog⁡log⁡n)O(\frac{\log n}{\log \log n}). We also prove that rgTASs are Turing universal with a construction that simulates an arbitrary Turing machine. Next, we provide results for a variation of the rgTAS class, partially restricted glue TASs, which is similar except that the magnitude of the negative glue's strength can only assumed to be ≥1\ge 1. These results consist of a construction with O(log⁡n)O(\log n) tile complexity for building N×NN \times N squares, and one which simulates a Turing machine but with a greater scaling factor than for the rgTAS construction.

Open access
preprint2012arXiv

One Tile to Rule Them All: Simulating Any Turing Machine, Tile Assembly System, or Tiling System with a Single Puzzle Piece

In this paper we explore the power of tile self-assembly models that extend the well-studied abstract Tile Assembly Model (aTAM) by permitting tiles of shapes beyond unit squares. Our main result shows the surprising fact that any aTAM system, consisting of many different tile types, can be simulated by a single tile type of a general shape. As a consequence, we obtain a single universal tile type of a single (constant-size) shape that serves as a "universal tile machine": the single universal tile type can simulate any desired aTAM system when given a single seed assembly that encodes the desired aTAM system. We also show how to adapt this result to convert any of a variety of plane tiling systems (such as Wang tiles) into a "nearly" plane tiling system with a single tile (but with small gaps between the tiles). All of these results rely on the ability to both rotate and translate tiles; by contrast, we show that a single nonrotatable tile, of arbitrary shape, can produce assemblies which either grow infinitely or cannot grow at all, implying drastically limited computational power. On the positive side, we show how to simulate arbitrary cellular automata for a limited number of steps using a single nonrotatable tile and a linear-size seed assembly.

Open access
preprint2012arXiv

The tile assembly model is intrinsically universal

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 x m "supertile" 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 supertile of U, starting with those in the seed assembly, carries the "genome" of the simulated system T. At each location of a potential supertile in the self-assembly of U, a decision is made whether and how to express this genome, i.e., whether to generate a supertile 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).

Open access
preprint2011arXiv

Self-Assembly with Geometric Tiles

In this work we propose a generalization of Winfree's abstract Tile Assembly Model (aTAM) in which tile types are assigned rigid shapes, or geometries, along each tile face. We examine the number of distinct tile types needed to assemble shapes within this model, the temperature required for efficient assembly, and the problem of designing compact geometric faces to meet given compatibility specifications. Our results show a dramatic decrease in the number of tile types needed to assemble n×nn \times n squares to Θ(log⁡n)Θ(\sqrt{\log n}) at temperature 1 for the most simple model which meets a lower bound from Kolmogorov complexity, and O(log⁡log⁡n)O(\log\log n) in a model in which tile aggregates must move together through obstacle free paths within the plane. This stands in contrast to the Θ(log⁡n/log⁡log⁡n)Θ(\log n / \log\log n) tile types at temperature 2 needed in the basic aTAM. We also provide a general method for simulating a large and computationally universal class of temperature 2 aTAM systems with geometric tiles at temperature 1. Finally, we consider the problem of computing a set of compact geometric faces for a tile system to implement a given set of compatibility specifications. We show a number of bounds on the complexity of geometry size needed for various classes of compatibility specifications, many of which we directly apply to our tile assembly results to achieve non-trivial reductions in geometry size.

Open access
preprint2010arXiv

Self-Assembly of Arbitrary Shapes Using RNAse Enzymes: Meeting the Kolmogorov Bound with Small Scale Factor (extended abstract)

We consider a model of algorithmic self-assembly of geometric shapes out of square Wang tiles studied in SODA 2010, in which there are two types of tiles (e.g., constructed out of DNA and RNA material) and one operation that destroys all tiles of a particular type (e.g., an RNAse enzyme destroys all RNA tiles). We show that a single use of this destruction operation enables much more efficient construction of arbitrary shapes. In particular, an arbitrary shape can be constructed using an asymptotically optimal number of distinct tile types (related to the shape's Kolmogorov complexity), after scaling the shape by only a logarithmic factor. By contrast, without the destruction operation, the best such result has a scale factor at least linear in the size of the shape, and is connected only by a spanning tree of the scaled tiles. We also characterize a large collection of shapes that can be constructed efficiently without any scaling.

Open access
preprint2010arXiv

Strong Fault-Tolerance for Self-Assembly with Fuzzy Temperature

We consider the problem of fault-tolerance in nanoscale algorithmic self-assembly. We employ a 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 x 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 (i.e., the temperature is "fuzzy" and may drift from 2 to 1 for arbitrarily long); however, any assembly that grows sufficiently to become stable at temperature 2 is guaranteed to assemble at temperature 2 into the correct final assembly of an n x 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.

Open access
preprint2010arXiv

Temperature 1 Self-Assembly: Deterministic Assembly in 3D and Probabilistic Assembly in 2D

We investigate the power of the Wang tile self-assembly model at temperature 1, a threshold value that permits attachment between any two tiles that share even a single bond. When restricted to deterministic assembly in the plane, no temperature 1 assembly system has been shown to build a shape with a tile complexity smaller than the diameter of the shape. In contrast, we show that temperature 1 self-assembly in 3 dimensions, even when growth is restricted to at most 1 step into the third dimension, is capable of simulating a large class of temperature 2 systems, in turn permitting the simulation of arbitrary Turing machines and the assembly of n×nn\times n squares in near optimal O(log⁡n)O(\log n) tile complexity. Further, we consider temperature 1 probabilistic assembly in 2D, and show that with a logarithmic scale up of tile complexity and shape scale, the same general class of temperature τ=2τ=2 systems can be simulated with high probability, yielding Turing machine simulation and O(log⁡2n)O(\log^2 n) assembly of n×nn\times n squares with high probability. Our results show a sharp contrast in achievable tile complexity at temperature 1 if either growth into the third dimension or a small probability of error are permitted. Motivated by applications in nanotechnology and molecular computing, and the plausibility of implementing 3 dimensional self-assembly systems, our techniques may provide the needed power of temperature 2 systems, while at the same time avoiding the experimental challenges faced by those systems.

Open access

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.