Skip to Main content Skip to Navigation
New interface
Journal articles

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

Abstract : Catalytic 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.
Complete list of metadata

https://hal.archives-ouvertes.fr/hal-03650217
Contributor : Frédéric Davesne Connect in order to contact the contributor
Submitted on : Sunday, April 24, 2022 - 5:29:11 PM
Last modification on : Friday, May 13, 2022 - 9:23:03 PM

Links full text

Identifiers

Citation

Artiom Alhazov, Rudolf Freund, Sergiu Ivanov, Marion Oswald. Variants of derivation modes for which purely catalytic P systems are computationally complete. Theoretical Computer Science, 2022, 920, pp.95--112. ⟨10.1016/j.tcs.2022.03.007⟩. ⟨hal-03650217⟩

Share

Metrics

Record views

47