BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Matthew J. Patitz

Matthew J. Patitz appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Emerging TechnologiesComputational ComplexityComputational GeometryData Structures and AlgorithmsFormal Languages and Automata TheoryComputational Engineering, Finance, and ScienceLogic in Computer ScienceMathematical Softwarenlin.CG

Catalog footprint

What is connected

27works
9topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

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.

Published work

27 published item(s)

preprint2022arXiv

Replication of arbitrary hole-free shapes via self-assembly with signal-passing tiles

In this paper, we investigate the abilities of systems of self-assembling tiles which can each pass a constant number of signals to their immediate neighbors to create replicas of input shapes. Namely, we work within the Signal-passing Tile Assembly Model (STAM), and we provide a universal STAM tile set which is capable of creating unbounded numbers of assemblies of shapes identical to those of input assemblies. The shapes of the input assemblies can be arbitrary 2-dimensional hole-free shapes. This improves previous shape replication results in self-assembly that required models in which multiple assembly stages and/or bins were required, and the shapes which could be replicated were more constrained, as well as a previous version of this result that required input shapes to be represented at scale factor 2.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Self-Replication via Tile Self-Assembly

In this paper we present a model containing modifications to the Signal-passing Tile Assembly Model (STAM), a tile-based self-assembly model whose tiles are capable of activating and deactivating glues based on the binding of other glues. These modifications consist of an extension to 3D, the ability of tiles to form "flexible" bonds that allow bound tiles to rotate relative to each other, and allowing tiles of multiple shapes within the same system. We call this new model the STAM*, and we present a series of constructions within it that are capable of self-replicating behavior. Namely, the input seed assemblies to our STAM* systems can encode either "genomes" specifying the instructions for building a target shape, or can be copies of the target shape with instructions built in. A universal tile set exists for any target shape (at scale factor 2), and from a genome assembly creates infinite copies of the genome as well as the target shape. An input target structure, on the other hand, can be "deconstructed" by the universal tile set to form a genome encoding it, which will then replicate and also initiate the growth of copies of assemblies of the target shape. Since the lengths of the genomes for these constructions are proportional to the number of points in the target shape, we also present a replicator which utilizes hierarchical self-assembly to greatly reduce the size of the genomes required. The main goals of this work are to examine minimal requirements of self-assembling systems capable of self-replicating behavior, with the aim of better understanding self-replication in nature as well as understanding the complexity of mimicking it.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Universal Shape Replication Via Self-Assembly With Signal-Passing Tiles

In this paper, we investigate shape-assembling power of a tile-based model of self-assembly called the Signal-Passing Tile Assembly Model (STAM). In this model, the glues that bind tiles together can be turned on and off by the binding actions of other glues via "signals". Specifically, the problem we investigate is "shape replication" wherein, given a set of input assemblies of arbitrary shape, a system must construct an arbitrary number of assemblies with the same shapes and, with the exception of size-bounded junk assemblies that result from the process, no others. We provide the first fully universal shape replication result, namely a single tile set capable of performing shape replication on arbitrary sets of any 3-dimensional shapes without requiring any scaling or pre-encoded information in the input assemblies. Our result requires the input assemblies to be composed of signal-passing tiles whose glues can be deactivated to allow deconstruction of those assemblies, which we also prove is necessary by showing that there are shapes whose geometry cannot be replicated without deconstruction. Additionally, we modularize our construction to create systems capable of creating binary encodings of arbitrary shapes, and building arbitrary shapes from their encodings. Because the STAM is capable of universal computation, this then allows for arbitrary programs to be run within an STAM system, using the shape encodings as input, so that any computable transformation can be performed on the shapes.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Hierarchical Self-Assembly of Fractals with Signal-Passing Tiles

