Pseudo-inversion: closure properties and decidability |
| |
Authors: | Da-Jung Cho Yo-Sub Han Shin-Dong Kang Hwee Kim Sang-Ki Ko Kai Salomaa |
| |
Affiliation: | 1.Department of Computer Science,Yonsei University,Seoul,Republic of Korea;2.School of Computing,Queen’s University,Kingston,Canada |
| |
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 (w = uxv) to be the set of all strings (v^Rxu^R), where (uv ne lambda ) 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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|