论文标题
在温度1处的定向瓷砖组装系统上
On the directed tile assembly systems at temperature 1
论文作者
论文摘要
我们在这里表明，在温度1处的称为定向自组装的模型无法进行复杂的计算，例如图灵机的计算。由于该模型可以看作是对有限自动机对2D语言的概括，因此逻辑方法是分两个步骤进行。第一个是开发2D泵送引理，第二个是使用此泵浦引理来对不同类型的计算进行分类。 以前，AL的Meunier已证明了抽水引理和Doty等人的存在，假设存在抽水引理，则已将不同类型的末端组装分类。因此，这两篇论文的组合解决了定向温度1的猜想……但以不完美的方式解决了。确实，由于Doty等人的工作是Meunier等人的泵浦引理的前部，因此作者假设了一个不同，更强的抽水引理。然而，Doty等人中的所有演示仍然与Meunier等人的抽水相处有关。 在本文中，我们协调了这两篇文章之间的符号，以清楚地解决定向温度1的猜想。我们还能够对可能出现在某些瓷砖组装系统中的双周期结构进行最佳描述。
We show here that a model called directed self-assembly at temperature 1 is unable to do complex computations like the ones of a Turing machine. Since this model can be seen as a generalization of finite automata to 2D languages, a logical approach is to proceed in two steps. The first one is to develop a 2D pumping lemma and the second one is to use this pumping lemma to classify the different types of possible computation. Previously, Meunier at al have proven a pumping lemma and Doty et al, assuming the existence of a pumping lemma, have classified the different types of terminal assembly. Thus the combination of these two papers solves the directed temperature 1 conjecture ... but in an imperfect way. Indeed, since the work of Doty et al is anterior to the pumping lemma of Meunier et al, the authors assumed a different and stronger pumping lemma. Nevertheless, all the demonstrations made in Doty et al still hold with the pumping lemma of Meunier et al. In this paper, we harmonize the notations between these two articles in order to clearly solve the directed temperature 1 conjecture. We are also able to give an optimal description of the bi-periodic structures which may appear in some tile assembly system.
