Skip to Main content Skip to Navigation
Journal articles

When catalytic P systems with one catalyst can be computationally complete

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 in the whole system: 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 computational completeness even with only one catalyst. In this paper, we show that one catalyst is sufficient for obtaining computational completeness if either catalytic rules have weak priority over non-catalytic rules or else instead of the standard maximally parallel derivation mode, we use the derivation mode maxobjects , i.e., we only take those multisets of rules which affect the maximal number of objects in the underlying configuration.
Complete list of metadata

https://hal.archives-ouvertes.fr/hal-03320415
Contributor : Frédéric Davesne Connect in order to contact the contributor
Submitted on : Sunday, August 15, 2021 - 10:23:12 PM
Last modification on : Wednesday, October 13, 2021 - 7:58:04 PM

Links full text

Identifiers

Citation

Artiom Alhazov, Rudolf Freund, Sergiu Ivanov. When catalytic P systems with one catalyst can be computationally complete. Journal of Membrane Computing, 2021, 3, pp.170--181. ⟨10.1007/s41965-021-00079-x⟩. ⟨hal-03320415⟩

Share

Metrics

Record views

117