In this paper, we present high-level overviews of tile-based self-assembling systems capable of producing complex, infinite, aperiodic structures known as discrete self-similar fractals. Fractals have a variety of interesting mathematical and structural properties, and by utilizing the bottom-up growth paradigm of self-assembly to create them we not only learn important techniques for building such complex structures, we also gain insight into how similar structural complexity arises in natural self-assembling systems. Our results fundamentally leverage hierarchical assembly processes, and use as our building blocks square "tile" components which are capable of activating and deactivating their binding "glues" a constant number of times each, based only on local interactions. We provide the first constructions capable of building arbitrary discrete self-similar fractals at scale factor 1, and many at temperature 1 (i.e. "non-cooperatively"), including the Sierpinski triangle.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Universal Simulation of Directed Systems in the abstract Tile Assembly Model Requires Undirectedness

As a mathematical model of self-assembling systems, Winfree's abstract Tile Assembly Model (aTAM) is a remarkable platform for studying the behaviors and powers of self-assembling systems. Capable of Turing universal computation, the aTAM allows algorithmic self-assembly, in which the components can be designed so that the rules governing their behaviors force them to inherently execute prescribed algorithms as they combine. Adding to its completeness, the aTAM was shown to also be intrinsically universal, which means that there exists a single tile set such that for any arbitrary input aTAM system, that tile set can be configured into a seed structure which will then cause self-assembly using that tile set to simulate the input system, capturing its full dynamics modulo only a scale factor. However, the universal simulator previously given makes use of nondeterminism in terms of tile types placed in several key locations when different assembly sequences are followed, even when simulating a directed system, meaning one that has exactly one unique terminal assembly. The question then became whether or not that nondeterminism is fundamentally required. Here, we answer that in the affirmative: the class of directed systems in the aTAM is not intrinsically universal, meaning there is no universal simulator for directed systems which itself is always directed. This provides insight into the role of nondeterminism in self-assembly, which is itself a fundamentally nondeterministic process. To achieve this result we leverage powerful results of computational complexity hierarchies, including tight bounds on both best and worst-case complexities of decidable languages, to design systems with precisely controllable space resources available to embedded computations. We also develop novel techniques for designing systems containing subsystems with disjoint, mutually exclusive computational powers.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Computing in continuous space with self-assembling polygonal tiles

In this paper we investigate the computational power of the polygonal tile assembly model (polygonal TAM) at temperature 1, i.e. in non-cooperative systems. The polygonal TAM is an extension of Winfree's abstract tile assembly model (aTAM) which not only allows for square tiles (as in the aTAM) but also allows for tile shapes that are polygons. Although a number of self-assembly results have shown computational universality at temperature 1, these are the first results to do so by fundamentally relying on tile placements in continuous, rather than discrete, space. With the square tiles of the aTAM, it is conjectured that the class of temperature 1 systems is not computationally universal. Here we show that the class of systems whose tiles are composed of a regular polygon P with n > 6 sides is computationally universal. On the other hand, we show that the class of systems whose tiles consist of a regular polygon P with n <= 6 cannot compute using any known techniques. In addition, we show a number of classes of systems whose tiles consist of a non-regular polygon with n >= 3 sides are computationally universal.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Reflections on Tiles (in Self-Assembly)

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.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

The Simulation Powers and Limitations of Higher Temperature Hierarchical Self-Assembly Systems

In this paper, we extend existing results about simulation and intrinsic universality in a model of tile-based self-assembly. Namely, we work within the 2-Handed Assembly Model (2HAM), which is a model of self-assembly in which assemblies are formed by square tiles that are allowed to combine, using glues along their edges, individually or as pairs of arbitrarily large assemblies in a hierarchical manner, and we explore the abilities of these systems to simulate each other when the simulating systems have a higher "temperature" parameter, which is a system wide threshold dictating how many glue bonds must be formed between two assemblies to allow them to combine. It has previously been shown that systems with lower temperatures cannot simulate arbitrary systems with higher temperatures, and also that systems at some higher temperatures can simulate those at particular lower temperatures, creating an infinite set of infinite hierarchies of 2HAM systems with strictly increasing simulation power within each hierarchy. These previous results relied on two different definitions of simulation, one (strong simulation) seemingly more restrictive than the other (standard simulation), but which have previously not been proven to be distinct. Here we prove distinctions between them by first fully characterizing the set of pairs of temperatures such that the high temperature systems are intrinsically universal for the lower temperature systems (i.e. one tile set at the higher temperature can simulate any at the lower) using strong simulation. This includes the first impossibility result for simulation downward in temperature. We then show that lower temperature systems which cannot be simulated by higher temperature systems using the strong definition, can in fact be simulated using the standard definition, proving the distinction between the types of simulation.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Binary pattern tile set synthesis is NP-hard

