Decision Problems for Linear and Circular Splicing Systems

摘要

We will consider here the splicing systems, generative devices inspired by cut and paste phenomena on DNA molecules under the action of restriction and ligase enzymes. A DNA strand can be viewed as a string over a four letter alphabet (the four deoxyribonucleotides), therefore we can model DNA computation within the framework of formal language theory. In spite of a vast literature on splicing systems, briefly surveyed here, a few problems related to their computational power are still open. We intend to evidence how classical techniques and concepts in automata theory are a legitimate tool for investigating some of these problems.