Doubler and linearizer: an approach toward a unified theory for molecular computing based on DNA complementarity

摘要

Two specific mappings called doubler f_d and linearizer f_e are introduced to bridge between two kinds of languages. Specifically, f_d maps string languages into (double-stranded) molecular languages, while f_e performs the opposite mapping. Using these mappings, we obtain new characterizations for the families of sticker languages and of Watson-Crick languages, which lead to not only a unified view of the two families of languages but also provide a helpful view on the computational capability of DNA complementarity. Furthermore, we introduce a special type of a projection f_(pr) which is composed of f_d and a projection in the usual sense. We show that any recursively enumerable language L can be expressed as f_(pr)(L_m) for a minimal linear language L_m. This result can be strengthened to L = f_(pr)(L_s), for a specific form of minimal linear language L_s, which provides a simple morphic characterization for the family of recursively enumerable languages.