In the field of algorithmic self-assembly, a long-standing unproven conjecture has been that of the NP-hardness of binary pattern tile set synthesis (2-PATS). The $k$-PATS problem is that of designing a tile assembly system with the smallest number of tile types which will self-assemble an input pattern of $k$ colors. Of both theoretical and practical significance, $k$-PATS has been studied in a series of papers which have shown $k$-PATS to be NP-hard for $k = 60$, $k = 29$, and then $k = 11$. In this paper, we close the fundamental conjecture that 2-PATS is NP-hard, concluding this line of study. While most of our proof relies on standard mathematical proof techniques, one crucial lemma makes use of a computer-assisted proof, which is a relatively novel but increasingly utilized paradigm for deriving proofs for complex mathematical problems. This tool is especially powerful for attacking combinatorial problems, as exemplified by the proof of the four color theorem by Appel and Haken (simplified later by Robertson, Sanders, Seymour, and Thomas) or the recent important advance on the Erdős discrepancy problem by Konev and Lisitsa using computer programs. We utilize a massively parallel algorithm and thus turn an otherwise intractable portion of our proof into a program which requires approximately a year of computation time, bringing the use of computer-assisted proofs to a new scale. We fully detail the algorithm employed by our code, and make the code freely available online.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Doubles and Negatives are Positive (in Self-Assembly)

In the abstract Tile Assembly Model (aTAM), the phenomenon of cooperation occurs when the attachment of a new tile to a growing assembly requires it to bind to more than one tile already in the assembly. Often referred to as ``temperature-2'' systems, those which employ cooperation are known to be quite powerful (i.e. they are computationally universal and can build an enormous variety of shapes and structures). Conversely, aTAM systems which do not enforce cooperative behavior, a.k.a. ``temperature-1'' systems, are conjectured to be relatively very weak, likely to be unable to perform complex computations or algorithmically direct the process of self-assembly. Nonetheless, a variety of models based on slight modifications to the aTAM have been developed in which temperature-1 systems are in fact capable of Turing universal computation through a restricted notion of cooperation. Despite that power, though, several of those models have previously been proven to be unable to perform or simulate the stronger form of cooperation exhibited by temperature-2 aTAM systems. In this paper, we first prove that another model in which temperature-1 systems are computationally universal, namely the restricted glue TAM (rgTAM) in which tiles are allowed to have edges which exhibit repulsive forces, is also unable to simulate the strongly cooperative behavior of the temperature-2 aTAM. We then show that by combining the properties of two such models, the Dupled Tile Assembly Model (DTAM) and the rgTAM into the DrgTAM, we derive a model which is actually more powerful at temperature-1 than the aTAM at temperature-2. Specifically, the DrgTAM, at temperature-1, can simulate any aTAM system of any temperature, and it also contains systems which cannot be simulated by any system in the aTAM.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

The Power of Duples (in Self-Assembly): It's Not So Hip To Be Square

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 show that the DaTAM doesn't provide asymptotic improvements over the aTAM in its ability to efficiently build thin rectangles. 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.

0 citations0 reviewsNo code linkedOpen 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 $U$ 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 $τ\geq 2$, temperature-$τ$ 2HAM tile systems are indeed intrinsically universal: in other words, for each $τ$ there is a single universal 2HAM tile set $U$ 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.

0 citations0 reviewsNo code linkedOpen 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 $P$ of size 3 or greater, there exists a temperature-1 polyTAM system containing only shape-$P$ 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.

0 citations0 reviewsNo code linkedOpen 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.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Intrinsic universality in tile self-assembly requires cooperation

