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 的信号瓦片模型，其中信号发射时的不切实际的方面可能被利用来实现模型中实验不可能实现的结果。研究人员通过提出信号传递的多个小变化来解决这些问题，每个变化都消除了原始模型的问题。然后将每个变体与统一框架联系起来，并在每个变体和原始信号瓦片模型的比例因子内实现相等，从而为实现模型的全部功能提供实验上可行的路径。第二个焦点是自组装模型中的排斥力，它提供了巨大的力量，并允许在模型内跨越任意距离进行不切实际的通信。该项目试图表明，如果允许程序集临时连接以检查兼容性，则可以在平铺自动机框架内模拟排斥力，如果不允许，则断开连接，这表明无需不可能的通信即可实现等效功能。第三个重点是其他常见的自组装模型和主动或基于运动的模型。该奖项反映了 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