Skip to Main content Skip to Navigation
Journal articles

Variants of derivation modes for which catalytic P systems with one catalyst are computationally complete

Abstract : Abstract Catalytic P systems are among the first variants of membrane systems ever considered in this area. This variant of systems also features some prominent computational complexity questions, and in particular the problem of using only one catalyst: is one catalyst enough to allow for generating all recursively enumerable sets of multisets? Several additional ingredients have been shown to be sufficient for obtaining even computational completeness with only one catalyst. Last year we could show that the derivation mode $$max_{objects}$$ m a x objects , 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 this paper we follow this way of research and show that one catalyst is also sufficient for obtaining computational completeness when using specific variants of derivation modes based on non-extendable multisets of rules: we only take those non-extendable multisets whose application yields the maximal number of generated objects or else those non-extendable multisets whose application yields the maximal difference in the number of objects between the newly generated configuration and the current configuration. A similar computational completeness result can even be obtained when omitting the condition of non-extendability of the applied multisets when taking the maximal difference of objects or the maximal number of generated objects. Moreover, we reconsider simple P system with energy control—both symbol and rule energy-controlled P systems equipped with these new variants of derivation modes yield computational completeness.
Document type :
Journal articles
Complete list of metadata

https://hal.archives-ouvertes.fr/hal-03438339
Contributor : Frédéric Davesne Connect in order to contact the contributor
Submitted on : Sunday, November 21, 2021 - 3:59:51 PM
Last modification on : Tuesday, November 23, 2021 - 3:41:13 AM

Links full text

Identifiers

Citation

Artiom Alhazov, Rudolf Freund, Sergiu Ivanov, Sergey Verlan. Variants of derivation modes for which catalytic P systems with one catalyst are computationally complete. Journal of Membrane Computing, In press, ⟨10.1007/s41965-021-00085-z⟩. ⟨hal-03438339⟩

Share

Metrics

Record views

34