Regular Extended H Systems are Computationally Universal
Gheorghe Pǎun · Journal of automata, languages and combinatorics · 1996
Recently, a new type of generative mechanisms were introduced, under the name of H systems. They are based on the splicing operation, a language-theoretic counterpart of DNA recombination. Extended H systems with finite sets of rules are known to generate regular languages only. If (at least) linear sets of rules are used, then characterizations of recursively enumerable languages are obtained. The power of the intermediate class of H systems, with regular sets of splicing rules, is not yet known. We settle here the question, by proving that extended H systems with finite sets of axioms and regular sets of rules characterize the recursively enumerable languages, thus having the full power of Turing machines (in fact, one axiom is shown to suffice).