Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Bücher
Zeitschriften
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
MTZ-Fachkongress

Antriebe und Energiesysteme von morgen


Austausch von Automobil- und Energiewirtschaft

Am 14./15. Mai geht es in Chemnitz um die Mobilitätswende durch Elektro- und Wasserstofffahrzeuge.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Chemical Reaction Networks and Stochastic Local Search Kapitel lesen Erstes Kapitel lesen

2019 | OriginalPaper | Buchkapitel

Simulation of Programmable Matter Systems Using Active Tile-Based Self-Assembly

verfasst von : John Calvin Alumbaugh, Joshua J. Daymude, Erik D. Demaine, Matthew J. Patitz, Andréa W. Richa

Erschienen in: DNA Computing and Molecular Programming

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

Self-assembly refers to the process by which small, simple components mix and combine to form complex structures using only local interactions. Designed as a hybrid between tile assembly models and cellular automata, the Tile Automata (TA) model was recently introduced as a platform to help study connections between various models of self-assembly. However, in this paper we present a result in which we use TA to simulate arbitrary systems within the amoebot model, a theoretical model of programmable matter in which the individual components are relatively simple state machines that are able to sense the states of their neighbors and to move via series of expansions and contractions.
We show that for every amoebot system, there is a TA system capable of simulating the local information transmission built into amoebot particles, and that the TA “macrotiles” used to simulate its particles are capable of simulating movement (via attachment and detachment operations) while maintaining the necessary properties of amoebot particle systems. The TA systems are able to utilize only the local interactions of state changes and binding and unbinding along tile edges, but are able to fully simulate the dynamics of these programmable matter systems.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren
Vorheriges Kapitel Non-cooperatively Assembling Large Structures
Nächstes Kapitel Combined Amplification and Molecular Classification for Gene Expression Diagnostics
Fußnoten
1
Note that there may be ambiguity in choosing a port facing local direction 0; e.g., in Fig. 3c, both port 0 and port 8 face local direction 0. In this case, the port facing local direction 0 and “away” from the particle is labeled 0.
 
2
Note that this forced scheduling is simply a result of our formalism and does not alter or subvert the underlying asynchrony assumed by the amoebot model.
 
