Toward minimum size self-assembled counters

DNA self-assembly is a promising paradigm for nanotechnology. In this paper we study the problem of finding tile systems of minimum size that assemble a given shape in the Tile Assembly Model, defined by Rothemund and Winfree (Proceedings of the thirty-second annual ACM symposium on theory of computing, 2000). We present a tile system that assembles an \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$N\times\lceil\log_2 N\rceil$$\end{document} rectangle in asymptotically optimal \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\Uptheta(N)$$\end{document} time. This tile system has only 7 tiles. Earlier constructions need at least 8 tiles (Chen et al. Proceedings of symposium on discrete algorithms, 2004). We managed to reduce the number of tiles without increasing the assembly time. The new tile system works at temperature 3. The new construction was found by the combination of exhaustive computerized search of the design space and manual adjustment of the search output.