Affiliations: Faculty of Informatics, Vienna University of Technology, Favoritenstr. 9, 1040 Vienna, Austria. rudi@emcc.at; marion@emcc.at | Institute of Mathematics of the Romanian Academy, PO Box 1-764, 014700 Bucureşti, Romania. ghpaun@gmail.com
Note: [] Address for correspondence: Faculty of Informatics, Vienna University of Technology, Favoritenstr. 9, 1040 Vienna, Austria
Abstract: The questions whether catalytic P systems with only one catalyst and purely catalytic P systems with only two catalysts can already be computationally complete in the generative case, still are open problems. For accepting P systems or P automata, the situation is even more complicated when we consider sets of vectors of natural numbers and not only sets of natural numbers – the number of catalysts increases with the dimension of the vectors. We here establish computational completeness for catalytic P systems and P automata with only one catalyst as well as for purely catalytic P systems and P automata with only two catalysts in the skin membrane by using specific variants of additional control mechanisms: in P systems and P automata with label selection, we only use rules from one set of a finite number of sets of rules in each computation step; in time-varying P systems and P automata the available sets of rules change periodically with time. The same control mechanisms also allow for computing partial recursive relations or functions of (vectors of) natural numbers when being used in catalytic P systems with one catalyst and purely catalytic P systems with two catalysts. Finally, these variants of P systems can also be used to generate or accept strings and to compute partial relations or functions on strings, and again we obtain computational completeness with only one catalyst in the case of catalytic P systems and two catalysts in the case of purely catalytic P systems.
