(Fénix Editora, 2006) Dassow, Jürgen; Csuhaj Varjú, Erzsébet
Membrane or P systems form a distributed parallel model of computing
which is obtained as an abstraction from the structure and functioning of living cells.
In this paper we consider a very basic membrane system and add to it checkers which
are special finite automata to check whether or not a configuration of the membrane
system is "good" or "bad". The computation is only continued if the configuration is
good, otherwise it stops without a result. Such membrane systems are called Darwinian
P systems. There are three parameters characterizing the size of a system, the number
of membranes, the number of checkers, and the size of the checkers measured by the
number of states. We prove that we can generate all sets of Parikh vectors of recursively
enumerable languages if we restrict the number and size of checkers to one checker with
six states or to five checkers with two states. Moreover, we prove that Darwinian systems
with one membrane and checkers with at most two states are also sufficient to generate
all Parikh sets of recursively enumerable languages. The latter result is optimal since
Darwinian systems with checkers with only one state generate only sets of Parikh vectors
of ET0L languages. All results are valid for length sets instead of sets of Parikh vectors,
too.
