PubMed · 9390239
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.
Explore related subjects
Keep this discovery
Explore connections, maps & timelines
C Ferretti, S Kobayashi. 1996. DNA splicing systems and post systems.. https://pubmed.ncbi.nlm.nih.gov/9390239/
Cite the original work for its findings. Save a collection to share your selection of sources.