DNA splicing systems and post systems.
This paper concerns the formal study on the generative powers of extended splicing (H) systems. First, using a classical result by Post which characterizes the recursively enumerable languages in terms of his Post Normal systems, we establish several new characterizations of extended H systems which not only allow us to have very simple alternative proof methods for the previous results mentioned above, but also give a new insight into the relationships between families of extended H systems. We show a kind of normal form for extended H systems exactly characterizing the class of regular languages. We also show a new representation result for the family of context-free languages in terms of extended H systems.
Ferretti
C
C
Department of Computer Science and Information Mathematics, University of Electro-Communications, Tokyo, Japan. ferretti.gold.cs.uec.ac.jp
Kobayashi
S
S
D017398:Alternative Splicing; D003198:Computer Simulation; D004247:DNA / Q000737:chemistry* / Q000235:genetics*; D008957:Models, Genetic; D012984:Software
D004247:DNA