@inproceedings{b4b9a9a4d8c04cd986bac38dce2f4e2b,
title = "Pseudo-inversion on formal languages",
abstract = "We consider the pseudo-inversion operation inspired by a biological event as a result of the partial inversion. We define the pseudo-inversion of a string w=uxv to consist of all strings vRxuR, where uv ≠ λ 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 consider the iterated pseudo-inversion operation and establish the basic properties. Finally, we introduce the pseudo-inversion-freeness and examine closure properties and decidability problems for regular and context-free languages. We establish that pseudo-inversion-freeness is decidable in polynomial time for regular languages and undecidable for context-free languages.",
author = "Cho, {Da Jung} and Han, {Yo Sub} and Kang, {Shin Dong} and Hwee Kim and Ko, {Sang Ki} and Kai Salomaa",
year = "2014",
doi = "10.1007/978-3-319-08123-6_8",
language = "English",
isbn = "9783319081229",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "93--104",
booktitle = "Unconventional Computation and Natural Computation - 13th International Conference, UCNC 2014, Proceedings",
address = "Germany",
note = "13th International Conference on Unconventional Computation and Natural Computation, UCNC 2014 ; Conference date: 14-07-2014 Through 18-07-2014",
}