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.DNA.2020.10
URN: urn:nbn:de:0030-drops-129635
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12963/
Go to the corresponding LIPIcs Volume Portal

Caballero, David ; Gomez, Timothy ; Schweller, Robert ; Wylie, Tim

Verification and Computation in Restricted Tile Automata

pdf-format:
LIPIcs-DNA-2020-10.pdf (0.7 MB)

Abstract

Many models of self-assembly have been shown to be capable of performing computation. Tile Automata was recently introduced combining features of both Celluar Automata and the 2-Handed Model of self-assembly both capable of universal computation. In this work we study the complexity of Tile Automata utilizing features inherited from the two models mentioned above. We first present a construction for simulating Turing Machines that performs both covert and fuel efficient computation. We then explore the capabilities of limited Tile Automata systems such as 1-Dimensional systems (all assemblies are of height 1) and freezing Systems (tiles may not repeat states). Using these results we provide a connection between the problem of finding the largest uniquely producible assembly using n states and the busy beaver problem for non-freezing systems and provide a freezing system capable of uniquely assembling an assembly whose length is exponential in the number of states of the system. We finish by exploring the complexity of the Unique Assembly Verification problem in Tile Automata with different limitations such as freezing and systems without the power of detachment.

BibTeX - Entry

@InProceedings{caballero_et_al:LIPIcs:2020:12963,
  author =	{David Caballero and Timothy Gomez and Robert Schweller and Tim Wylie},
  title =	{{Verification and Computation in Restricted Tile Automata}},
  booktitle =	{26th International Conference on DNA Computing and Molecular Programming (DNA 26)},
  pages =	{10:1--10:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-163-4},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{174},
  editor =	{Cody Geary and Matthew J. Patitz},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/12963},
  URN =		{urn:nbn:de:0030-drops-129635},
  doi =		{10.4230/LIPIcs.DNA.2020.10},
  annote =	{Keywords: Tile Automata, Turing Machines, Unique Assembly Verification}
}

Keywords: Tile Automata, Turing Machines, Unique Assembly Verification
Collection: 26th International Conference on DNA Computing and Molecular Programming (DNA 26)
Issue Date: 2020
Date of publication: 04.09.2020

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