BZPEERReading, trust and collaboration for research
Menu

Discover

GraphFollow connections around a paper, topic or saved view.

Workspaces

HomePick up where your research flow left off.InboxHandle requests, replies and notifications from one place.CollectionsCurate reading lists, evidence sets and shareable dossiers.ResearchSee your private provenance graph, trail and imports.CollaborationMove from discovery into focused discussion rooms.PublishDraft, preview and publish full-text research articles.

Network

ExpertsFind specialists worth following or asking for help.CommunitiesJoin research circles organized around shared work.PartnersSee external organizations active around the same topics.

Opportunities

ListingsBrowse roles, calls and collaborations with clearer fit signals.

Account

Log inReturn to your reading and collaboration workspace.Create accountStart saving work, following people and joining teams.
Log inCreate account

Researcher profile

Jacob Hendricks

Jacob Hendricks contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
Emerging TechnologiesComputational ComplexityData Structures and AlgorithmsFormal Languages and Automata TheoryLogic in Computer Sciencenlin.CG

Trust snapshot

Quick read

Trust 21 - EmergingVerification L1Unclaimed author
6works
0followers
6topics
4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Identity and collaboration

How to connect with this researcher

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Log in to claim

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

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

Published work

6 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
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

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

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