New Bounds on the Tile Complexity of Thin Rectangles at Temperature-1
New Bounds on the Tile Complexity of Thin Rectangles at Temperature-1
复制标题
DOI：
10.1007/978-3-030-26807-7_6
复制
发表时间：
2018-08
期刊：
影响因子：
--
通讯作者：
David Furcy;Scott M. Summers;Christian Wendlandt
中科院分区：
文献类型：
--
作者：
David Furcy;Scott M. Summers;Christian Wendlandt
在本文中，我们研究的最小数量的独特的瓷砖类型所需的自组装薄矩形Winfree的抽象瓷砖组装模型（aTAM），限制到温度-1。使用加泰罗尼亚数、平面自组装和窗口电影引理的限制版本，我们推导出2D中温度为-1的薄矩形瓦片复杂度的新下界。然后，我们给出了第一个已知的上限的瓷砖复杂性的“刚刚好”的3D薄矩形在温度-1，瓷砖被允许放置在最多一步到第三维。我们的构造，它产生一个独特的终端组件，实现了一个刚刚好的3D，锯齿形计数器，其基础取决于目标矩形的尺寸，其数字编码的几何，垂直方向和二进制。
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.