Top

Natural Computing

Published in:

01-06-2015

Parallel computation using active self-assembly

Authors: Moya Chen, Doris Xin, Damien Woods

Published in: Natural Computing | Issue 2/2015

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

search-config

AI-assisted search

Off

Abstract

We study the computational complexity of the recently proposed nubots model of molecular-scale self-assembly. The model generalises asynchronous cellular automata to have non-local movement where large assemblies of molecules can be moved around, analogous to millions of molecular motors in animal muscle effecting the rapid movement of macroscale arms and legs. We show that nubots is capable of simulating Boolean circuits of polylogarithmic depth and polynomial size, in only polylogarithmic expected time. In computational complexity terms, we show that any problem from the complexity class NC is solved in polylogarithmic expected time on nubots that use a polynomial amount of workspace. Along the way, we give fast parallel algorithms for a number of problems including line growth, sorting, Boolean matrix multiplication and space-bounded Turing machine simulation, all using a constant number of nubot states (monomer types). Circuit depth is a well-studied notion of parallel time, and our result implies that nubots is a highly parallel model of computation in a formal sense. Asynchronous cellular automata are not capable of such parallelism, and our result shows that adding a movement primitive to such a model, to get the nubots model, drastically increases parallel processing abilities.

previous article Leaderless deterministic chemical reaction networks

next article Signal transmission across tile assemblies: 3D static tiles simulate active self-assembly by 2D signal-passing tiles

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

\({\mathrm{NC}}\), or Nick’s class, is named after Nicholas Pippenger.

By confluent we mean a kind of determinism where the system (rules with the input) is assumed to always make a unique single terminal assembly.

In Woods et al. (2013) the nubots model includes “agitation”: each monomer is repeatedly subjected to random movements intended to model a nano-scale environment where there is Brownian motion, uncontrolled movements and turbulent fluid flows in all directions. Our constructions in this paper work with or without agitation, hence they are robust to random uncontrolled movements, but we choose to ignore this issue and not formally define agitation for ease of presentation.

For simplicity, when counting the number of applicable rules for a configuration, a movement rule is counted twice, to account for the two choices of arm and base.

Our choice of a 1D, rather than 2D, encoding simplifies our constructions. It would also be possible use a more direct 2D square encoding, which, it turns out, can be unfolded to and from our line encoding in expected time \(O(\log n)\). We omit the details.

Our configurations include an output tape write symbol and an output tape head position which is not standard practice (Papadimitriou 1994), but will be useful in our construction.

Each configuration is of length polynomial in \(|x| = O(|\) \([\widetilde{x}]\) \(|)\), hence including \([\widetilde{x}]\) here does not change the asymptotics.

The line segments in an encoded matrix usually encode the matrix element’s \((i, j)\) coordinates, here we do things slightly differently: we are using encoded configurations, rather than natural numbers, as the matrix indices. This simplifies our constructions a little.

Aggarwal G, Cheng Q, Goldwasser MH, Kao M-Y, de Espanes PM, Schweller RT (2005) Complexities for generalized models of self-assembly. SIAM J Comput 34:1493–1515CrossRefMATHMathSciNet

Allender E, Koucký M (2010) Amplifying lower bounds by means of self-reducibility. JACM 14:1–36CrossRef

Aloupis G, Collette S, Demaine ED, Langerman S, Sacristán V, Wuhrer S (2008) Reconfiguration of cube-style modular robots using \(O(\log n)\) parallel moves. In: ISAAC: Proc. of the 19th Annual International Symposium on Algorithms and Computation, pp 342–353

Aloupis G, Collette S, Damian M, Demaine E, Flatland R, Langerman S, O’Rourke J, Pinciu V, Ramaswami S, Sacristán V, Wuhrer S (2011) Efficient constant-velocity reconfiguration of crystalline robots. Robotica 29(1):59–71CrossRef

Becker F, Remila E, Rapaport I (2006) Self-assemblying classes of shapes, fast and with minimal number of tiles. In: Proceedings of the 26th Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2006), vol 4337 of LNCS. Springer, pp 45–56

Butler Z, Fitch R, Rus D (2002) Distributed control for unit-compressible robots: goal-recognition, locomotion, and splitting. IEEE/ASME Trans Mechatron 7:418–430CrossRef

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: STACS: 30th International Symposium on Theoretical Aspects of Computer, Science, pp 172–184

Chandran H, Gopalkrishnan N, Reif J (2012) Tile complexity of approximate squares. Algorithmica 66(1):1–17CrossRefMathSciNet

Condon A (1994) A theory of strict P-completeness. Comput Complex 4(3):220–241CrossRefMATHMathSciNet

Dabby N, Chen H-L (2012) Active self-assembly of simple units using an insertion primitive. In: SODA: Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms, pp 1526–1536

