Abstract
Given a string, a non-overlapping inversion is to reverse some non-overlapping fragments of the string simultaneously. We define a non-overlapping inversion operation to be the computation of all possible non-overlapping inversions. We apply the operation on a string, which gives rise to a set of strings, and construct an NFA recognizing the set. Then, we design an efficient DFA reduction algorithm from the resulting NFA. We also consider the non-overlapping inversion operation on a language and show the closure properties for regular, context-free and context-sensitive languages. We furthermore examine iterative non-overlapping inversions and establish the closure properties. Finally, we introduce non-overlapping inversion-free languages and present the decidability results for regular and context-free languages.
| Original language | English |
|---|---|
| Pages (from-to) | 9-22 |
| Number of pages | 14 |
| Journal | Theoretical Computer Science |
| Volume | 592 |
| DOIs | |
| Publication status | Published - 2015 Aug 9 |
Bibliographical note
Funding Information:This research was supported by the Basic Science Research Program through NRF funded by MEST ( 2012R1A1A2044562 ) and the Yonsei University Future-leading Research Initiative of 2014. Kim was supported by NRF Grant funded by the Korean Government (NRF-2013-Global Ph.D. Fellowship Program).
Publisher Copyright:
© 2015 Elsevier B.V.
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- Computer Science(all)