C. Ferretti, S. Kobayashi
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.