Linearizer and Doubler : Two Mappings to Unify Molecular Computing Models Based on DNA Complementarity

摘要

Two specific mappings called doubler fd and linearizer f? are introduced to bridge two domains of languages. That is, fd maps string languages into (double-stranded) molecular languages, while f? transforms in the other way around. Using these mappings, we give new characterizations for the families of sticker languages and of Watson-Crick languages, which leads to not only a unified view of the two families of languages but also a clarified view of the computational capability of the DNA complementarity. One of the results implies that any recursively enumerable language can be expressed as the projective image of fd(L) for a minimal linear language L.