License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.DNA.27.6
URN: urn:nbn:de:0030-drops-146735
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/14673/
Go to the corresponding LIPIcs Volume Portal

Meunier, Pierre-Étienne ; Regnault, Damien

Directed Non-Cooperative Tile Assembly Is Decidable

pdf-format:
LIPIcs-DNA-27-6.pdf (0.7 MB)

Abstract

We provide a complete characterisation of all final states of a model called directed non-cooperative tile self-assembly, also called directed temperature 1 tile assembly, which proves that this model cannot possibly perform Turing computation. This model is a deterministic version of the more general undirected model, whose computational power is still open. Our result uses recent results in the domain, and solves a conjecture formalised in 2011. We believe that this is a major step towards understanding the full model.
Temperature 1 tile assembly can be seen as a two-dimensional extension of finite automata, where geometry provides a form of memory and synchronisation, yet the full power of these "geometric blockings" was still largely unknown until recently (note that nontrivial algorithms which are able to build larger structures than the naive constructions have been found).

BibTeX - Entry

@InProceedings{meunier_et_al:LIPIcs.DNA.27.6,
  author =	{Meunier, Pierre-\'{E}tienne and Regnault, Damien},
  title =	{{Directed Non-Cooperative Tile Assembly Is Decidable}},
  booktitle =	{27th International Conference on DNA Computing and Molecular Programming (DNA 27)},
  pages =	{6:1--6:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-205-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{205},
  editor =	{Lakin, Matthew R. and \v{S}ulc, Petr},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/14673},
  URN =		{urn:nbn:de:0030-drops-146735},
  doi =		{10.4230/LIPIcs.DNA.27.6},
  annote =	{Keywords: Self-assembly, Molecular Computing, Models of Computation, Computational Geometry}
}

Keywords: Self-assembly, Molecular Computing, Models of Computation, Computational Geometry
Collection: 27th International Conference on DNA Computing and Molecular Programming (DNA 27)
Issue Date: 2021
Date of publication: 08.09.2021

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