Abstract
Two specific mappings called doublerf d and linearizerf ℓ are introduced to bridge two domains of languages. That is, f d 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 f d (L) for a minimal linear language L.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Hoogeboom, H.J., Vugt, N.V.: Fair sticker languages. Acta Informatica 37, 213–225 (2000)
Păun, G.: Marcus contextual grammar. Kluwer Academic Publishers, Dordrecht (1997)
Păun, G., Rozenberg, G., Salomaa, A.: DNA Computing. New Computing Paradigms. Springer, Heidelberg (1998)
Rozenberg, G., Salomaa, A. (eds.): Handbook of Formal Languages. Springer, Heidelberg (1997)
Salomaa, A.: Turing, Watson-Crick and Lindenmayer: Aspects of DNA Complementarity. In: Unconventional Models of Computation, Auckland, pp. 94–107. Springer, Heidelberg (1998)
Sakakibara, Y., Kobayashi, S.: Sticker systems with complex structures. Soft Computing 5, 114–120 (2001)
Vliet, R., van Hoogeboon, H.J., Rozenberg, G.: Combinatorial Aspects of Minimal DNA Expressions. In: Ferretti, C., Mauri, G., Zandron, C. (eds.) DNA 2004. LNCS, vol. 3384, pp. 84–96. Springer, Heidelberg (2005)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Onodera, K., Yokomori, T. (2006). Linearizer and Doubler : Two Mappings to Unify Molecular Computing Models Based on DNA Complementarity. In: Carbone, A., Pierce, N.A. (eds) DNA Computing. DNA 2005. Lecture Notes in Computer Science, vol 3892. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11753681_18
Download citation
DOI: https://doi.org/10.1007/11753681_18
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-34161-1
Online ISBN: 978-3-540-34165-9
eBook Packages: Computer ScienceComputer Science (R0)