Pseudo-inversion: closure properties and decidability

Da Jung Cho, Yo Sub Han, Shin Dong Kang, Hwee Kim, Sang Ki Ko, Kai Salomaa

Research output: Contribution to journalArticlepeer-review

1 Scopus citations


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 languageEnglish
Pages (from-to)31-39
Number of pages9
JournalNatural Computing
Issue number1
StatePublished - 1 Mar 2016


  • Bio-inspired operation
  • Closure properties
  • Decidability
  • Formal languages
  • Pseudo-inversion
  • Reversal-bounded multicounter machines


Dive into the research topics of 'Pseudo-inversion: closure properties and decidability'. Together they form a unique fingerprint.

Cite this