HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
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

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 : Thursday, February 10, 2022 - 11:48:03 PM

Links full text



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⟩



Record views