dc.contributor.author |
Paun, G |
en |
dc.date.accessioned |
2009-04-16T23:14:25Z |
en |
dc.date.available |
2009-04-16T23:14:25Z |
en |
dc.date.issued |
1997-12 |
en |
dc.identifier.citation |
CDMTCS Research Reports CDMTCS-072 (1997) |
en |
dc.identifier.issn |
1178-3540 |
en |
dc.identifier.uri |
http://hdl.handle.net/2292/3581 |
en |
dc.description.abstract |
First, we recall some characterizations of recursively enumerable
languages by means of finite H systems with certain regulations on the splicing
operation. Then, we consider a variant of the splicing operation where the
splicing proceeds always in couples of steps: the two strings obtained after a
splicing enter immediately a second splicing (the rules used in the two steps are
not prescribed). Somewhat surprising if we take into account the loose control
on the performed operations, extended H systems with finite sets of axioms and
of splicing rules, using this double splicing operation, can again characterize the
recursively enumerable languages. Finally, we consider two types of distributed
H systems: communicating distributed H systems and time-varying distributed
H systems. For the first type of devices, we give a new proof of the recent result of
[24] that (in the extended case) such systems with three components characterize
the recursively enumerable languages. In what concerns the second mentioned
distributed model, we prove that time-varying H systems with seven components
can characterize the recursively enumerable languages. The optimality of these
two last mentioned results is open. |
en |
dc.publisher |
Department of Computer Science, The University of Auckland, New Zealand |
en |
dc.relation.ispartofseries |
CDMTCS Research Report Series |
en |
dc.rights.uri |
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm |
en |
dc.source.uri |
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial |
en |
dc.title |
DNA Computing Based on Splicing: Universality Results |
en |
dc.type |
Technical Report |
en |
dc.subject.marsden |
Fields of Research::280000 Information, Computing and Communication Sciences |
en |
dc.rights.holder |
The author(s) |
en |
dc.rights.accessrights |
http://purl.org/eprint/accessRights/OpenAccess |
en |