On the computing powers of L-reductions of insertion languages

Fumiya Okubo, Takashi Yokomori*


研究成果: Article査読

1 被引用数 (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.

ジャーナルTheoretical Computer Science
出版ステータスPublished - 2021 3月 16

ASJC Scopus subject areas

  • 理論的コンピュータサイエンス
  • コンピュータ サイエンス(全般)


「On the computing powers of L-reductions of insertion languages」の研究トピックを掘り下げます。これらがまとまってユニークなフィンガープリントを構成します。