On the computing powers of L-reductions of insertion languages

We investigate the computing power of the following language operation %: Given two languages L₁ over Σ and L₂ over Γ with Γ⊂Σ, we consider the language operation L₁%L₂={u₀u₁⋯u_n|∃u=u₀v₁u₁⋯v_nu_n∈L₁ and ∃v_i∈L₂(1≤∀i≤n)}. In this case we say that L(=L₁%L₂) is the L₂-reduction of L₁. This is extended to the language families as follows: L₁%L₂={L₁%L₂|L₁∈L₁,L₂∈L₂}. 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={xⁿx‾ⁿ|n∈N} and that min-LIN%{D₂}=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∈INS₃⁰ and a Dyck language D, where INS_⁎⁰ (INS₃⁰) 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 INS_⁎⁰%{D₂}=RE, where D₂ denotes the Dyck language over binary alphabet. For context-free languages, we show that INS₃⁰%F=CF, where F is the family of finite sets. This also derives that INS_⁎⁰%{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∈INS₂⁰ 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 L₂-reduction of L₁. 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.