title: DNA splicing systems and post systems.
abstract: 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.
authors.affiliation: Department of Computer Science and Information Mathematics, University of Electro-Communications, Tokyo, Japan. ferretti.gold.cs.uec.ac.jp
authors.forename: C
authors.initials: C
authors.lastname: Ferretti
authors.forename: S
authors.initials: S
authors.lastname: Kobayashi
mesh_terms: D017398:Alternative Splicing; D003198:Computer Simulation; D004247:DNA / Q000737:chemistry* / Q000235:genetics*; D008957:Models, Genetic; D012984:Software
chemical_list: D004247:DNA