New bounds on the tile complexity of thin rectangles at temperature-1

DOI10.1007/978-3-030-26807-7_6zbMATH Open1504.68069arXiv1808.04358OpenAlexW2966809659MaRDI QIDQ2278613FDOQ2278613

Authors: David Furcy, Scott M. Summers, Christian Wendlandt 

Publication date: 5 December 2019

Abstract: In this paper, we study the minimum number of unique tile types required for the self-assembly of thin rectangles in Winfree's abstract Tile Assembly Model (aTAM), restricted to temperature-1. Using Catalan numbers, planar self-assembly and a restricted version of the Window Movie Lemma, we derive a new lower bound on the tile complexity of thin rectangles at temperature-1 in 2D. Then, we give the first known upper bound on the tile complexity of ``just-barely 3D thin rectangles at temperature-1, where tiles are allowed to be placed at most one step into the third dimension. Our construction, which produces a unique terminal assembly, implements a just-barely 3D, zig-zag counter, whose base depends on the dimensions of the target rectangle, and whose digits are encoded geometrically, vertically-oriented and in binary.

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

Recommendations

• Self-assembly of and optimal encoding within thin rectangles at temperature-1 in 3D
• Complexities for generalized models of self-assembly
• Complexities for Generalized Models of Self-Assembly
• Optimal program-size complexity for self-assembly at temperature 1 in 3D

Mathematics Subject Classification ID

Other nonclassical models of computation (68Q09) Biologically inspired models of computation (DNA computing, membrane computing, etc.) (68Q07)

Cited In (5)

• Building squares with optimal state complexity in restricted active self-assembly
• ALCH: an imperative language for chemical reaction network-controlled tile assembly
• Self-assembly of and optimal encoding within thin rectangles at temperature-1 in 3D
• Improved lower and upper bounds on the tile complexity of uniquely self-assembling a thin rectangle non-cooperatively in 3D
• Improved lower and upper bounds on the tile complexity of uniquely self-assembling a thin rectangle non-cooperatively in 3D

This page was built for publication: New bounds on the tile complexity of thin rectangles at temperature-1

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