Abstract
We consider a pseudo-inversion operation inspired by biological events, such as DNA sequence transformations, where only parts of a string are reversed. We define the pseudo-inversion of a string (Formula presented.) to be the set of all strings (Formula presented.) , where (Formula presented.) and consider the operation from a formal language theoretic viewpoint. We show that regular languages are closed under the pseudo-inversion operation whereas context-free languages are not. Furthermore, we study the iterated pseudo-inversion operation and show that the iterated pseudo-inversion of a context-free language is recognized by a nondeterministic reversal-bounded multicounter machine. Finally, we introduce the notion of pseudo-inversion-freeness and examine closure properties and decidability problems for regular and context-free languages. We demonstrate that pseudo-inversion-freeness is decidable in polynomial time for regular languages and undecidable for context-free languages.
| Original language | English |
|---|---|
| Pages (from-to) | 31-39 |
| Number of pages | 9 |
| Journal | Natural Computing |
| Volume | 15 |
| Issue number | 1 |
| DOIs | |
| Publication status | Published - 2016 Mar 1 |
Bibliographical note
Funding Information:We wish to thank the referees for the careful reading of the paper and many valuable suggestions. Cho, Han, Kang and Ko were supported by the Basic Science Research Program through NRF funded by MEST (2012R1A1A2044562), the International Cooperation Program managed by NRF of Korea (2014K2A1A2048512) and Yonsei University Future-leading Research Initiative of 2014, 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:
© 2015, Springer Science+Business Media Dordrecht.
All Science Journal Classification (ASJC) codes
- Computer Science Applications