Affiliations: Department of Languages and Software Engineering,
Faculty of Computer Science, Polytechnical University of Madrid, Campus de
Montegancedo, Boadilla del Monte 28660, Madrid, Spain | Facultad de Informática, Universidad Politécnica
de Madrid, Campus de Montegancedo s/n, Boadilla del Monte 28660 Madrid,
Spain
Abstract: We introduce a variant of P systems with string-objects – called
worm-objects – inspired in the DNA computing area. These systems work with
multisets of string-objects processed by splitting, mutation, replication and
recombination. This model is simpler (we eliminate the replication operation)
and more realistic (the recombination operation is changed by the simpler one
of suffix-prefix or head-tail concatenation developed in the DNA computing
framework) than the previous one. The result of a computation is the set of
strings sent out of the system. We work with multisets of strings but we
generate languages instead of sets of numbers. We prove that, without priority
among rules or other control mechanisms, (1) these P systems with at most three
membranes can generate all recursively enumerable languages, (2) with
non-decreasing length mutation and splitting rules, three membranes are enough
to generate the family of context-sensitive languages, and (3) with these
restricted types of splitting and mutation rules, four membranes can generate
the family of recursively enumerable languages.
Keywords: Membrane computing, P systems, Recursively enumerable languages