Demaine E, Demaine M, Fekete S, Ishaque M, Rafalin E, Schweller R, Souvaine D (2008) Staged self-assembly: nanomanufacture of arbitrary shapes with \({O}(1)\) glues. Nat Comput 7(3):347–370CrossRefMATHMathSciNet

Demaine ED, Eisenstat S, Ishaque M, Winslow A (2011) One-dimensional staged self-assembly. In: DNA: 17th Intl Conf on DNA Computing & Molecular Programming, vol 6937 of LNCS. Pasadena, pp 100–114

Demaine ED, Patitz MJ, Rogers TA, Schweller RT, Summers SM, Woods D (2013) The two-handed tile assembly model is not intrinsically universal. In: ICALP: 40th International Colloquium on Automata, Languages and Programming. Proceedings, part 1, vol 7965 of LNCS. Riga, Latvia, pp 400–412. arXiv:1306.6710 [cs.CG]

Demaine ED, Demaine ML, Fekete SP, Patitz MJ, Schweller RT, Winslow A, Woods D (2014) One tile to rule them all: simulating any Turing machine, tile assembly system, or tiling system with a single puzzle piece. In: ICALP: Proceedings of the 41st International Colloquium on Automata, Languages, and Programming. arXiv:1212.4756 [cs.DS]

Doty D (2010) Randomized self-assembly for exact shapes. SICOMP 39:3521CrossRefMATHMathSciNet

Doty D, Lutz JH, Patitz MJ, Summers SM, Woods D (2009) Intrinsic universality in self-assembly. In: STACS: Proceedings of the 27th International Symposium on Theoretical Aspects of Computer, Science, pp 275–286

Doty D, Lutz JH, Patitz MJ, Schweller RT, Summers SM, Woods D (2012) The tile assembly model is intrinsically universal. In: FOCS: Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer, Science, pp 439–446

Fu B, Patitz M, Schweller R, Sheline B (2012) Self-assembly with geometric tiles. In: ICALP: The 39th International Colloquium on Automata, Languages and Programming, vol 7391 of LNCS. Springer, pp 714–725

Gillespie D (1992) A rigorous derivation of the chemical master equation. Phys A 188(1):404–425CrossRefMathSciNet

Greenlaw R, Hoover HJ, Ruzzo WL (1995) Limits to parallel computation: P-completeness theory. Oxford University Press, USAMATH

Hendricks J, Patitz MJ (2013) On the equivalence of cellular automata and the tile assembly model. In: MCU: Proceedings of Machines, Computations and Universality. University of Zürich, Switzerland. September 9–12, Electronic Proceedings in Theoretical Computer Science, vol 128, pp 167–189

Hendricks J, Padilla JE, Patitz MJ, Rogers TA (2013) Signal transmission across tile assemblies: 3D static tiles simulate active self-assembly by 2D signal-passing tiles. In: DNA19: The 19th International Conference on DNA Computing and Molecular Programming, vol 8141 of LNCS. Springer. arXiv:1306.5005 [cs.ET]

Jonoska N, McColm GL (2009) Complexity classes for self-assembling flexible tiles. Theoret Comput Sci 410(4):332–346CrossRefMATHMathSciNet

Jonoska N, Karpenko D (2012) Active tile self-assembly, self-similar structures and recursion. arXiv:1211.3085 [cs.ET]

Kao M., Schweller R. (2006) Reducing tile complexity for self-assembly through temperature programming. In: SODA: Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, ACM, pp 571–580

Kao M, Schweller R (2008) Randomized self-assembly for approximate shapes. In ICALP: Proceedings of the 35th International Colloquium on Automata, Languages and Programming, vol 5125 of LNCS. Springer, pp 370–384

Keenan A, Schweller R, Sherman M, Zhong X (2014) Fast arithmetic in algorithmic self-assembly. In: UCNC : the 13th International Conference on Unconventional Computation and Natural Computation. arXiv:1303.2416 [cs.DS]

Klavins E (2004) Directed self-assembly using graph grammars. Self Assembled Architectures and Devices, Snowbird, UT, In Foundations of Nanoscience

Malchik C, Winslow A (2014) Tight bounds for active self-assembly using an insertion primitive. The 22nd European Symposium on Algorithms. arXiv:1401.0359 [cs.FL]

Martin AC, Kaschube M, Wieschaus EF (2008) Pulsed contractions of an actin-myosin network drive apical constriction. Nature 457(7228):495–499CrossRef

Meunier P-E, Patitz MJ, Summers SM, Theyssier G, Winslow A, Woods D (2014) Intrinsic universality in tile self-assembly requires cooperation. In: SODA: ACM-SIAM Symposium on Discrete Algorithms, pp 752–771. arXiv:1304.1679 [cs.CC]

