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.

自组装是一种自下而上的过程，通过这种过程，简单的无组织部件自主地联合收割机组合成大型复杂结构。这个过程在自然界中是丰富的，是构建生物有机体的关键基础机制。简单的自组装系统的局部相互作用通常也能够模拟通用计算，这使得研究人员开始使用自组装技术作为在纳米尺度上对物质进行精确算法操作的工具。该项目介绍和探索了自组装的瓦片自动机抽象模型，以作为统一自组装的各种已建立和实验动机模型的框架。这项工作在这个框架内开发了基本的理论结果，并使用Tile Automata作为中心枢纽连接了各种已建立的实验模型-在以前不同的模型之间产生了令人惊讶的联系。除了为自组装理论提供基础之外，这个框架还提供了影响和简化实验工作的重要工具。基于DNA的模型的某些方面是不可信的，但通过使用与Tile Automata的连接，这项工作将表明，不切实际的功能可以在模型的更合理的有限版本中获得，从而为实验实施提供指导。这项工作的一个主要目标是提供本科生的研究机会，并增加代表性不足的群体中的计算机科学研究参与。这项工作的另一个成果将是继续为各种型号开发软件模拟器以及实施新型号。该项目引入了一种称为Tile Automata的数学模型，该模型将元胞自动机系统的局部交互规则与基于Tile的自组装模型的自组装特性相结合。虽然大多数自组装模型的动机是实验技术，但抽象可能会无意中限制或不切实际地扩展系统的功能。研究的一部分是识别和删除这些属性。这项工作的第一个重点是基于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