论文标题
在有限的主动自组装中，建筑方形具有最佳状态复杂性
Building Squares with Optimal State Complexity in Restricted Active Self-Assembly
论文作者
论文摘要
Tile Automata是一个最近定义的自组装模型，它借用了从Cellular Automata的许多概念来创建主动的自组装系统，在组件中可能会发生变化而无需附件。该模型已被证明是有力的，但是许多基本问题尚未探讨。在这里，我们研究了在种子瓷砖自动机系统中组装$ n \ times n $正方形的状态复杂性，在该系统中，生长从种子开始，瓷砖可能一次连接一个，类似于抽象瓷砖组装模型。我们为三类种子瓷砖自动机系统（全部不超支）提供最佳界限，这些系统在过渡规则中允许的复杂性量有所不同。我们表明，通常，种子瓷砖自动机系统需要$θ{（\ log^{\ frac {1} {4}}} n）} $状态。对于单截止系统，只有一个状态可以在过渡规则中发生变化，我们显示了$θ{（\ log^{\ frac {1} {1} {3}} n）} $的限制，对于确定性系统，每对状态只有一个相关的过渡规则，big frac frac {\ frac {\ fog n} n}）^\ frac {1} {2}）$。
Tile Automata is a recently defined model of self-assembly that borrows many concepts from cellular automata to create active self-assembling systems where changes may be occurring within an assembly without requiring attachment. This model has been shown to be powerful, but many fundamental questions have yet to be explored. Here, we study the state complexity of assembling $n \times n$ squares in seeded Tile Automata systems where growth starts from a seed and tiles may attach one at a time, similar to the abstract Tile Assembly Model. We provide optimal bounds for three classes of seeded Tile Automata systems (all without detachment), which vary in the amount of complexity allowed in the transition rules. We show that, in general, seeded Tile Automata systems require $Θ{(\log^{\frac{1}{4}} n)}$ states. For single-transition systems, where only one state may change in a transition rule, we show a bound of $Θ{(\log^{\frac{1}{3}} n)}$, and for deterministic systems, where each pair of states may only have one associated transition rule, a bound of $Θ( (\frac{\log n}{\log \log n})^\frac{1}{2} )$.
