L -reduction computation revisited

Kaoru Fujioka, Fumiya Okubo, Takashi Yokomori

Research output: Contribution to journalArticlepeer-review


Let K and L be two languages over Σ and Γ (with Γ ⊂ Σ), respectively. Then, the L-reduction of K, denoted by K%L, is defined by {u0u1⋯un∈(Σ-Γ)∗∣u0v1u1⋯vnun∈K,vi∈L(1≤i≤n)}. This is extended to language classes as follows: K%L={K%L∣K∈K,L∈L}. In this paper, we investigate the computing powers of K%L in which K ranges among various classes of INSji and min-LIN, while L is taken as DYCK and F, where INSji: the class of insertion languages of weight (j, i), min-LIN: the class of minimal linear languages, DYCK: the class of Dyck languages, and F: the class of finite languages. The obtained results include:INS11%DYCK=REINSi0%F=INSj1%F=CF (for i≥ 3 and j≥ 1)INS20%DYCK=INS20min-LIN%F1=LIN where RE, CF, LIN, F1 are classes of recursively enumerable, of context-free, of linear languages, and of singleton languages over unary alphabet, respectively. Further, we provide a very simple alternative proof for the known result min-LIN%DYCK2=RE. We also show that with a certain condition, for the class of context-sensitive languages CS, there exists no K such that K%DYCK=CS, which is in marked contrast to the characterization results mentioned above for other classes in Chomsky hierarchy. It should be remarked from the viewpoint of molecular computing theory that the notion of L-reduction is naturally motivated by a molecular biological functioning well-known as RNA splicing occurring in most eukaryotic genes.

Original languageEnglish
Pages (from-to)409-426
Number of pages18
JournalActa Informatica
Issue number4
Publication statusPublished - Aug 2022

All Science Journal Classification (ASJC) codes

  • Software
  • Information Systems
  • Computer Networks and Communications


Dive into the research topics of 'L -reduction computation revisited'. Together they form a unique fingerprint.

Cite this