Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4950618 | Information and Computation | 2017 | 12 Pages |
Abstract
The operation of overlap assembly was defined by Csuhaj-Varjú, Petre, and Vaszil as a formal model of the linear self-assembly of DNA strands: The overlap assembly of two strings, xy and yz, which share an “overlap” y, results in the string xyz. This paper continues the exploration of the properties of the overlap assembly operation by investigating closure of various language classes under iterated overlap assembly, and the decidability of the completeness of a language. It also investigates the problem of deciding whether a given string is terminal with respect to a language, and the problem of deciding if a given language can be generated by an overlap assembly operation of two given others.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Srujan Kumar Enaganti, Oscar H. Ibarra, Lila Kari, Steffen Kopecki,