TY - JOUR

T1 - On the computing powers of L-reductions of insertion languages

AU - Okubo, Fumiya

AU - Yokomori, Takashi

N1 - Funding Information:
The authors deeply acknowledge the referees for their careful reading and valuable comments which greatly improved the readability and the consistency of this paper. The work of F. Okubo was in part supported by JSPS KAKENHI Grant Number JP16K16008 . The work of T. Yokomori was in part supported by JSPS KAKENHI, Grant-in-Aid for Scientific Research (C) JP17K00021 .
Publisher Copyright:
© 2020 Elsevier B.V.

PY - 2021/3/16

Y1 - 2021/3/16

N2 - 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 INS⁎0 (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 INS⁎0%{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 INS⁎0%{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.

AB - 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 INS⁎0 (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 INS⁎0%{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 INS⁎0%{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.

KW - Context-free languages

KW - Dyck-reduction

KW - Insertion systems and languages

KW - Recursively enumerable languages

UR - http://www.scopus.com/inward/record.url?scp=85096841897&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85096841897&partnerID=8YFLogxK

U2 - 10.1016/j.tcs.2020.11.029

DO - 10.1016/j.tcs.2020.11.029

M3 - Article

AN - SCOPUS:85096841897

SN - 0304-3975

VL - 862

SP - 224

EP - 235

JO - Theoretical Computer Science

JF - Theoretical Computer Science

ER -