On the Hairpin Incompletion

• Autorzy: Okubo F. , Yokomori T.
• Języki publikacji: EN

Abstrakty

EN

Hairpin completion and its variant called bounded hairpin completion are operations on formal languages, inspired by a hairpin formation in molecular biology. Another variant called hairpin lengthening has been recently introduced, and the related closure properties and algorithmic problems concerning several families of languages have been studied. In this paper, we introduce a new operation of this kind, called hairpin incompletion which is not only an extension of bounded hairpin completion, but also a restricted (bounded) variant of hairpin lengthening. Further, the hairpin incompletion operation provides a formal language theoretic framework that models a bio-molecular technique nowadays known asWhiplash PCR. We study the closure properties of language families under both the operation and its iterated version. We show that a family of languages closed under intersection with regular sets, concatenation with regular sets, and finite union is closed under one-sided iterated hairpin incompletion, and that a family of languages containing all linear languages and closed under circular permutation, left derivative and substitution is also closed under iterated hairpin incompletion.

Słowa kluczowe

EN

hairpin incompletion

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2011
• Tom: Vol. 110, nr 1-4
• Strony: 255--269
• Opis fizyczny: Bibliogr. 18 poz.

Twórcy

autor

Okubo F.

autor

Yokomori T.

• Department of Mathematics, Faculty of Education and Integrated Arts and Sciences, Waseda University, 1-6-1 Nishiwaseda, Shinjuku-ku, Tokyo, Japan,

Bibliografia

• [1] J. Castellanos, V. Mitrana: Some remarks on hairpin and loop languages, in Words, Semigroups, and Translations, World Scientific, Singapore, pp.47-59, 2001.
• [2] D. Cheptea, C. Martin-Vide, V. Mitrana: A new operation on words suggested by DNA biochemistry: hairpin completion, in Proc. Transgressive Computing, pp.216-228, 2006.
• [3] M. Hagiya, M. Arita, D. Kiga, K. Sakamoto, and S. Yokoyama: Towards parallel evaluation and learning of Boolean μ-formulas with molecules, DNA Based Computers III (Rubin, H. and Wood, D. eds.), DIMACS Series in Discrete Mathematics, vol. 48, pp. 57-72, 2000.
• [4] M. Ito, P. Leupold, F. Manea, and V. Mitrana: Bounded hairpin completion, Information and Computation, vol.209, pp.471-485, 2011.
• [5] L. Kari, S. Konstantinidis, P. Sosik, G. Thierrin: On hairpin-free words and languages, in Proc. Developments in Language Theory 2005, LNCS 3572, Springer, pp.296-307, 2005.
• [6] K. Komiya and J.A. Rose: Experimental validation of signal dependent operation in Whiplash PCR, DNA Computing. 14th International Workshop on DNA-Based Computers (Goel, A. and Simmel, F.C., eds.), LNCS 5347, Springer, pp.1-10, 2009.
• [7] K. Komiya, K. Sakamoto, A. Kameda, M. Yamamoto, A. Ohuchi, D. Kiga, S. Yokoyama and M. Hagiya: DNA polymerase programmed with a hairpin DNA incorporates a multiple-instruction architecture into molecular computing, Biosystems, vol. 83, pp. 18-25, 2006.
• [8] S. Kopecki: On the iterated hairpin completion. In Y. Gao, H. Lu, S. Seki, and S. Yu (editors), 14th Developments in Language Theory, LNCS 6224, Springer, pp.438-439, 2010. Also, in http://arxiv.org/abs/1010.3640.
• [9] F. Manea, C. Mart´ın-Vide, V. Mitrana: On some algorithmic problems regarding the hairpin completion, Discrete Applied Mathematics, vol.157, pp.2143-2152, 2009.
• [10] F. Manea, C. Mart´ın-Vide, V. Mitrana: On the hairpin lengthening, submitted 2010.
• [11] F. Manea, V. Mitrana: Hairpin completion versus hairpin reduction, in Computation in Europe CiE 2007, LNCS 4497, Springer, pp.532-541, 2007.
• [12] F.Manea, V.Mitrana, T. Yokomori: Two complementary operations inspired by the DNA hairpin formation: completion and reduction, Theoretical Computer Science, vol.410, pp.41-425, 2009.
• [13] G. Pǎun, G. Rozenberg, A. Salomaa: DNA Computing, Springer-Verlag, Berlin (1998).
• [14] G. Pǎun, G. Rozenberg, T. Yokomori: Hairpin languages, Intern. J. Found. Comp. Sci., vol. 12, pp.837-847, 2001.
• [15] G. Rozenberg, A. Salomaa (Eds.): Handbook of Formal Languages, 3 volumes, Springer-Verlag, Berlin, Heidelberg (1997).
• [16] K. Sakamoto, D. Kiga, K. Komiya, H. Gouzu, S. Yokoyama, S. Ikeda, H. Sugiyama and M. Hagiya: State transitions by molecules, BioSystems, vol.52, no.1-3, pp.81-91, 1999.
• [17] K. Sakamoto, H. Gouzu, K. Komiya, D. Kiga, S. Yokoyama, T. Yokomori and M. Hagiya: Molecular computation by DNA hairpin formation, Science, vol. 288, pp.1223-1226, 2000.
• [18] A. Salomaa: Formal Languages, Academic Press (1973).