License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ISAAC.2020.53
URN: urn:nbn:de:0030-drops-133978
URL: https://drops.dagstuhl.de/opus/volltexte/2020/13397/
Go to the corresponding LIPIcs Volume Portal

Cantu, Angel A. ; Luchsinger, Austin ; Schweller, Robert ; Wylie, Tim

Signal Passing Self-Assembly Simulates Tile Automata

pdf-format:
LIPIcs-ISAAC-2020-53.pdf (1 MB)

Abstract

The natural process of self-assembly has been studied through various abstract models due to the abundant applications that benefit from self-assembly. Many of these different models emerged in an effort to capture and understand the fundamental properties of different physical systems and the mechanisms by which assembly may occur. A newly proposed model, known as Tile Automata, offers an abstract toolkit to analyze and compare the algorithmic properties of different self-assembly systems. In this paper, we show that for every Tile Automata system, there exists a Signal-passing Tile Assembly system that can simulate it. Finally, we connect our result with a recent discovery showing that Tile Automata can simulate Amoebot programmable matter systems, thus showing that the Signal-passing Tile Assembly can simulate any Amoebot system.

BibTeX - Entry

@InProceedings{cantu_et_al:LIPIcs:2020:13397,
  author =	{Angel A. Cantu and Austin Luchsinger and Robert Schweller and Tim Wylie},
  title =	{{Signal Passing Self-Assembly Simulates Tile Automata}},
  booktitle =	{31st International Symposium on Algorithms and Computation (ISAAC 2020)},
  pages =	{53:1--53:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-173-3},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{181},
  editor =	{Yixin Cao and Siu-Wing Cheng and Minming Li},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/13397},
  URN =		{urn:nbn:de:0030-drops-133978},
  doi =		{10.4230/LIPIcs.ISAAC.2020.53},
  annote =	{Keywords: self-assembly, signal-passing tile assembly model, tile automata, cellular automata, simulation}
}

Keywords: self-assembly, signal-passing tile assembly model, tile automata, cellular automata, simulation
Collection: 31st International Symposium on Algorithms and Computation (ISAAC 2020)
Issue Date: 2020
Date of publication: 04.12.2020
Supplementary Material: Supplemental videos of example STAM signal tools used in this paper may be found at https://asarg.hackresearch.com/main/isaac-2020/.

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI