Variants of derivation modes for which purely catalytic P systems are computationally complete

International audienceCatalytic P systems and purely catalytic P systems are among the first variants of membrane systems ever considered in this area. These variants of systems also feature some prominent computational complexity questions, and in particular the problem if only one catalyst in catalytic P systems and two catalysts in purely catalytic P systems are enough to allow for generating all recursively enumerable sets of multisets. Several additional ingredients have been shown to be sufficient for obtaining such results. Previously, we could show that using the derivation mode maxobjects, where we only take those multisets of rules which affect the maximal number of objects in the underlying configuration, one catalyst is sufficient for obtaining computational completeness without any other ingredients in catalytic P systems. In this paper we investigate the question whether we can obtain a similar result for purely catalytic P systems, i.e., we show that two catalysts in purely catalytic P systems are enough to allow for generating all recursively enumerable sets of multisets when using specific variants of the maximally parallel derivation mode: we take only those applicable multisets of rules which (i) generate the maximal number of objects, or (ii) yield the maximal difference in the number of objects between the newly generated configuration and the current configuration. In addition, we also consider non-extendable multisets of rules which (i) generate the minimal number of objects, or (ii) yield the minimal difference in the number of objects between the newly generated configuration and the current configuration. In all cases, we have also shown that register machines with n decrementable registers can be simulated by simple purely catalytic P systems working in any of these derivation modes using only n catalysts. Hence, simple purely catalytic P systems working in any of these derivation modes are computationally complete