NDLI: Fast arithmetic in algorithmic self-assembly

Content Provider	Springer Nature Link
Author	Keenan, Alexandra Schweller, Robert Sherman, Michael Zhong, Xingsi
Copyright Year	2015
Abstract	In this paper we consider the time complexity of adding two n-bit numbers together within the tile self-assembly model. The (abstract) tile assembly model is a mathematical model of self-assembly in which system components are square tiles with different glue types assigned to tile edges. Assembly is driven by the attachment of singleton tiles to a growing seed assembly when the net force of glue attraction for a tile exceeds some fixed threshold. Within this frame work, we examine the time complexity of computing the sum of two n-bit numbers, where the input numbers are encoded in an initial seed assembly, and the output sum is encoded in the final, terminal assembly of the system. We show that this problem, along with multiplication, has a worst case lower bound of $$\varOmega ( \sqrt{n} )$$ in 2D assembly, and $$\varOmega (\root 3 \of {n})$$ in 3D assembly. We further design algorithms for both 2D and 3D that meet this bound with worst case run times of $$O(\sqrt{n})$$ and $$O(\root 3 \of {n})$$ respectively, which beats the previous best known upper bound of O(n). Finally, we consider average case complexity of addition over uniformly distributed n-bit strings and show how we can achieve $$O(\log n)$$ average case time with a simultaneous $$O(\sqrt{n})$$ worst case run time in 2D. As additional evidence for the speed of our algorithms, we implement our algorithms, along with the simpler O(n) time algorithm, into a probabilistic run-time simulator and compare the timing results.
Starting Page	115
Ending Page	128
Page Count	14
File Format	PDF
ISSN	15677818
Journal	Natural Computing
Volume Number	15
Issue Number	1
e-ISSN	15729796
Language	English
Publisher	Springer Netherlands
Publisher Date	2015-11-17
Publisher Place	Dordrecht
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Algorithmic self-assembly Computational geometry Adder Tile assembly model Theory of Computation Evolutionary Biology Processor Architectures Artificial Intelligence (incl. Robotics) Statistical Physics, Dynamical Systems and Complexity
Content Type	Text
Resource Type	Article
Subject	Computer Science Applications

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Exponential replication of patterns in the signal tile assembly model

An introduction to tile-based self-assembly and a survey of recent results

Distributed agreement in tile self-assembly

Parallel computation using active self-assembly

Self-assembly of discrete self-similar fractals

Hierarchical self assembly of patterns from the Robinson tilings: DNA tile design in an enhanced Tile Assembly Model

Error suppression mechanisms for DNA tile self-assembly and their simulation

Self-assembly of decidable sets

Robust self-assembly of graphs

Fast arithmetic in algorithmic self-assembly

Similar Documents

Exponential replication of patterns in the signal tile assembly model

An introduction to tile-based self-assembly and a survey of recent results

Distributed agreement in tile self-assembly

Parallel computation using active self-assembly

Self-assembly of discrete self-similar fractals

Hierarchical self assembly of patterns from the Robinson tilings: DNA tile design in an enhanced Tile Assembly Model

Error suppression mechanisms for DNA tile self-assembly and their simulation

Self-assembly of decidable sets

Robust self-assembly of graphs

Fast arithmetic in algorithmic self-assembly