Abstract
A duplication is one of the basic phenomena that occur in molecular evolution on a biological sequence. A duplication on a string is a process of copying a substring of the string—Given w = x1x2x3, a duplication of w is x1x2x2x3. We define k-pseudo-duplication of a string w to be a set of all strings obtained from w by inserting after a substring u of w another substring uʹ such that the edit distance between u and uʹ is at most k. We consider duplication, k-pseudo-duplication and reverse duplication as operations on formal languages. First, we demonstrate that regular languages and context-free languages are not closed under the duplication, k-pseudo-duplication and reverse-duplication operations. Second, we show that context-sensitive languages are closed under duplication, pseudo-duplication and reverse-duplication. Last, we present the necessary and sufficient number of states that a nondeterministic finite automaton needs to recognize all duplications of a string with respect to the string length.
| Original language | English |
|---|---|
| Pages (from-to) | 145-167 |
| Number of pages | 23 |
| Journal | International Journal of Unconventional Computing |
| Volume | 12 |
| Issue number | 2-3 |
| Publication status | Published - 2016 |
Bibliographical note
Funding Information:Cho and Han were supported by the Basic Science Research Program through NRF funded by MEST (2015R1D1A1A01060097), the International Cooperation Program managed by NRF of Korea (2014K2A1A2048512) and Yonsei University Future-leading Research Initiative of 2015. Kim was supported by NRF-2013-Global Ph.D. Fellowship Program and Salomaa was supported by the Natural Sciences and Engineering Research Council of Canada Grant OGP0147224.
Publisher Copyright:
© 2016 Old City Publishing, Inc.
All Science Journal Classification (ASJC) codes
- Computer Science(all)