New Bounds on the Tile Complexity of Thin Rectangles at Temperature-1
| Autor: | David Furcy, Scott M. Summers, Christian Wendlandt |
|---|---|
| Rok vydání: | 2019 |
| Předmět: |
0303 health sciences
Lemma (mathematics) Dimension (graph theory) Binary number 0102 computer and information sciences Base (topology) 01 natural sciences Upper and lower bounds Catalan number Combinatorics 03 medical and health sciences 010201 computation theory & mathematics visual_art visual_art.visual_art_medium Rectangle Tile 030304 developmental biology Mathematics |
| Zdroj: | Lecture Notes in Computer Science ISBN: 9783030268060 DNA |
| DOI: | 10.1007/978-3-030-26807-7_6 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|