Top

Natural Computing

17-11-2021

Verification and computation in restricted Tile Automata

Authors: David Caballero, Timothy Gomez, Robert Schweller, Tim Wylie

Published in: Natural Computing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

Many models of self-assembly have been shown to be capable of performing computation. Tile Automata was recently introduced combining features of both Cellular 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.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

We note that \(\varSigma\) does not include an “empty” state. In tile self-assembly, unlike cellular automata, positions in \({\mathbb {Z}}^2\) may have no tile (and thus no state).

When we refer to Unique Assembly allowing cycles, this requirement is omitted.

One-dimensional Tile Automata systems always have \(\tau = 1\), so we omit that parameter from T.

For this definition we consider Turing machines using a binary alphabet.

Adleman LM, Cheng Q, Goel A, Huang MDA, Kempe D, de Espanés PM, Rothemund PWK (2002) Combinatorial optimization problems in self-assembly. In: Proceedings of the 34th annual ACM symposium on theory of computing, pp 23–32

Alumbaugh JC, Daymude JJ, Demaine ED, Patitz MJ, Richa AW (2019) Simulation of programmable matter systems using active tile-based self-assembly. In: Thachuk C, Liu Y (eds) DNA computing and molecular programming. Springer, Cham, pp 140–158CrossRef

Caballero D, Gomez T, Schweller R, Wylie T (2020) Verification and Computation in Restricted Tile Automata. In: Geary C, Patitz MJ (eds) 26th international conference on DNA computing and molecular programming (DNA 26), Leibniz International Proceedings in Informatics (LIPIcs), vol. 174, pp. 10:1–10:18. Schloss Dagstuhl–Leibniz-Zentrum für Informatik, Dagstuhl, Germany. https://doi.org/10.4230/LIPIcs.DNA.2020.10. URL https://drops.dagstuhl.de/opus/volltexte/2020/12963

Caballero D, Gomez T, Schweller R, Wylie T (2021) Covert computation in staged self-assembly: Verification is pspace-complete. In: Proceedings of the 29th European Symposium on Algorithms, ESA’21

Cannon S, Demaine ED, Demaine ML, Eisenstat S, Patitz MJ, Schweller RT, Summers SM, Winslow A (2013) Two Hands Are Better Than One (up to constant factors): Self-Assembly In The 2HAM vs. aTAM. In: 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013), Leibniz International Proceedings in Informatics (LIPIcs), vol. 20, pp. 172–184. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik

Cantu AA, Luchsinger A, Schweller R, Wylie T (2020) Covert Computation in Self-Assembled Circuits. Algorithmica. https://doi.org/10.1007/s00453-020-00764-w. arXiv:1908.06068

Cantu AA, Luchsinger A, Schweller R, Wylie T (2020) Signal Passing Self-Assembly Simulates Tile Automata. In: Y. Cao, S.W. Cheng, M. Li (eds.) 31st International Symposium on Algorithms and Computation (ISAAC 2020), Leibniz International Proceedings in Informatics (LIPIcs), vol. 181, pp. 53:1–53:17. Schloss Dagstuhl–Leibniz-Zentrum für Informatik, Dagstuhl, Germany. https://doi.org/10.4230/LIPIcs.ISAAC.2020.53. URL https://drops.dagstuhl.de/opus/volltexte/2020/13397

Chalk C, Luchsinger A, Martinez E, Schweller R, Winslow A, Wylie T (2018) Freezing simulates non-freezing tile automata. In: International Conference on DNA Computing and Molecular Programming, pp. 155–172. Springer

Chalk C, Luchsinger A, Schweller R, Wylie T (2018) Self-assembly of any shape with constant tile types using high temperature. In: Proceedings of the 26th Annual European Symposium on Algorithms, ESA’18

Cook M (2004) Universality in elementary cellular automata. Complex Syst 15(1):1–40MathSciNetMATH

Daymude JJ, Hinnenthal K, Richa AW, Scheideler C (2019) Computing by programmable particles. In: Distributed computing by mobile entities: current research in moving and computing, pp 615–681. Springer, Cham

