AF: Small: RUI: Unifying Self-Assembly Through Tile Automata

AF：小：RUI：通过平铺自动机统一自组装

• 批准号: 1817602
• 负责人: Robert Schweller
• 金额: $ 49.5万
• 依托单位: The University of Texas Rio Grande Valley
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2018
• 资助国家: 美国
• 起止时间: 2018-07-01 至 2022-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1817602&HistoricalAwards=false
• 关键词: AF; Small; RUI; Unifying; Self

Self-assembly is the bottom-up process by which simple unorganized components autonomously combine to form large complex structures. This process is abundant in nature as a key underlying mechanism for the construction of biological organisms. The local interactions of simple self-assembling systems are often capable of simulating general purpose computation as well, leading researchers to begin using self-assembly technology as a tool for the precise algorithmic manipulation of matter at nano-scales. This project introduces and explores the Tile Automata abstract model of self-assembly to serve as a framework for unifying the diverse set of established and experimentally motivated models of self-assembly. The work develops fundamental theoretical results within this framework, and connects various established experimental models using Tile Automata as a central hub - yielding surprising connections between previously disparate models. Beyond providing a foundation for a theory of self-assembly, this framework also provides an important tool to influence and simplify experimental work. Some aspects of the DNA-based model are implausible, but by using the connections with Tile Automata, the work will show that the power of the unrealistic features may be attained within a more plausible limited version of the model, thus providing a guide for experimental implementation. A major goal of this work is to provide undergraduate research opportunities and increase Computer Science research participation among underrepresented groups. Another outcome of this work will be the continued development of software simulators for various models as well as the implementation of new models. The project introduces a mathematical model termed Tile Automata that combines the local interaction rules from Cellular Automata systems with self-assembly properties from tile-based self-assembly models. Although the majority of self-assembly models are motivated by experimental techniques, the abstractions may unintentionally limit or unrealistically extend the power of the system. Part of the research is to identify and remove these properties. The first focus of this work is on the DNA based signal tile model where unrealistic aspects of when signals fire may be exploited to achieve results within the model that are impossible experimentally. The investigators address these issues by proposing multiple small variations to signal passing, which each remove the issue with the original model. Each variation is then tied to the unifying framework and equality is achieved within a scale factor for each variation and for the original signal tile model, thereby providing an experimentally feasible path for achieving the full power of the model. The second focus is on repulsive forces within self-assembly models, which provide an enormous amount of power and allow for unrealistic communication across arbitrary distance within the model. The project seeks to show that repulsive forces may be simulated within the Tile Automata framework if assemblies are allowed to temporarily connect to check compatibility and then disconnect if not, which shows equivalent capabilities can be achieved without the improbable communication. The third focus is on other common self-assembly models and active or movement-based models.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.

自组装是自下而上的过程，通过这个过程，简单的无组织的组件自主地结合在一起，形成大型的复杂结构。这一过程在自然界中是丰富的，是构建生物有机体的关键基础机制。简单的自组装系统的局部相互作用通常也能够模拟通用计算，这使得研究人员开始使用自组装技术作为一种工具，在纳米尺度上对物质进行精确的算法操作。本项目引入并探索了自组装的瓦片自动机抽象模型，以作为统一各种已建立的和实验激励的自组装模型集的框架。这项工作在这个框架内发展了基本的理论结果，并使用瓷砖自动机作为中心枢纽连接各种已建立的实验模型-在以前不同的模型之间产生了令人惊讶的联系。除了为自组装理论提供基础外，这个框架还提供了影响和简化实验工作的重要工具。基于DNA的模型的某些方面是不可信的，但通过使用与瓷砖自动机的联系，工作将表明，不现实特征的力量可能在更可信的有限版本的模型中获得，从而为实验实现提供指导。这项工作的一个主要目标是为本科生提供研究机会，并在代表性不足的群体中增加计算机科学研究的参与度。这项工作的另一个成果将是继续开发各种模型的软件模拟器以及实施新的模型。该项目引入了一个名为瓦片自动机的数学模型，该模型结合了元胞自动机系统中的局部交互规则和瓦片自组装模型中的自组装特性。尽管大多数自组装模型是由实验技术驱动的，但抽象可能会无意中限制或不切实际地扩展系统的能力。研究的一部分是识别和删除这些属性。这项工作的第一个重点是基于DNA的信号瓦片模型，在该模型中，可以利用信号发射的不现实方面来实现在实验中不可能实现的结果。调查人员通过对信号传递提出多个小的变化来解决这些问题，每个变化都消除了原始模型的问题。然后，每个变化被绑定到统一的框架，并且对于每个变化和对于原始信号瓦片模型，在比例因子内实现相等，从而为实现模型的全部功率提供了实验上可行的路径。第二个重点是自组装模型中的排斥力，这种模型提供了巨大的能量，并允许在模型内跨越任意距离进行不切实际的交流。该项目试图证明，如果允许组件临时连接以检查兼容性，然后断开连接，则可以在Tile Automata框架内模拟排斥力，这表明在没有不可能的通信的情况下，可以实现同等的能力。第三个重点是其他常见的自组装模型和主动或基于运动的模型。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

项目成果

Signal Passing Self-Assembly Simulates Tile Automata

信号传递自组装模拟瓦片自动机

• DOI: 10.4230/lipics.isaac.2020.53
• 发表时间: 2020
• 期刊: International Symposium on Algorithms and Computation
• 作者: Cantu, Angel A.;Luchsinger, Austin;Schweller, Robert;Wylie, Tim
• 通讯作者: Wylie, Tim

Relocation with uniform external control in limited directions

在有限方向上进行统一外部控制的搬迁

• 发表时间: 2019
• 期刊: JCDCGGG
• 作者: Balanza-Martinez, Jose;Caballero, David;Cantu, Angel;Gomez, Timothy;Luchsinger, Austin;Schweller, Robert;Wylie, Tim
• 通讯作者: Wylie, Tim

Tile Pattern-Building Games on a Grid are PSPACE-complete

网格上的平铺图案构建游戏是 PSPACE 完整的

• 发表时间: 2018
• 期刊: and Games
• 作者: Cantu, Angel A.;Gonzalez, Arturo;Lozano, Cesar;Luchsinger, Austin;Medina, Eduardo;Martinez, Fernando;Ramirez, Arnoldo;Wylie, Tim
• 通讯作者: Wylie, Tim

Freezing Simulates Non-freezing Tile Automata

• DOI: 10.1007/978-3-030-00030-1_10
• 发表时间: 2018-10
• 作者: Cameron T. Chalk;Austin Luchsinger;Eric Martinez;R. Schweller;Andrew Winslow;Tim Wylie

Covert Computation in Self-Assembled Circuits

• DOI: 10.1007/s00453-020-00764-w
• 发表时间: 2019-08
• 期刊: Algorithmica
• 影响因子: 1.1
• 作者: Angel A. Cantu;Austin Luchsinger;R. Schweller;Tim Wylie