On the computing powers of L-reductions of insertion languages

Fumiya Okubo, Takashi Yokomori

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)


We investigate the computing power of the following language operation %: Given two languages L1 over Σ and L2 over Γ with Γ⊂Σ, we consider the language operation L1%L2={u0u1⋯un|∃u=u0v1u1⋯vnun∈L1 and ∃vi∈L2(1≤∀i≤n)}. In this case we say that L(=L1%L2) is the L2-reduction of L1. This is extended to the language families as follows: L1%L2={L1%L2|L1∈L1,L2∈L2}. Among many works concerning Dyck-reductions, for the family of recursively enumerable languages RE, it was shown that LIN%{EQ}=RE (Jantzen & Petersen, 1994) with EQ={xnx‾n|n∈N} and that min-LIN%{D2}=RE (Hirose & Okawa, 1996, and Latteux & Turakainen, 1990), where LIN and min-LIN are the families of linear and minimal linear context-free languages, respectively. In this paper, we show that each recursively enumerable language L can be represented in the form L=K%D, for some K∈INS30 and a Dyck language D, where INS0 (INS30) denotes the family of insertion languages (insertion languages where the maximum length of the string to be inserted is 3). We can refine it as INS0%{D2}=RE, where D2 denotes the Dyck language over binary alphabet. For context-free languages, we show that INS30%F=CF, where F is the family of finite sets. This also derives that INS0%{MIR}=CF with MIR={xx‾R|x∈{0,1}}. Further, for regular languages, it is shown that each regular language R can be represented in the form R=K%F, for some K∈INS20 and a finite set F={abb‾a‾|a∈V}. We also present some results which characterize the computability and properties of L in the framework of L2-reduction of L1. It is intriguing to note that, from the DNA computing point of view, the notion of L-reduction is naturally motivated by a molecular biological functioning well-known as DNA(RNA) splicing occurring in most eukaryotic genes.

Original languageEnglish
Pages (from-to)224-235
Number of pages12
JournalTheoretical Computer Science
Publication statusPublished - Mar 16 2021
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'On the computing powers of L-reductions of insertion languages'. Together they form a unique fingerprint.

Cite this