We prove a negative result on the power of a model of algorithmic self-assembly for which it has been notoriously difficult to find general techniques and results. Specifically, we prove that Winfree's abstract Tile Assembly Model, when restricted to use noncooperative tile binding, is not intrinsically universal. This stands in stark contrast to the recent result that, via cooperative binding, the abstract Tile Assembly Model is indeed intrinsically universal. Noncooperative self-assembly, also known as "temperature 1", is where tiles bind to each other if they match on one or more sides, whereas cooperative binding requires binding on multiple sides. Our result shows that the change from single- to multi-sided binding qualitatively improves the kinds of dynamics and behavior that these models of nanoscale self-assembly are capable of. Our lower bound on simulation power holds in both two and three dimensions; the latter being quite surprising given that three-dimensional noncooperative tile assembly systems simulate Turing machines. On the positive side, we exhibit a three-dimensional noncooperative self-assembly tile set capable of simulating any two-dimensional noncooperative self-assembly system. Our negative result can be interpreted to mean that Turing universal algorithmic behavior in self-assembly does not imply the ability to simulate arbitrary algorithmic self-assembly processes.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

On the Equivalence of Cellular Automata and the Tile Assembly Model

In this paper, we explore relationships between two models of systems which are governed by only the local interactions of large collections of simple components: cellular automata (CA) and the abstract Tile Assembly Model (aTAM). While sharing several similarities, the models have fundamental differences, most notably the dynamic nature of CA (in which every cell location is allowed to change state an infinite number of times) versus the static nature of the aTAM (in which tiles are static components that can never change or be removed once they attach to a growing assembly). We work with 2-dimensional systems in both models, and for our results we first define what it means for CA systems to simulate aTAM systems, and then for aTAM systems to simulate CA systems. We use notions of simulate which are similar to those used in the study of intrinsic universality since they are in some sense strict, but also intuitively natural notions of simulation. We then demonstrate a particular nondeterministic CA which can be configured so that it can simulate any arbitrary aTAM system, and finally an aTAM tile set which can be configured so that it can be used to simulate any arbitrary nondeterministic CA system which begins with a finite initial configuration.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Signal Transmission Across Tile Assemblies: 3D Static Tiles Simulate Active Self-Assembly by 2D Signal-Passing Tiles

The 2-Handed Assembly Model (2HAM) is a tile-based self-assembly model in which, typically beginning from single tiles, arbitrarily large aggregations of static tiles combine in pairs to form structures. The Signal-passing Tile Assembly Model (STAM) is an extension of the 2HAM in which the tiles are dynamically changing components which are able to alter their binding domains as they bind together. For our first result, we demonstrate useful techniques and transformations for converting an arbitrarily complex STAM$^+$ tile set into an STAM$^+$ tile set where every tile has a constant, low amount of complexity, in terms of the number and types of ``signals'' they can send, with a trade off in scale factor. Using these simplifications, we prove that for each temperature $τ>1$ there exists a 3D tile set in the 2HAM which is intrinsically universal for the class of all 2D STAM$^+$ systems at temperature $τ$ (where the STAM$^+$ does not make use of the STAM's power of glue deactivation and assembly breaking, as the tile components of the 2HAM are static and unable to change or break bonds). This means that there is a single tile set $U$ in the 3D 2HAM which can, for an arbitrarily complex STAM$^+$ system $S$, be configured with a single input configuration which causes $U$ to exactly simulate $S$ at a scale factor dependent upon $S$. Furthermore, this simulation uses only two planes of the third dimension. This implies that there exists a 3D tile set at temperature $2$ in the 2HAM which is intrinsically universal for the class of all 2D STAM$^+$ systems at temperature $1$. Moreover, we show that for each temperature $τ>1$ there exists an STAM$^+$ tile set which is intrinsically universal for the class of all 2D STAM$^+$ systems at temperature $τ$, including the case where $τ= 1$.

0 citations0 reviewsNo code linkedOpen 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 \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 \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 \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 \times N$ square with an rgTAS is $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 $\ge 1$. These results consist of a construction with $O(\log n)$ tile complexity for building $N \times N$ squares, and one which simulates a Turing machine but with a greater scaling factor than for the rgTAS construction.

0 citations0 reviewsNo code linkedOpen 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.

0 citations0 reviewsNo code linkedOpen 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).

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Two Hands Are Better Than One (up to constant factors)

