Purely Catalytic P Systems: Two Catalysts Can Be Sufficient for Computational Completeness
Închide
Articolul precedent
Articolul urmator
683 0
SM ISO690:2012
FREUND, Rudolf. Purely Catalytic P Systems: Two Catalysts Can Be Sufficient for Computational Completeness. In: International Conference on Membrane Computing, 20-23 august 2013, Chișinău. Chișinău: "VALINEX" SRL, 2013, pp. 153-166. ISBN 978-9975-4237-2-4.
EXPORT metadate:
Google Scholar
Crossref
CERIF

DataCite
Dublin Core
International Conference on Membrane Computing 2013
Conferința "International Conference on Membrane Computing"
Chișinău, Moldova, 20-23 august 2013

Purely Catalytic P Systems: Two Catalysts Can Be Sufficient for Computational Completeness


Pag. 153-166

Freund Rudolf
 
University of Vienna
 
Disponibil în IBN: 1 iulie 2018


Rezumat

Whether purely catalytic P systems with only two catalysts can already be computational complete, is still an open problem. Here we establish computational completeness by using specific variants of additional control mechanisms. At each step using only multiset rules from one set of a finite number of sets of rules allows for obtaining computational completeness with two catalysts and only one membrane. If the available sets of rules change periodically with time, computational completeness can be obtained with two catalysts in one membrane, too. Moreover, we show computational completeness for purely catalytic P systems with two mobile catalysts and two membranes.