Y. Sakakibara, C. Ferretti
Splicing on tree-like structures.
Abstract
In this paper, we provide a method to accelerate the power of
splicing systems.
We introduce the splicing systems on trees to be
built as partially annealed single strands, that is a quite similar
notion and a natural extension of splicing systems on strings.
Trees are a common and useful data structure in computer science
and have a biological counterpart such as molecular sequences
with secondary structures, which are typical structures in RNA sequences.
Splicing on trees involves (1) complete subtrees as axioms,
(2) restriction operated on the annealed subsequences,
(3) rules to substitute a complete subtree with another.
We show that splicing systems on trees with finite sets of axioms
and finite sets of rules can generate the class of context-free
languages without the need of multiplicity constraints.