We study the difference between the standard seeded model of tile self-assembly, and the "seedless" two-handed model of tile self-assembly. Most of our results suggest that the two-handed model is more powerful. In particular, we show how to simulate any seeded system with a two-handed system that is essentially just a constant factor larger. We exhibit finite shapes with a busy-beaver separation in the number of distinct tiles required by seeded versus two-handed, and exhibit an infinite shape that can be constructed two-handed but not seeded. Finally, we show that verifying whether a given system uniquely assembles a desired supertile is co-NP-complete in the two-handed model, while it was known to be polynomially solvable in the seeded model.

0 citations0 reviewsNo code linkedOpen 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 \times n$ squares to $Θ(\sqrt{\log n})$ at temperature 1 for the most simple model which meets a lower bound from Kolmogorov complexity, and $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)$ 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.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Simulation of Self-Assembly in the Abstract Tile Assembly Model with ISU TAS

Since its introduction by Erik Winfree in 1998, the abstract Tile Assembly Model (aTAM) has inspired a wealth of research. As an abstract model for tile based self-assembly, it has proven to be remarkably powerful and expressive in terms of the structures which can self-assemble within it. As research has progressed in the aTAM, the self-assembling structures being studied have become progressively more complex. This increasing complexity, along with a need for standardization of definitions and tools among researchers, motivated the development of the Iowa State University Tile Assembly Simulator (ISU TAS). ISU TAS is a graphical simulator and tile set editor for designing and building 2-D and 3-D aTAM tile assembly systems and simulating their self-assembly. This paper reviews the features and functionality of ISU TAS and describes how it can be used to further research into the complexities of the aTAM. Software and source code are available at http://www.cs.iastate.edu/~lnsa.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Identifying Shapes Using Self-Assembly (extended abstract)

In this paper, we introduce the following problem in the theory of algorithmic self-assembly: given an input shape as the seed of a tile-based self-assembly system, design a finite tile set that can, in some sense, uniquely identify whether or not the given input shape--drawn from a very general class of shapes--matches a particular target shape. We first study the complexity of correctly identifying squares. Then we investigate the complexity associated with the identification of a considerably more general class of non-square, hole-free shapes.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Intrinsic Universality in Self-Assembly

We show that the Tile Assembly Model exhibits a strong notion of universality where the goal is to give a single tile assembly system that simulates the behavior of any other tile assembly system. We give a tile assembly system that is capable of simulating a very wide class of tile systems, including itself. Specifically, we give a tile set that simulates the assembly of any tile assembly system in a class of systems that we call \emph{locally consistent}: each tile binds with exactly the strength needed to stay attached, and that there are no glue mismatches between tiles in any produced assembly. Our construction is reminiscent of the studies of \emph{intrinsic universality} of cellular automata by Ollinger and others, in the sense that our simulation of a tile system $T$ by a tile system $U$ represents each tile in an assembly produced by $T$ by a $c \times c$ block of tiles in $U$, where $c$ is a constant depending on $T$ but not on the size of the assembly $T$ produces (which may in fact be infinite). Also, our construction improves on earlier simulations of tile assembly systems by other tile assembly systems (in particular, those of Soloveichik and Winfree, and of Demaine et al.) in that we simulate the actual process of self-assembly, not just the end result, as in Soloveichik and Winfree's construction, and we do not discriminate against infinite structures. Both previous results simulate only temperature 1 systems, whereas our construction simulates tile assembly systems operating at temperature 2.

0 citations0 reviewsNo code linkedOpen 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.

0 citations0 reviewsNo code linkedOpen 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.

0 citations0 reviewsNo code linkedOpen access