Multiplier System in the Tile Assembly Model with Reduced Tileset-Size
作者： Xiwen Fang , Xuejia Lai
DOI: 10.1007/978-3-319-01781-5_9
关键词:
摘要: Previously a 28-tile multiplier system which computes the product of two numbers was proposed by Brun. However tileset-size is not optimal. In this paper we prove that multiplication can be carried out using less tile types while maintaining same time efficiency: propose new assembly systems, both deterministically compute A*B for given A and B in constant time. Our first requires 24 computational our second 16 types, achieve smaller constants than Brun’s system.
springer.com
sci-hub.st 参考文章(15)
Qinghua Liu, Liman Wang, Anthony G. Frutos, Anne E. Condon, Robert M. Corn, Lloyd M. Smith, DNA computing on surfaces. Nature. ,vol. 403, pp. 175- 179 ,(2000) , 10.1038/35003155
Erik Winfree, Paul W. K. Rothemund, The program-size complexity of self-assembled squares ACM. ,(2000)
Yuriy Brun, Improving Efficiency of 3-SAT-Solving Tile Systems Lecture Notes in Computer Science. ,vol. 6518, pp. 1- 12 ,(2011) , 10.1007/978-3-642-18305-8_1
Erik Winfree, Furong Liu, Lisa A. Wenzler, Nadrian C. Seeman, Design and self-assembly of two-dimensional DNA crystals Nature. ,vol. 394, pp. 539- 544 ,(1998) , 10.1038/28998
DNA Computing and Molecular Programming Lecture Notes in Computer Science. ,vol. 6518, ,(2011) , 10.1007/978-3-642-18305-8
Michail G. Lagoudakis, Thomas H. LaBean, 2D DNA self-assembly for satisfiability. DNA Based Computers. pp. 141- 154 ,(1999)
Yuriy Brun, Solving NP-complete problems in the tile assembly model Theoretical Computer Science. ,vol. 395, pp. 31- 46 ,(2008) , 10.1016/J.TCS.2007.07.052
L. Adleman, Molecular computation of solutions to combinatorial problems Science. ,vol. 266, pp. 1021- 1024 ,(1994) , 10.1126/SCIENCE.7973651
Paul W. K. Rothemund, Erik Winfree, The program-size complexity of self-assembled squares (extended abstract) symposium on the theory of computing. pp. 459- 468 ,(2000) , 10.1145/335305.335358
Robert D. Barish, Paul W. K. Rothemund, Erik Winfree, Two Computational Primitives for Algorithmic Self-Assembly: Copying and Counting Nano Letters. ,vol. 5, pp. 2586- 2592 ,(2005) , 10.1021/NL052038L