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

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

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.