Literatur
1.
Alumbaugh, J.C., Daymude, J.J., Demaine, E.D., Patitz, M.J., Richa, A.W.: Simulation of programmable matter systems using active tile-based self-assembly. Technical Reports 1906.01773, Computing Research Repository (2019). http://​arxiv.​org/​abs/​1906.​01773
2.
Andrés Arroyo, M., Cannon, S., Daymude, J.J., Randall, D., Richa, A.W.: A stochastic approach to shortcut bridging in programmable matter. Nat. Comput. 17(4), 723–741 (2018)MathSciNetCrossRef
3.
4.
Cannon, S., Daymude, J.J., Randall, D., Richa, A.W.: A Markov chain algorithm for compression in self-organizing particle systems. In: Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing, pp. 279–288, PODC 2016. ACM, New York (2016)
5.
6.
Daymude, J.J., Gmyr, R., Richa, A.W., Scheideler, C., Strothmann, T.: Improved leader election for self-organizing programmable matter. In: Fernández Anta, A., Jurdzinski, T., Mosteiro, M.A., Zhang, Y. (eds.) ALGOSENSORS 2017. LNCS, vol. 10718, pp. 127–140. Springer, Cham (2017). https://​doi.​org/​10.​1007/​978-3-319-72751-6_​10CrossRef
7.
Daymude, J.J., Hinnenthal, K., Richa, A.W., Scheideler, C.: Computing by programmable particles. In: Flocchini, P., Prencipe, G., Santoro, N. (eds.) Distributed Computing by Mobile Entities: Current Research in Moving and Computing. LNCS, vol. 11340, pp. 615–681. Springer, Cham (2019). https://​doi.​org/​10.​1007/​978-3-030-11072-7_​22CrossRef
8.
Demaine, E.D., Patitz, M.J., Rogers, T.A., Schweller, R.T., Summers, S.M., Woods, D.: The two-handed tile assembly model is not intrinsically universal. In: Fomin, F.V., Freivalds, R., Kwiatkowska, M., Peleg, D. (eds.) ICALP 2013. LNCS, vol. 7965, pp. 400–412. Springer, Heidelberg (2013). https://​doi.​org/​10.​1007/​978-3-642-39206-1_​34CrossRef
9.
Derakhshandeh, Z., Gmyr, R., Richa, A.W., Scheideler, C., Strothmann, T.: Universal shape formation for programmable matter. In: Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures SPAA, pp. 289–299. 2016. ACM, New York (2016)
10.
Derakhshandeh, Z., Gmyr, R., Richa, A.W., Scheideler, C., Strothmann, T.: Universal coating for programmable matter. Theor. Comput. Sci. 671, 56–68 (2017)MathSciNetCrossRef
11.
Derakhshandeh, Z., Richa, A., Dolev, S., Scheideler, C., Gmyr, R., Strothmann, T.: Brief announcement: amoebot-a new model for programmable matter. In: Annual ACM Symposium on Parallelism in Algorithms and Architectures, pp. 220–222. Association for Computing Machinery (2014)
12.
Doty, D., Lutz, J.H., Patitz, M.J., Schweller, R.T., Summers, S.M., Woods, D.: The tile assembly model is intrinsically universal. In: 2012 Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science, pp. 302–310. FOCS (2012)
13.
Fekete, S.P., Hendricks, J., Patitz, M.J., Rogers, T.A., Schweller, R.T.: Universal computation with arbitrary polyomino tiles in non-cooperative self-assembly. In: 2015 Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2015), San Diego, CA, USA, pp. 148–167, 4–6 January 2015
14.
Gilbert, O., Hendricks, J., Patitz, M.J., Rogers, T.A.: Computing in continuous space with self-assembling polygonal tiles. In: 2016 Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2016), Arlington, VA, USA, pp. 937–956, 10–12 January 2016
15.
Hendricks, J., Padilla, J.E., Patitz, M.J., Rogers, T.A.: Signal transmission across tile assemblies: 3D static tiles simulate active self-assembly by 2D signal-passing tiles. In: Soloveichik, D., Yurke, B. (eds.) DNA 2013. LNCS, vol. 8141, pp. 90–104. Springer, Cham (2013). https://​doi.​org/​10.​1007/​978-3-319-01928-4_​7CrossRef
16.
Hendricks, J., Patitz, M.J., Rogers, T.A., Summers, S.M.: The power of duples (in self-assembly): it’s not so hip to be square. Theor. Comput. Sci. 743, 148–166 (2015) MathSciNetCrossRef
17.
18.
Meunier, P.E., Patitz, M.J., Summers, S.M., Theyssier, G., Winslow, A., Woods, D.: Intrinsic universality in tile self-assembly requires cooperation. In: 2014 Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA 2014), Portland, OR, USA, pp. 752–771, 5–7 January 2014
19.
Meunier, P., Woods, D.: The non-cooperative tile assembly model is not intrinsically universal or capable of bounded turing machine simulation. In: 2017 Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, pp. 328–341, 19–23 June 2017
20.
Padilla, J.E., Patitz, M.J., Schweller, R.T., Seeman, N.C., Summers, S.M., Zhong, X.: Asynchronous signal passing for tile self-assembly: Fuel efficient computation and efficient assembly of shapes. Int. J. Found. Comput. Sci. 25(4), 459–488 (2014)MathSciNetCrossRef
21.
Patitz, M.J., Schweller, R.T., Summers, S.M.: Exact shapes and turing universality at temperature 1 with a single negative glue. In: 2011 Proceedings of the 17th International Conference on DNA Computing and Molecular Programming, pp. 175–189. DNA (2011)
22.
Winfree, E.: Algorithmic self-assembly of DNA. Ph.D. thesis, California Institute of Technology, June 1998
23.
Woods, D.: Intrinsic universality and the computational power of self-assembly. Philos. Trans. R. Soc. Lond. A: Math. Phys. Eng. Sci. 373(2046), 1–13 (2015)CrossRef
24.
Woods, D., Chen, H.L., Goodfriend, S., Dabby, N., Winfree, E., Yin, P.: Active self-assembly of algorithmic shapes and patterns in polylogarithmic time. In: Proceedings of the 4th Conference on Innovations in Theoretical Computer Science, ITCS 2013, pp. 353–354. ACM, New York (2013)
Metadaten
Titel
Simulation of Programmable Matter Systems Using Active Tile-Based Self-Assembly
verfasst von
John Calvin Alumbaugh
Joshua J. Daymude
Erik D. Demaine
Matthew J. Patitz
Andréa W. Richa
Copyright-Jahr
2019
Buch
DNA Computing and Molecular Programming

Print ISBN: 978-3-030-26806-0

Electronic ISBN: 978-3-030-26807-7

Copyright-Jahr: 2019

DOI
https://doi.org/10.1007/978-3-030-26807-7_8

Premium Partner

    Bildnachweise