Murata S, Kurokawa H (2007) Self-reconfigurable robots. IEEE Robot Autom Mag 14(1):71–78CrossRef

Murphy N, Woods D (2013) AND and/or OR: uniform polynomial-size circuits. In MCU: Machines, Computations and Universality, vol 128, pp 150–166, EPTCS. arXiv:1212.3282

Murphy N, Naughton TJ, Woods D, Henley B, McDermott K, Duffy E, van der Burgt PJ, Woods N (2008) Implementations of a model of physical sorting. Int J Unconv Comput 4(1):3–12

Neary T, Woods D (2006) P-completeness of cellular automaton rule 110. In: ICALP: The 33rd International Colloquium on Automata, Languages and Programming, vol 4051 of LNCS. Springer, pp 132–143

Padilla J, Liu W, Seeman N (2011) Hierarchical self assembly of patterns from the Robinson tilings: DNA tile design in an enhanced tile assembly model. Nat Comput 11(2):323–338CrossRefMathSciNet

Padilla J, Patitz M, Pena R, Schweller R, Seeman N, Sheline R, Summers S, Zhong X (2013) Asynchronous signal passing for tile self-assembly: fuel efficient computation and efficient assembly of shapes. In Unconventional Computation and Natural Computation, vol 7956 of LNCS. Springer, pp 174–185

Papadimitriou CM (1994) Computational complexity. Addison-Wesley, New YorkMATH

Patitz MJ (2012) An introduction to tile-based self-assembly. In: Unconventional Computation and Natural Computation, vol 7445 LNCS. Springer, pp 34–62

Prusinkiewicz P, Lindenmayer A (1990) The algorithmic beauty of plants. Springer, New YorkCrossRefMATH

Reif J, Slee S (2007) Optimal kinodynamic motion planning for 2D reconfiguration of self-reconfigurable robots. Robot Sci Syst 12(2):81–115

Rothemund PWK, Winfree E (2000) The program-size complexity of self-assembled squares (extended abstract). In: STOC: Proceedings of the thirty-second annual ACM symposium on Theory of computing. ACM Press, pp 459–468

Rus D, Vona M (2001) Crystalline robots: self-reconfiguration with compressible unit modules. Auton Robots 10(1):107–124CrossRefMATH

Schultes D (2006) Rainbow sort: sorting at the speed of light. Nat Comput 5(1):67–82CrossRefMATHMathSciNet

Soloveichik D, Cook M, Winfree E, Bruck J (2008) Computation with finite stochastic chemical reaction networks. Nat Comput 7(4):615–633CrossRefMATHMathSciNet

Summers S (2012) Reducing tile complexity for the self-assembly of scaled shapes through temperature programming. Algorithmica 4:1–20

Vollmer H (1999) Introduction to circuit complexity: a uniform approach. Springer, New YorkCrossRef

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

Woods D (2005) Upper bounds on the computational power of an optical model of computation. In: Algorithms and Computation. Springer, pp 777–788

Woods D (2013) Intrinsic universality and the computational power of self-assembly. In: MCU: Proceedings of Machines, Computations and Universality, vol 128. Univ. of Zürich, Switzerland. Sept 9–12, Electronic Proceedings in Theoretical Computer Science, pp 16–22

Woods D, Naughton TJ (2008) Parallel and sequential optical computing. In: Optical supercomputing, vol 5172 of LNCS. Springer, pp 70–86

Woods D, Chen H-L, Goodfriend S, Dabby N, Winfree E, Yin P (2013) Active self-assembly of algorithmic shapes and patterns in polylogarithmic time. In: ITCS’13: Proceedings of the 4th conference on Innovations in Theoretical Computer Science. ACM, pp 353–354. Full version: arXiv:1301.2626 [cs.DS]

Yurke B, Turberfield AJ, Mills AP Jr, Simmel FC, Nuemann JL (2000) A DNA-fuelled molecular machine made of DNA. Nature 406:605–608CrossRef

Title: Parallel computation using active self-assembly
Authors: Moya Chen
Doris Xin
Damien Woods
Publication date: 01-06-2015
Publisher: Springer Netherlands
Published in: Natural Computing / Issue 2/2015
Print ISSN: 1567-7818
Electronic ISSN: 1572-9796
DOI: https://doi.org/10.1007/s11047-014-9432-y

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"

Other articles of this Issue 2/2015

Empirical modeling using genetic programming: a survey of issues and approaches

Exponential replication of patterns in the signal tile assembly model

Leaderless deterministic chemical reaction networks

Preface

3-color bounded patterned self-assembly

Staged self-assembly and polyomino context-free grammars

Premium Partner