|
Journal of Automata, Languages and Combinatorics
formerly:
Journal of Information Processing and Cybernetics /
Elektronische Informationsverarbeitung und Kybernetik
|
|
@article{jalc010103,
author = {Gheorghe P\u{a}un},
title = {Regular Extended H Systems are Computationally Universal},
journal = jalc,
year = 1996,
volume = 1,
number = 1,
pages = {27--36},
keywords = {DNA recombination, splicing, H systems, Turing machines,
descriptional complexity, DNA computing},
abstract = {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).}
}