Geometric tiles and powers and limitations of geometric hindrance in self-assembly

DOI10.1007/S11047-021-09846-2MaRDI QIDQ6095490zbMATH OpenFDO

Authors Daniel Hader, Matthew J. Patitz

Publication date 8 September 2023

Published in Natural Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1903.05774

Mathematics Subject Classification ID

Other nonclassical models of computation (68Q09)

Abstract: Tile-based self-assembly systems are capable of universal computation and algorithmically-directed growth. Systems capable of such behavior typically make use of "glue cooperation" in which the glues on at least $2$ sides of a tile must match and bind to those exposed on the perimeter of an assembly for that tile to attach. However, several models have been developed which utilize "weak cooperation", where only a single glue needs to bind but other preventative forces (such as geometric, or steric, hindrance) provide additional selection for which tiles may attach, and where this allows for algorithmic behavior. In this paper we first work in a model where tiles are allowed to have geometric bumps and dents on their edges. We show how such tiles can simulate systems of square tiles with complex glue functions (using asymptotically optimal sizes of bumps and dents), and also how they can simulate weakly cooperative systems in a model which allows for duples (i.e. tiles either twice as long or twice as tall as square tiles). We then show that with only weak cooperation via geometric hindrance, no system in any model can simulate even a class of tightly constrained, deterministic cooperative systems, further defining the boundary of what is possible using this tool.

Recommendations

• Geometric tiles and powers and limitations of geometric hindrance in self-assembly
• Self-assembly with geometric tiles
• An introduction to tile-based self-assembly and a survey of recent results
• An introduction to tile-based self-assembly
• A brief tour of theoretical tile self-assembly
• Triangular and hexagonal tile self-assembly systems
• Size-dependent tile self-assembly: constant-height rectangles and stability
• Self assembly of rectangular shapes on concentration programming and probabilistic tile assembly models

Cites work

• Complexity of Graph Self-assembly in Accretive Systems and Self-destructible Systems
• Complexity of Self‐Assembled Shapes
• Computability and complexity in self-assembly
• Computing in continuous space with self-assembling polygonal tiles (extended abstract)
• Exact shapes and Turing universality at temperature 1 with a single negative glue
• Geometric tiles and powers and limitations of geometric hindrance in self-assembly
• Intrinsic universality in tile self-assembly requires cooperation
• Limitations of self-assembly at temperature 1
• One tile to rule them all: simulating any tile assembly system with a single universal tile
• Self-assembly with geometric tiles
• Strict self-assembly of discrete Sierpinski triangles
• Temperature 1 self-assembly: deterministic assembly in 3D and probabilistic assembly in 2D
• The non-cooperative tile assembly model is not intrinsically universal or capable of bounded Turing machine simulation
• The power of duples (in self-assembly): it's not so hip to be square
• The program-size complexity of self-assembled squares (extended abstract)
• Universal computation with arbitrary polyomino tiles in non-cooperative self-assembly

Cited in

(2)

• Geometric tiles and powers and limitations of geometric hindrance in self-assembly
• Building squares with optimal state complexity in restricted active self-assembly

This page was built for publication: Geometric tiles and powers and limitations of geometric hindrance in self-assembly

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6095490)