Demaine ED, Demaine ML, Fekete SP, Ishaque M, Rafalin E, Schweller RT, Souvaine DL (2008) Staged self-assembly: nanomanufacture of arbitrary shapes with o (1) glues. Natural Comput 7(3):347–370MathSciNetCrossRef

Demaine ED, Eisenstat S, Ishaque M, Winslow A (2011) One-dimensional staged self-assembly. In: Proceedings of the 17th international conference on DNA computing and molecular programming, DNA’11, pp. 100–114

Doty D, Kari L, Masson B (2013) Negative interactions in irreversible self-assembly. Algorithmica 66(1):153–172MathSciNetCrossRef

Evans C (2014) Crystals that count! physical principles and experimental investigations of dna tile self-assembly. Ph.D. thesis, California Inst. of Tech

Goles E, Meunier PE, Rapaport I, Theyssier G (2011) Communication complexity and intrinsic universality in cellular automata. Theor Comput Sci 412(1–2):2–21MathSciNetCrossRef

Kanaras AG, Wang Z, Bates AD, Cosstick R, Brust M (2003) Towards multistep nanostructure synthesis: programmed enzymatic self-assembly of DNA/gold systems. Angewandte Chemie International Edition 42(2):191–194CrossRef

Kawano R (2018) Synthetic ion channels and DNA logic gates as components of molecular robots. ChemPhysChem 19(4):359–366. https://doi.org/10.1002/cphc.201700982CrossRef

Keenan A, Schweller R, Sherman M, Zhong X (2016) Fast arithmetic in algorithmic self-assembly. Natural Comput 15(1):115–128MathSciNetCrossRef

Kimna C, Lieleg O (2019) Engineering an orchestrated release avalanche from hydrogels using DNA-nanotechnology. J Controll Release. https://doi.org/10.1016/j.jconrel.2019.04.028CrossRef

Kuroda SY (1964) Classes of languages and linear-bounded automata. Information and Control 7(2):207–223. https://doi.org/10.1016/S0019-9958(64)90120-2. URL http://www.sciencedirect.com/science/article/pii/S0019995864901202

Luchsinger A, Schweller R, Wylie T (2018) Self-assembly of shapes at constant scale using repulsive forces. Natural Comput. https://doi.org/10.1007/s11047-018-9707-9CrossRefMATH

Padilla JE, Patitz MJ, Pena R, Schweller RT, Seeman NC, Sheline R, Summers SM, Zhong X (2013) Asynchronous signal passing for tile self-assembly: Fuel efficient computation and efficient assembly of shapes. In: Unconventional Computation and Natural Computation, pp. 174–185. Springer

Schweller R, Sherman M (2013) Fuel efficient computation in passive self-assembly. In: Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA’13, pp. 1513–1525. SIAM

Schweller R, Winslow A, Wylie T (2017) Complexities for high-temperature two-handed tile self-assembly. In: Brijder R, Qian L (eds) DNA computing and molecular programming. Springer, Cham, pp 98–109CrossRef

Schweller R, Winslow A, Wylie T (2019) Nearly constant tile complexity for any shape in two-handed tile assembly. Algorithmica 81(8):3114–3135MathSciNetCrossRef

Schweller R, Winslow A, Wylie T (2019) Verification in staged tile self-assembly. Natural Comput 18(1):107–117MathSciNetCrossRef

Spakowski H (2006) Completeness for parallel access to np and counting class separation. Ausgezeichnete Informatikdissertationen 2005

Winfree E (1998) Algorithmic self-assembly of DNA. Ph.D. thesis, California Institute of Technology

Winslow A (2015) Staged self-assembly and polyomino context-free grammars. Natural Comput 14(2):293–302MathSciNetCrossRef

Worsch T (2013) Towards intrinsically universal asynchronous ca. Natural Comput 12(4):539–550MathSciNetCrossRef

Title: Verification and computation in restricted Tile Automata
Authors: David Caballero
Timothy Gomez
Robert Schweller
Tim Wylie
Publication date: 17-11-2021
Publisher: Springer Netherlands
Published in: Natural Computing
Print ISSN: 1567-7818
Electronic ISSN: 1572-9796
DOI: https://doi.org/10.1007/s11047-021-09875-x

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner